Skip to content

Instantly share code, notes, and snippets.

@moiseev

moiseev/newer-integers.md

Created January 13, 2017 20:43
Show Gist options
  • Save moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c to your computer and use it in GitHub Desktop.
Save moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c to your computer and use it in GitHub Desktop.
Download ZIP
Protocol-oriented integers (take 2)
Raw
newer-integers.md

Protocol-oriented integers (take 2)

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 the doubleWidthMultiply, 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment