I notice the BinaryInteger's func word(at n: Int) -> UInt function expects a 2's complement representation. Do you expect that "BigInt" will be implemented with 2's complement? As a nonmutating function, I would think any implementation from a 1's complement big int would result in O(n^2) unless the BigInt were designed with scratch space where it could store the intermediate values of that representation. I only ask because just last week I was designing an arbitrary-width float type in 1's complement, well, really I kept the sign bit in a separate Bool. Of course, I recognize the value of being able to write integer init code from a 2's complement representation, I'm just curious if there's a way to allow this function to be more efficient for alternate representations.
I love that there's a DoubleWidth type, having coded some arbitrary precision arithmetic, that's always a downer going from generic code to having to pick a specific "big enough" result type. I'm glad the % operator got moved. It really did stand out as not part of floating points. Trailing zeros looks like a sensible optimization. I agree with moving the shift operators, I like that you've called out the notion of an infinite shift. I can't say I fully understood the use of the separate mask vs. smart shift operators, but I'll take another read in the next few days and see if I understand why they exist. I know this PR does not address the BitInt implementation, but do you have one? I'm glad to see this moving forward. -Ben Spratling Sent from my iPad > On Jan 14, 2017, at 2:00 AM, Rien via swift-evolution > <[email protected]> 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 >> <[email protected]> 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 >> [email protected] >> https://lists.swift.org/mailman/listinfo/swift-evolution > > > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
