On Sun, Jan 15, 2017 at 2:00 AM, Nate Cook via swift-evolution < swift-evolution@swift.org> wrote:
> > Link: https://github.com/natecook1000/swift/blob/nc- > bigint/test/Prototypes/BigInt.swift > > This is just a proof of concept BigInt implementation—there's not much in > the way of optimization going on, and it's a little out of date. It does > use sign-magnitude, so the word(at:) implementation is O(n) on each call > due to this bit: > > https://github.com/natecook1000/swift/blob/nc- > bigint/test/Prototypes/BigInt.swift#L571-L576 > > > The only other question I have from looking at this again is whether > perhaps BinaryInteger should have a toString(radix:uppercase:) method, > since arbitrary precision types may be able to optimize significantly for > different bases. The prototype at the link doesn't do this, but a hex > string (or any factor of 2 base?) should be far cheaper to generate than > the general case that uses repeated division. Without that, a BigInt type > doesn't have any way to customize the generic String<T>(_:radix:uppercase:) > initializer. > Oh yes, +1 to this idea. (Though for consistency it might be more aptly named `description(radix:uppercase:)`.) -Nate > > > I'm glad to see this moving forward. > > -Ben Spratling > > On Jan 14, 2017, at 2:00 AM, Rien via swift-evolution < > swift-evolution@swift.org> wrote: > > +1 > > Any change of including “ranged integers”? > I.e. an integer with a value that must fit in a predefined range? > > Regards, > Rien > > Site: http://balancingrock.nl > Blog: http://swiftrien.blogspot.com > Github: http://github.com/Swiftrien > Project: http://swiftfire.nl > > > > > On 13 Jan 2017, at 21:47, Max Moiseev via swift-evolution < > swift-evolution@swift.org> wrote: > > Hi everyone, > > Back in June 2016 we discussed the new design of the integer types for the > standard library. It even resulted in acceptance of SE-0104 for Swift 3. > Unfortunately we were not able to implement it in time for the release. > > But it was not forgotten, although, as time went by, a few changes needed > to be made in order to reflect the current state of the language. > Without further introduction, please welcome the refined proposal to make > integers in Swift more suitable for generic programming. > > Available in this gist https://gist.github.com/moiseev/ > 62ffe3c91b66866fdebf6f3fcc7cad8c and also inlined below. > > Max > > Protocol-oriented integers (take 2) > > • Proposal: SE-NNNN > • Authors: Dave Abrahams, Maxim Moiseev > • Review Manager: TBD > • Status: Awaiting review > • Bug: SR-3196 > • Previous Proposal: SE-0104 > Introduction > > This proposal is an evolution of SE-0104. The goal is still to clean up > Swifts integer APIs and make them more useful for generic programming. > > The language has evolved in ways that affect integers APIs since the time > the original proposal was approved for Swift 3. We also attempted to > implement the proposed model in the standard library and found that some > essential APIs were missing, whereas others could be safely removed. > > Major changes to the APIs introduced by this proposal (as compared to > SE-0104) are listed in a dedicated section. > > Motivation > > Swift's integer protocols don't currently provide a suitable basis for > generic programming. See this blog post for an example of an attempt to > implement a generic algorithm over integers. > > The way the Arithmetic protocol is defined, it does not generalize to > floating point numbers and also slows down compilation by requiring every > concrete type to provide an implementation of arithmetic operators, thus > polluting the overload set. > > Converting from one integer type to another is performed using the concept > of the 'maximum width integer' (see MaxInt), which is an artificial > limitation. The very existence of MaxInt makes it unclear what to do should > someone implement Int256, for example. > > Another annoying problem is the inability to use integers of different > types in comparison and bit-shift operations. For example, the following > snippets won't compile: > > var x: Int8 = 42 > let y = 1 > let z = 0 > > > x > <<= y // error: binary operator '<<=' cannot be applied to operands of > type 'Int8' and 'Int' > if x > z { ... } // error: binary operator '>' cannot be applied to > operands of type 'Int8' and 'Int' > Currently, bit-shifting a negative number of (or too many) bits causes a > trap on some platforms, which makes low-level bit manipulations needlessly > dangerous and unpredictable. > > Finally, the current design predates many of the improvements that came > since Swift 1, and hasn't been revised since then. > > Proposed solution > > We propose a new model that does not have above mentioned problems and is > more easily extensible. > > +--------------+ +-------------+ > +------>+ Arithmetic | | Comparable | > | | (+,-,*,/) | | (==,<,>,...)| > | +-------------++ +---+---------+ > | ^ ^ > +-------+------------+ | | > | SignedArithmetic | +-+-------+-----------+ > | (unary -) | | BinaryInteger | > +------+-------------+ |(words,%,bitwise,...)| > ^ ++---+-----+----------+ > | +-----------^ ^ ^---------------+ > | | | | > +------+---------++ +---------+---------------+ +--+----------------+ > | SignedInteger | | FixedWidthInteger | | UnsignedInteger | > | | |(endianness,overflow,...)| | | > +---------------+-+ +-+--------------------+--+ +-+-----------------+ > ^ ^ ^ ^ > | | | | > | | | | > ++--------+-+ +-+-------+-+ > |Int family |-+ |UInt family|-+ > +-----------+ | +-----------+ | > +-----------+ +-----------+ > > There are several benefits provided by this model over the old one: > > • It allows mixing integer types in generic functions. > > The possibility to initialize instances of any concrete integer type with > values of any other concrete integer type enables writing functions that > operate on more than one type conforming to BinaryInteger, such as > heterogeneous comparisons or bit shifts, described later. > > • It removes the overload resolution overhead. > > Arithmetic and bitwise operations can now be defined as generic operators > on protocols. This approach significantly reduces the number of overloads > for those operations, which used to be defined for every single concrete > integer type. > > • It enables protocol sharing between integer and floating point types. > > Note the exclusion of the % operation from Arithmetic. Its behavior for > floating point numbers is sufficiently different from the one for integers > that using it in generic context would lead to confusion. The FloatingPoint > protocol introduced by SE-0067 should now refine SignedArithmetic. > > • It makes future extensions possible. > > The proposed model eliminates the 'largest integer type' concept > previously used to interoperate between integer types (see toIntMax in the > current model) and instead provides access to machine words. It also > introduces thedoubleWidthMultiply, doubleWidthDivide, and > quotientAndRemainder methods. Together these changes can be used to provide > an efficient implementation of bignums that would be hard to achieve > otherwise. > > The implementation of proposed model in the standard library is available > in the new-integer-protocols branch. > > A note on bit shifts > > This proposal introduces the concepts of smart shifts and masking shifts. > > The semantics of shift operations are often undefined in under- or > over-shift cases. Smart shifts, implemented by >> and <<, are designed to > address this problem and always behave in a well defined way, as shown in > the examples below: > > • x << -2 is equivalent to x >> 2 > > • (1 as UInt8) >> 42) will evaluate to 0 > > • (-128 as Int8) >> 42) will evaluate to 0xff or -1 > > In most scenarios, the right hand operand is a literal constant, and > branches for handling under- and over-shift cases can be optimized away. > For other cases, this proposal provides masking shifts, implemented by &>> > and &<<. A masking shift logically preprocesses the right hand operand by > masking its bits to produce a value in the range 0...(x-1) where x is the > number of bits in the left hand operand. On most architectures this masking > is already performed by the CPU's shift instructions and has no cost. Both > kinds of shift avoid undefined behavior and produce uniform semantics > across architectures. > > Detailed design > > What's new since SE-0104 > > • SE-0091 removed the necessity to dispatch generic operators through > special methods. > > All operators are now declared by protocols as static funcs. > > • Standard Library no longer provides + and - operators for Strideable > types. > > They were problematic, as one could have written mixed-type code like let > x: Int64 = 42; x += (1 as Int), which would compile, but shouldn't. > Besides, since the Stride of an unsigned type is signed, Standard Library > had to implement a hack to make code like let x: UInt = 42; x += (1 as Int) > ambiguous. These operators were only necessary because they made advancing > collection indices convenient, which is no longer the case since the > introduction of the new indexing model in Swift 3. > > • Shifts and other bitwise operations were moved from FixedWidthInteger > to BinaryInteger. > > Left shift operation on an unbounded integer should infinitely extend the > number, and never drop set bits when they reach the most significant > position in the underlying representation. > > • BitwiseOperations protocol was deprecated. > > We believe there are no useful entities that support bitwise operations, > but at the same time are not binary integers. > > • minimumSignedRepresentationBitWidth property was removed. > > • trailingZeros property was added to the BinaryInteger protocol. > > leadingZeros and popcount properties are still defined by the > FixedWidthInteger protocol. > > • Endian-converting initializers and properties were added to the > FixedWidthInteger protocol. > > • Standard library introduces the new type DoubleWidth<T>. > > See this section for more details. > > Protocols > > Arithmetic > > The Arithmetic protocol declares binary arithmetic operators – such as +, > -, and * — and their mutating counterparts. > > It provides a suitable basis for arithmetic on scalars such as integers > and floating point numbers. > > Both mutating and non-mutating operations are declared in the protocol, > however only the mutating ones are required, as default implementations of > the non-mutating ones are provided by a protocol extension. > > The Magnitude associated type is able to hold the absolute value of any > possible value of Self. Concrete types do not have to provide a type alias > for it, as it can be inferred from the magnitude property. This property > can be useful in operations that are simpler to implement in terms of > unsigned values, for example, printing a value of an integer, which is just > printing a '-' character in front of an absolute value. > > Please note that for ordinary work, the magnitude property should not be > preferred to the abs(_) function, whose return value is of the same type as > its argument. > > public protocol Arithmetic : Equatable, ExpressibleByIntegerLiteral > { > > /// Creates a new instance from the given integer, if it can be represented > /// exactly. > /// > /// If the value passed as `source` is not representable exactly, the > result > /// is `nil`. In the following example, the constant `x` is successfully > /// created from a value of `100`, while the attempt to initialize the > /// constant `y` from `1_000` fails because the `Int8` type can represent > /// `127` at maximum: > /// > /// let x = Int8(exactly: 100) > /// // x == Optional(100) > /// let y = Int8(exactly: 1_000) > /// // y == nil > /// > /// - Parameter source: A floating-point value to convert to an integer. > init?<T : BinaryInteger>(exactly source > : T) > > > /// A type that can represent the absolute value of any possible value of > the > /// conforming type. > associatedtype Magnitude : Equatable, ExpressibleByIntegerLiteral > > > > /// The magnitude of this value. > /// > /// For any numeric value `x`, `x.magnitude` is the absolute value of `x`. > /// You can use the `magnitude` property in operations that are simpler to > /// implement in terms of unsigned values, such as printing the value of an > /// integer, which is just printing a '-' character in front of an absolute > /// value. > /// > /// let x = -200 > /// // x.magnitude == 200 > /// > /// The global `abs(_:)` function provides more familiar syntax when you > need > /// to find an absolute value. In addition, because `abs(_:)` always > returns > /// a value of the same type, even in a generic context, using the function > /// instead of the `magnitude` property is encouraged. > /// > /// - SeeAlso: `abs(_:)` > var magnitude: Magnitude { get > } > > > /// Returns the sum of the two given values. > /// > /// The sum of `lhs` and `rhs` must be representable in the same type. In > the > /// following example, the result of `100 + 200` is greater than the > maximum > /// representable `Int8` value: > /// > /// let x: Int8 = 10 + 21 > /// // x == 31 > /// let y: Int8 = 100 + 121 > /// // Overflow error > static func +(_ lhs: Self, _ rhs: Self) -> Self > > > > /// Adds the given value to this value in place. > /// > /// For example: > /// > /// var x = 15 > /// y += 7 > /// // y == 22 > static func +=(_ lhs: inout Self, rhs: Self > ) > > > /// Returns the difference of the two given values. > /// > /// The difference of `lhs` and `rhs` must be representable in the same > type. > /// In the following example, the result of `10 - 21` is less than zero, > the > /// minimum representable `UInt` value: > /// > /// let x: UInt = 21 - 10 > /// // x == 11 > /// let y: UInt = 10 - 21 > /// // Overflow error > static func -(_ lhs: Self, _ rhs: Self) -> Self > > > > /// Subtracts the given value from this value in place. > /// > /// For example: > /// > /// var x = 15 > /// y -= 7 > /// // y == 8 > static func -=(_ lhs: inout Self, rhs: Self > ) > > > /// Returns the product of the two given values. > /// > /// The product of `lhs` and `rhs` must be representable in the same type. > In > /// the following example, the result of `10 * 50` is greater than the > /// maximum representable `Int8` value. > /// > /// let x: Int8 = 10 * 5 > /// // x == 50 > /// let y: Int8 = 10 * 50 > /// // Overflow error > static func *(_ lhs: Self, _ rhs: Self) -> Self > > > > /// Multiples this value by the given value in place. > /// > /// For example: > /// > /// var x = 15 > /// y *= 7 > /// // y == 105 > static func *=(_ lhs: inout Self, rhs: Self > ) > > > /// Returns the quotient of dividing the first value by the second. > /// > /// For integer types, any remainder of the division is discarded. > /// > /// let x = 21 / 5 > /// // x == 4 > static func /(_ lhs: Self, _ rhs: Self) -> Self > > > > /// Divides this value by the given value in place. > /// > /// For example: > /// > /// var x = 15 > /// y /= 7 > /// // y == 2 > static func /=(_ lhs: inout Self, rhs: Self > ) > } > > > extension Arithmetic > { > > public init() { self = 0 > } > > > public static prefix func + (x: Self) -> Self > { > > return > x > } > } > > SignedArithmetic > > The SignedArithmetic protocol is for numbers that can be negated. > > public protocol SignedArithmetic : Arithmetic > { > > /// Returns the additive inverse of this value. > /// > /// let x = 21 > /// let y = -x > /// // y == -21 > /// > /// - Returns: The additive inverse of this value. > /// > /// - SeeAlso: `negate()` > static prefix func - (_ operand: Self) -> Self > > > > /// Replaces this value with its additive inverse. > /// > /// The following example uses the `negate()` method to negate the value of > /// an integer `x`: > /// > /// var x = 21 > /// x.negate() > /// // x == -21 > /// > /// - SeeAlso: The unary minus operator (`-`). > mutating func negate > () > } > > > extension SignedArithmetic > { > > public static prefix func - (_ operand: Self) -> Self > { > > var result = > operand > result. > negate > () > > return > result > } > > > public mutating func negate > () { > > self = Self() - self > > } > } > > BinaryInteger > > The BinaryInteger protocol is the basis for all the integer types provided > by the standard library. > > This protocol adds a few new initializers. Two of them allow to create > integers from floating point numbers, others support construction from > instances of any type conforming to BinaryInteger, using different > strategies: > > • Initialize Self with the value, provided that the value is > representable. The precondition should be satisfied by the caller. > > • Extend or truncate the value to fit into Self > > • Clamp the value to the representable range of Self > > BinaryInteger also declares bitwise and shift operators. > > public protocol BinaryInteger : > Comparable, Hashable, Arithmetic, CustomStringConvertible, Strideable > { > > > /// A Boolean value indicating whether this type is a signed integer type. > /// > /// *Signed* integer types can represent both positive and negative values. > /// *Unsigned* integer types can represent only nonnegative values. > static var isSigned: Bool { get > } > > > /// Creates an integer from the given floating-point value, if it can be > /// represented exactly. > /// > /// If the value passed as `source` is not representable exactly, the > result > /// is `nil`. In the following example, the constant `x` is successfully > /// created from a value of `21.0`, while the attempt to initialize the > /// constant `y` from `21.5` fails: > /// > /// let x = Int(exactly: 21.0) > /// // x == Optional(21) > /// let y = Int(exactly: 21.5) > /// // y == nil > /// > /// - Parameter source: A floating-point value to convert to an integer. > init?<T : FloatingPoint>(exactly source > : T) > > > /// Creates an integer from the given floating-point value, truncating any > /// fractional part. > /// > /// Truncating the fractional part of `source` is equivalent to rounding > /// toward zero. > /// > /// let x = Int(21.5) > /// // x == 21 > /// let y = Int(-21.5) > /// // y == -21 > /// > /// If `source` is outside the bounds of this type after truncation, a > /// runtime error may occur. > /// > /// let z = UInt(-21.5) > /// // Error: ...the result would be less than UInt.min > /// > /// - Parameter source: A floating-point value to convert to an integer. > /// `source` must be representable in this type after truncation. > init<T : FloatingPoint>(_ source > : T) > > > /// Creates an new instance from the given integer. > /// > /// If the value passed as `source` is not representable in this type, a > /// runtime error may occur. > /// > /// let x = -500 as Int > /// let y = Int32(x) > /// // y == -500 > /// > /// // -500 is not representable as a 'UInt32' instance > /// let z = UInt32(x) > /// // Error > /// > /// - Parameter source: An integer to convert. `source` must be > representable > /// in this type. > init<T : BinaryInteger>(_ source > : T) > > > /// Creates a new instance from the bit pattern of the given instance by > /// sign-extending or truncating to fit this type. > /// > /// When the bit width of `T` (the type of `source`) is equal to or greater > /// than this type's bit width, the result is the truncated > /// least-significant bits of `source`. For example, when converting a > /// 16-bit value to an 8-bit type, only the lower 8 bits of `source` are > /// used. > /// > /// let p: Int16 = -500 > /// // 'p' has a binary representation of 11111110_00001100 > /// let q = Int8(extendingOrTruncating: p) > /// // q == 12 > /// // 'q' has a binary representation of 00001100 > /// > /// When the bit width of `T` is less than this type's bit width, the > result > /// is *sign-extended* to fill the remaining bits. That is, if `source` is > /// negative, the result is padded with ones; otherwise, the result is > /// padded with zeros. > /// > /// let u: Int8 = 21 > /// // 'u' has a binary representation of 00010101 > /// let v = Int16(extendingOrTruncating: u) > /// // v == 21 > /// // 'v' has a binary representation of 00000000_00010101 > /// > /// let w: Int8 = -21 > /// // 'w' has a binary representation of 11101011 > /// let x = Int16(extendingOrTruncating: w) > /// // x == -21 > /// // 'x' has a binary representation of 11111111_11101011 > /// let y = UInt16(extendingOrTruncating: w) > /// // y == 65515 > /// // 'y' has a binary representation of 11111111_11101011 > /// > /// - Parameter source: An integer to convert to this type. > init<T : BinaryInteger>(extendingOrTruncating source > : T) > > > /// Creates a new instance with the representable value that's closest to > the > /// given integer. > /// > /// If the value passed as `source` is greater than the maximum > representable > /// value in this type, the result is the type's `max` value. If `source` > is > /// less than the smallest representable value in this type, the result is > /// the type's `min` value. > /// > /// In this example, `x` is initialized as an `Int8` instance by clamping > /// `500` to the range `-128...127`, and `y` is initialized as a `UInt` > /// instance by clamping `-500` to the range `0...UInt.max`. > /// > /// let x = Int8(clamping: 500) > /// // x == 127 > /// // x == Int8.max > /// > /// let y = UInt(clamping: -500) > /// // y == 0 > /// > /// - Parameter source: An integer to convert to this type. > init<T : BinaryInteger>(clamping source > : T) > > > /// Returns the n-th word, counting from the least significant to most > /// significant, of this value's binary representation. > /// > /// The `word(at:)` method returns negative values in two's complement > /// representation, regardless of a type's underlying implementation. If > `n` > /// is greater than the number of words in this value's current > /// representation, the result is `0` for positive numbers and `~0` for > /// negative numbers. > /// > /// - Parameter n: The word to return, counting from the least significant > to > /// most significant. `n` must be greater than or equal to zero. > /// - Returns: An word-sized, unsigned integer with the bit pattern of the > /// n-th word of this value. > func word(at n: Int) -> UInt > > > > /// The number of bits in the current binary representation of this value. > /// > /// This property is a constant for instances of fixed-width integer > /// types. > var bitWidth : Int { get > } > > > /// The number of trailing zeros in this value's binary representation. > /// > /// For example, in a fixed-width integer type with a `bitWidth` value of > 8, > /// the number -8 has three trailing zeros. > /// > /// let x = Int8(bitPattern: 0b1111_1000) > /// // x == -8 > /// // x.trailingZeros == 3 > var trailingZeros: Int { get > } > > > /// Returns the remainder of dividing the first value by the second. > /// > /// The result has the same sign as `lhs` and is less than `rhs.magnitude`. > /// > /// let x = 22 % 5 > /// // x == 2 > /// let y = 22 % -5 > /// // y == 2 > /// let z = -22 % -5 > /// // z == -2 > /// > /// - Parameters: > /// - lhs: The value to divide. > /// - rhs: The value to divide `lhs` by. `rhs` must not be zero. > static func %(_ lhs: Self, _ rhs: Self) -> Self > > > > /// Replaces this value with the remainder of itself divided by the given > /// value. For example: > /// > /// var x = 15 > /// x %= 7 > /// // x == 1 > /// > /// - Parameter rhs: The value to divide this value by. `rhs` must not be > /// zero. > /// > /// - SeeAlso: `remainder(dividingBy:)` > static func %=(_ lhs: inout Self, _ rhs: Self > ) > > > /// Returns the inverse of the bits set in the argument. > /// > /// The bitwise NOT operator (`~`) is a prefix operator that returns a > value > /// in which all the bits of its argument are flipped: Bits that are `1` in > /// the argument are `0` in the result, and bits that are `0` in the > argument > /// are `1` in the result. This is equivalent to the inverse of a set. For > /// example: > /// > /// let x: UInt8 = 5 // 0b00000101 > /// let notX = ~x // 0b11111010 > /// > /// Performing a bitwise NOT operation on 0 returns a value with every bit > /// set to `1`. > /// > /// let allOnes = ~UInt8.min // 0b11111111 > /// > /// - Complexity: O(1). > static prefix func ~ (_ x: Self) -> Self > > > > /// Returns the result of performing a bitwise AND operation on this value > /// and the given value. > /// > /// A bitwise AND operation results in a value that has each bit set to `1` > /// where *both* of its arguments have that bit set to `1`. For example: > /// > /// let x: UInt8 = 5 // 0b00000101 > /// let y: UInt8 = 14 // 0b00001110 > /// let z = x & y // 0b00000100 > static func &(_ lhs: Self, _ rhs: Self) -> Self > > > static func &=(_ lhs: inout Self, _ rhs: Self > ) > > > /// Returns the result of performing a bitwise OR operation on this value > and > /// the given value. > /// > /// A bitwise OR operation results in a value that has each bit set to `1` > /// where *one or both* of its arguments have that bit set to `1`. For > /// example: > /// > /// let x: UInt8 = 5 // 0b00000101 > /// let y: UInt8 = 14 // 0b00001110 > /// let z = x | y // 0b00001111 > static func |(_ lhs: Self, _ rhs: Self) -> Self > > > static func |=(_ lhs: inout Self, _ rhs: Self > ) > > > /// Returns the result of performing a bitwise XOR operation on this value > /// and the given value. > /// > /// A bitwise XOR operation, also known as an exclusive OR operation, > results > /// in a value that has each bit set to `1` where *one or the other but not > /// both* of its arguments had that bit set to `1`. For example: > /// > /// let x: UInt8 = 5 // 0b00000101 > /// let y: UInt8 = 14 // 0b00001110 > /// let z = x ^ y // 0b00001011 > static func ^(_ lhs: Self, _ rhs: Self) -> Self > > > static func ^=(_ lhs: inout Self, _ rhs: Self > ) > > > /// Returns the result of shifting this value's binary representation the > /// specified number of digits to the right. > /// > /// In a *masking shift*, the bit pattern of the value passed as `rhs` is > /// masked to produce a value between zero and the bit width of `lhs`. The > /// shift is performed using this masked value. Masking shifts require more > /// care to use correctly than a traditional bit shift, but are likely to > be > /// more efficient when used with shift amounts that are not compile-time > /// constants. On most architectures, a masking shift compiles down to a > /// single instruction. > /// > /// For example, if you shift an 8-bit, unsigned integer by 2, the shift > /// amount requires no masking. > /// > /// let x: UInt8 = 30 // 0b00011110 > /// let y = x &>> 2 > /// // y == 7 // 0b00000111 > /// > /// However, if you shift it by 11, it first bitmasks `rhs` to `3`, and > then > /// uses that masked value as the number of bits to shift `x`. > /// > /// let z = x &>> 11 > /// // z == 3 // 0b00000011 > /// > /// Relationship to the Right Shift Operator > /// ---------------------------------------- > /// > /// The masking right shift operator handles attempted overshifts and > /// undershifts differently from the right shift operator (`>>`). When the > /// value passed as `rhs` in a masking shift is within the range > /// `0...<bitWidth`, the operation is equivalent to using the right shift > /// operator. > /// > /// let x: UInt8 = 30 // 0b00011110 > /// let y1 = x &>> 2 > /// // y1 == 7 // 0b00000111 > /// let y2 = x >> 2 > /// // y2 == 7 // 0b00000111 > /// > /// The right shift operator does not mask its right-hand-side argument, so > /// passing `11` as `rhs` shifts all the bits of `x` to zero. > /// > /// let z1 = x &>> 11 > /// // z1 == 240 // 0b00000011 > /// let z2 = x >> 11 > /// // z2 == 0 // 0b00000000 > /// > /// - Parameter rhs: The number of bits to shift this value to the right. > If > /// `rhs` is outside the range `0..<bitWidth`, it is masked to produce a > /// value within that range. > /// - Returns: The result of shifting this value by the masked `rhs` to the > /// right. > /// > /// - SeeAlso: `&<<`, `>>` > static func &>>(_ lhs: Self, _ rhs: Self) -> Self > > > static func &>>=(_ lhs: inout Self, _ rhs: Self > ) > > > /// Returns the result of shifting this value's binary representation the > /// specified number of digits to the left. > /// > /// In a *masking shift*, the bit pattern of the value passed as `rhs` is > /// masked to produce a value between zero and the bit width of `lhs`. The > /// shift is performed using this masked value. Masking shifts require more > /// care to use correctly than a traditional bit shift, but are likely to > be > /// more efficient when used with shift amounts that are not compile-time > /// constants. On most architectures, a masking shift compiles down to a > /// single instruction. > /// > /// For example, if you shift an 8-bit, unsigned integer by 2, the shift > /// amount requires no masking. > /// > /// let x: UInt8 = 30 // 0b00011110 > /// let y = x &>> 2 > /// // y == 120 // 0b01111000 > /// > /// However, if you shift it by 11, it first bitmasks `rhs` to `3`, and > then > /// uses that masked value as the number of bits to shift `x`. > /// > /// let z = x &<< 11 > /// // z == 240 // 0b11110000 > /// > /// Relationship to the Left Shift Operator > /// --------------------------------------- > /// > /// The masking left shift operator handles attempted overshifts and > /// undershifts differently from the left shift operator (`<<`). When the > /// value passed as `rhs` in a masking shift is within the range > /// `0...<bitWidth`, the operation is equivalent to using the left shift > /// operator. > /// > /// let x: UInt8 = 30 // 0b00011110 > /// let y1 = x &<< 2 > /// // y1 == 120 // 0b01111000 > /// let y2 = x << 2 > /// // y2 == 120 // 0b01111000 > /// > /// The left shift operator does not mask its right-hand-side argument, so > /// passing `11` as `rhs` shifts all the bits of `x` to zero. > /// > /// let z1 = x &<< 11 > /// // z1 == 240 // 0b11110000 > /// let z2 = x << 11 > /// // z2 == 0 // 0b00000000 > /// > /// - Parameter rhs: The number of bits to shift this value to the left. If > /// `rhs` is outside the range `0..<bitWidth`, it is masked to produce a > /// value within that range. > /// - Returns: The result of shifting this value by the masked `rhs` to the > /// left. > /// > /// - SeeAlso: `&>>`, `<<` > static func &<<(_ lhs: Self, _ rhs: Self) -> Self > > > static func &<<=(_ lhs: inout Self, _ rhs: Self > ) > > > /// Returns the quotient and remainder of this value divided by the given > /// value. > /// > /// Use this method to calculate the quotient and remainder of a division > at > /// the same time. > /// > /// let x = 1_000_000 > /// let (q, r) = x.quotientAndRemainder(dividingBy: 933) > /// // q == 1071 > /// // r == 757 > /// > /// - Parameter rhs: The value to divide this value by. > /// - Returns: A tuple containing the quotient and remainder of this value > /// divided by `rhs`. > func quotientAndRemainder(dividingBy rhs: Self > ) > > -> (quotient: Self, remainder: Self > ) > > > /// Returns `-1` if this value is negative and `1` if it's positive; > /// otherwise, `0`. > /// > /// - Returns: The sign of this number, expressed as an integer of the same > /// type. > func signum() -> Self > > } > > FixedWidthInteger > > The FixedWidthInteger protocol adds the notion of endianness as well as > static properties for type bounds and bit width. > > The WithOverflow family of methods is used in default implementations of > mutating arithmetic methods (see the Arithmetic protocol). Having these > methods allows the library to provide both bounds-checked and masking > implementations of arithmetic operations, without duplicating code. > > The doubleWidthMultiply and doubleWidthDivide methods are necessary > building blocks to implement support for integer types of a greater width > such as arbitrary-precision integers. > > public protocol FixedWidthInteger : BinaryInteger > { > > /// The number of bits used for the underlying binary representation of > /// values of this type. > /// > /// An unsigned, fixed-width integer type can represent values from 0 > through > /// `(2 ** bitWidth) - 1`, where `**` is exponentiation. A signed, > /// fixed-width integer type can represent values from > /// `-(2 ** bitWidth - 1)` through `(2 ** bitWidth - 1) - 1`. For example, > /// the `Int8` type has a `bitWidth` value of 8 and can store any integer > in > /// the range `-128...127`. > static var bitWidth : Int { get > } > > > /// The maximum representable integer in this type. > /// > /// For unsigned integer types, this value is `(2 ** bitWidth) - 1`, where > /// `**` is exponentiation. For signed integer types, this value is > /// `(2 ** bitWidth - 1) - 1`. > static var max: Self { get > } > > > /// The minimum representable value. > /// > /// For unsigned integer types, this value is always `0`. For signed > integer > /// types, this value is `-(2 ** bitWidth - 1)`, where `**` is > /// exponentiation. > static var min: Self { get > } > > > /// Returns the sum of this value and the given value along with a flag > /// indicating whether overflow occurred in the operation. > /// > /// - Parameter other: The value to add to this value. > /// - Returns: A tuple containing the result of the addition along with a > /// flag indicating whether overflow occurred. If the `overflow` > component > /// is `.none`, the `partialValue` component contains the entire sum. If > /// the `overflow` component is `.overflow`, an overflow occurred and the > /// `partialValue` component contains the truncated sum of this value and > /// `other`. > /// > /// - SeeAlso: `+` > func addingWithOverflow(_ other: Self > ) > > -> (partialValue: Self, overflow > : ArithmeticOverflow) > > > /// Returns the difference of this value and the given value along with a > /// flag indicating whether overflow occurred in the operation. > /// > /// - Parameter other: The value to subtract from this value. > /// - Returns: A tuple containing the result of the subtraction along with > a > /// flag indicating whether overflow occurred. If the `overflow` > component > /// is `.none`, the `partialValue` component contains the entire > /// difference. If the `overflow` component is `.overflow`, an overflow > /// occurred and the `partialValue` component contains the truncated > /// result of `other` subtracted from this value. > /// > /// - SeeAlso: `-` > func subtractingWithOverflow(_ other: Self > ) > > -> (partialValue: Self, overflow > : ArithmeticOverflow) > > > /// Returns the product of this value and the given value along with a flag > /// indicating whether overflow occurred in the operation. > /// > /// - Parameter other: The value to multiply by this value. > /// - Returns: A tuple containing the result of the multiplication along > with > /// a flag indicating whether overflow occurred. If the `overflow` > /// component is `.none`, the `partialValue` component contains the > entire > /// product. If the `overflow` component is `.overflow`, an overflow > /// occurred and the `partialValue` component contains the truncated > /// product of this value and `other`. > /// > /// - SeeAlso: `*`, `doubleWidthMultiply(_:_:)` > func multipliedWithOverflow(by other: Self > ) > > -> (partialValue: Self, overflow > : ArithmeticOverflow) > > > /// Returns the quotient of dividing this value by the given value along > with > /// a flag indicating whether overflow occurred in the operation. > /// > /// For a value `x`, if zero is passed as `other`, the result is > /// `(x, .overflow)`. > /// > /// - Parameter other: The value to divide this value by. > /// - Returns: A tuple containing the result of the division along with a > /// flag indicating whether overflow occurred. If the `overflow` > component > /// is `.none`, the `partialValue` component contains the entire > quotient. > /// If the `overflow` component is `.overflow`, an overflow occurred and > /// the `partialValue` component contains the truncated quotient. > /// > /// - SeeAlso: `/`, `doubleWidthDivide(_:_:)` > func dividedWithOverflow(by other: Self > ) > > -> (partialValue: Self, overflow > : ArithmeticOverflow) > > > /// Returns a tuple containing the high and low parts of the result of > /// multiplying its arguments. > /// > /// Use this method to calculate the full result of a product that would > /// otherwise overflow. Unlike traditional truncating multiplication, the > /// `doubleWidthMultiply(_:_:)` method returns both the `high` and `low` > /// parts of the product of `lhs` and `rhs`. The following example uses > this > /// method to multiply two `UInt8` values that normally overflow when > /// multiplied: > /// > /// let x: UInt8 = 100 > /// let y: UInt8 = 20 > /// let result = UInt8.doubleWidthMultiply(100, 20) > /// // result.high == 0b00000111 > /// // result.low == 0b11010000 > /// > /// The product of `x` and `y` is 2000, which is too large to represent in > a > /// `UInt8` instance. The `high` and `low` components of the `result` tuple > /// represent 2000 when concatenated to form a double-width integer; that > /// is, using `result.high` as the high byte and `result.low` as the low > byte > /// of a `UInt16` instance. > /// > /// let z = UInt16(result.high) << 8 | UInt16(result.low) > /// // z == 2000 > /// > /// - Parameters: > /// - lhs: A value to multiply. > /// - rhs: Another value to multiply. > /// - Returns: A tuple containing the high and low parts of the result of > /// multiplying `lhs` and `rhs`. > /// > /// - SeeAlso: `multipliedWithOverflow(by:)` > static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self > ) > > -> (high: Self, low > : Magnitude) > > > /// Returns a tuple containing the quotient and remainder of dividing the > /// first argument by the second. > /// > /// The resulting quotient must be representable within the bounds of the > /// type. If the quotient of dividing `lhs` by `rhs` is too large to > /// represent in the type, a runtime error may occur. > /// > /// - Parameters: > /// - lhs: A tuple containing the high and low parts of a double-width > /// integer. The `high` component of the tuple carries the sign, if the > /// type is signed. > /// - rhs: The integer to divide into `lhs`. > /// - Returns: A tuple containing the quotient and remainder of `lhs` > divided > /// by `rhs`. > static func doubleWidthDivide > ( > > _ lhs: (high: Self, low: Magnitude), _ rhs: Self > ) > > -> (quotient: Self, remainder: Self > ) > > > /// The number of bits equal to 1 in this value's binary representation. > /// > /// For example, in a fixed-width integer type with a `bitWidth` value of > 8, > /// the number 31 has five bits equal to 1. > /// > /// let x: Int8 = 0b0001_1111 > /// // x == 31 > /// // x.popcount == 5 > var popcount: Int { get > } > > > /// The number of leading zeros in this value's binary representation. > /// > /// For example, in a fixed-width integer type with a `bitWidth` value of > 8, > /// the number 31 has three leading zeros. > /// > /// let x: Int8 = 0b0001_1111 > /// // x == 31 > /// // x.leadingZeros == 3 > /// - SeeAlso: `BinaryInteger.trailingZeros` > var leadingZeros: Int { get > } > > > /// Creates an integer from its big-endian representation, changing the > /// byte order if necessary. > init(bigEndian value: Self > ) > > > /// Creates an integer from its little-endian representation, changing the > /// byte order if necessary. > init(littleEndian value: Self > ) > > > /// The big-endian representation of this integer. > /// > /// If necessary, the byte order of this value is reversed from the typical > /// byte order of this integer type. On a big-endian platform, for any > /// integer `x`, `x == x.bigEndian`. > /// > /// - SeeAlso: `littleEndian` > var bigEndian: Self { get > } > > > /// The little-endian representation of this integer. > /// > /// If necessary, the byte order of this value is reversed from the typical > /// byte order of this integer type. On a little-endian platform, for any > /// integer `x`, `x == x.littleEndian`. > /// > /// - SeeAlso: `bigEndian` > var littleEndian: Self { get > } > > > /// A representation of this integer with the byte order swapped. > var byteSwapped: Self { get > } > } > > Auxiliary protocols > > public protocol UnsignedInteger : BinaryInteger > { > > associatedtype Magnitude : BinaryInteger > > } > > public protocol SignedInteger : BinaryInteger, SignedArithmetic > { > > associatedtype Magnitude : BinaryInteger > > } > > DoubleWidth > > The DoubleWidth<T> type allows to create wider fixed-width integer types > from the ones available in the standard library. > > Standard library currently provides fixed-width integer types of up to 64 > bits. A value of DoubleWidth<Int64> will double the range of the underlying > type and implement all the FixedWidthInteger requirements. Please note > though that the implementation will not necessarily be the most efficient > one, so it would not be a good idea to use DoubleWidth<Int32>instead of a > built-in Int64. > > Extra operators > > In addition to the operators described in the protocols section, we also > provide a few extensions that are not protocol requirements: > > Heterogeneous shifts > > extension BinaryInteger > { > > // Masking shifts > static func &>> <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Self > > > static func &>>= <Other : BinaryInteger>(lhs: inout Self, rhs > : Other) > > static func &<< <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Self > > > static func &<<= <Other : BinaryInteger>(lhs: inout Self, rhs > : Other) > > > // 'Smart' shifts > static func >> <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Self > > > static func >>= <Other : BinaryInteger>(lhs: inout Self, rhs > : Other) > > static func << <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Self > > > static func <<= <Other : BinaryInteger>(lhs: inout Self, rhs > : Other) > } > > Heterogeneous equality and comparison > > extension BinaryInteger > { > > // Equality > static func == <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Bool > > > static func != <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Bool > > > > // Comparison > static func < <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Bool > > > static func <= <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Bool > > > static func > <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Bool > > > static func >= <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Bool > > } > > Masking arithmetic > > public func &* <T: FixedWidthInteger>(lhs: T, rhs: T) -> > T > > public func &- <T: FixedWidthInteger>(lhs: T, rhs: T) -> > T > > public func &+ <T: FixedWidthInteger>(lhs: T, rhs: T) -> T > Non-goals > > This proposal: > > • DOES NOT solve the integer promotion problem, which would allow > mixed-type arithmetic. However, we believe that it is an important step in > the right direction. > > • DOES NOT include the implementation of a BigInt type, but allows it to > be implemented in the future. > > Source compatibility > > The proposed change is designed to be as non-breaking as possible, and it > has been proven that it does not break code on concrete integer types. > However, there are still a few API breaking changes in the realm of generic > code: > > • Integer protocols in Swift up to and including version 3 were not > particularly useful for generic programming, but were rather a means of > sharing implementation between conforming types. Therefore we believe the > amount of code that relied on these protocols is relatively small. The > breakage can be further reduced by introducing proper aliases for the > removed protocols with deprecation warnings. > > • Deprecation of the BitwiseOperations protocol. We find it hard to > imagine a type that conforms to this protocol, but is not a binary integer > type. > > • Addition of 'smart' shifts will change the behavior of existing code. > It will still compile, but will be potentially less performant due to extra > logic involved. In a case, where this becomes a problem, newly introduced > masking shift operators can be used instead. Unfortunately, performance > characteristics of the code cannot be statically checked, and thus > migration cannot be provided. > > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution > > > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution > > > -- > -Dave > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution > > > > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution > >
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution