Shift operator: the type of the second operand


(Jeremy Pereira) #1

These are the definitions of the right shift operators

  public func >>(lhs: Int8, rhs: Int8) -> Int8

  public func >>(lhs: Int, rhs: Int) -> Int

  public func >>(lhs: UInt, rhs: UInt) -> UInt

  public func >>(lhs: Int64, rhs: Int64) -> Int64

  public func >>(lhs: UInt64, rhs: UInt64) -> UInt64

  public func >>(lhs: UInt8, rhs: UInt8) -> UInt8

  public func >>(lhs: UInt16, rhs: UInt16) -> UInt16

  public func >>(lhs: Int16, rhs: Int16) -> Int16

  public func >>(lhs: Int32, rhs: Int32) -> Int32

  public func >>(lhs: UInt32, rhs: UInt32) -> UInt32

Note that both left and right hand side are of the same type. In my opinion, rhs, which represents the number of bits to shift, should always be an Int e.g.

  public func >>(lhs: UInt64, rhs: Int) -> UInt64

The two operands are fundamentally different, the left hand one is conceptually an array of bits and the right hand one is conceptually a count.

The current definitions mean that I almost always have to do a cast on the right operand with shift operations. e.g. the following snippet that converts a UInt64 into an array of boolean values.

    let aNumber: UInt64 = 0x123456
    var numberAsBits: [Bool] = [];
    for i in 0 ..< 64
    {
        numberAsBits.append((aNumber >> i) & 1 != 0); // Error because i needs to be cast to a UInt64
    }

I would like additional versions of the shift operator where rhs is an Int please.

Needless to say, the same applies to the left shift operators.


(Greg Titus) #2

+1. In fact, I would go even farther than asking for an additional version that uses Int on the rhs, I think all of the existing definitions are arguably wrong and they should all just be changed to use Int. I just took a brief scan of all uses of >> and << in the stdlib: most use constants on the rhs, and so would be unaffected. It looks like all the rest either use Int on the lhs or require explicit casting or calling numericCast() to get the rhs to match.

  - Greg

···

On Dec 18, 2015, at 3:55 AM, Jeremy Pereira via swift-evolution <swift-evolution@swift.org> wrote:

These are the definitions of the right shift operators

  public func >>(lhs: Int8, rhs: Int8) -> Int8

  public func >>(lhs: Int, rhs: Int) -> Int

  public func >>(lhs: UInt, rhs: UInt) -> UInt

  public func >>(lhs: Int64, rhs: Int64) -> Int64

  public func >>(lhs: UInt64, rhs: UInt64) -> UInt64

  public func >>(lhs: UInt8, rhs: UInt8) -> UInt8

  public func >>(lhs: UInt16, rhs: UInt16) -> UInt16

  public func >>(lhs: Int16, rhs: Int16) -> Int16

  public func >>(lhs: Int32, rhs: Int32) -> Int32

  public func >>(lhs: UInt32, rhs: UInt32) -> UInt32

Note that both left and right hand side are of the same type. In my opinion, rhs, which represents the number of bits to shift, should always be an Int e.g.

  public func >>(lhs: UInt64, rhs: Int) -> UInt64

The two operands are fundamentally different, the left hand one is conceptually an array of bits and the right hand one is conceptually a count.

The current definitions mean that I almost always have to do a cast on the right operand with shift operations. e.g. the following snippet that converts a UInt64 into an array of boolean values.

   let aNumber: UInt64 = 0x123456
   var numberAsBits: [Bool] = [];
   for i in 0 ..< 64
   {
       numberAsBits.append((aNumber >> i) & 1 != 0); // Error because i needs to be cast to a UInt64
   }

I would like additional versions of the shift operator where rhs is an Int please.

Needless to say, the same applies to the left shift operators.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Félix Cloutier) #3

I agree with you. The proposal probably needs to be considered before the ABI freeze.

···

Le 18 déc. 2015 à 06:55:38, Jeremy Pereira via swift-evolution <swift-evolution@swift.org> a écrit :

These are the definitions of the right shift operators

  public func >>(lhs: Int8, rhs: Int8) -> Int8

  public func >>(lhs: Int, rhs: Int) -> Int

  public func >>(lhs: UInt, rhs: UInt) -> UInt

  public func >>(lhs: Int64, rhs: Int64) -> Int64

  public func >>(lhs: UInt64, rhs: UInt64) -> UInt64

  public func >>(lhs: UInt8, rhs: UInt8) -> UInt8

  public func >>(lhs: UInt16, rhs: UInt16) -> UInt16

  public func >>(lhs: Int16, rhs: Int16) -> Int16

  public func >>(lhs: Int32, rhs: Int32) -> Int32

  public func >>(lhs: UInt32, rhs: UInt32) -> UInt32

Note that both left and right hand side are of the same type. In my opinion, rhs, which represents the number of bits to shift, should always be an Int e.g.

  public func >>(lhs: UInt64, rhs: Int) -> UInt64

The two operands are fundamentally different, the left hand one is conceptually an array of bits and the right hand one is conceptually a count.

The current definitions mean that I almost always have to do a cast on the right operand with shift operations. e.g. the following snippet that converts a UInt64 into an array of boolean values.

   let aNumber: UInt64 = 0x123456
   var numberAsBits: [Bool] = [];
   for i in 0 ..< 64
   {
       numberAsBits.append((aNumber >> i) & 1 != 0); // Error because i needs to be cast to a UInt64
   }

I would like additional versions of the shift operator where rhs is an Int please.

Needless to say, the same applies to the left shift operators.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Andrew Bennett) #4

+1

Something worth considering with this proposal: Should it be IntMax rather
than Int? (or UIntMax, does a negative count make sense?).

Although it's probably never going to be enough if you want to calculate
the next largest known prime number in swift, the last was 2^57885161 − 1.

*Also if it's in scope:*

Left and right shift are the only operators on integers that aren't
generalised by a protocol. Every other operator is somehow part of
IntegerType.

See IntegerArithmeticType, SignedNumberType and BitwiseOperationsType.

It would be nice to create a new protocol for something that can shift. The
new protocol could be:

protocol IntegerBitShiftType {
    var sizeInBits: UIntMax

    @warn_unused_result

    func <<(lhs: Self, rhs: UIntMax) -> Self

    @warn_unused_result

    func >>(lhs: Self, rhs: UIntMax) -> Self
}

If IntegerType conformed to that protocol I don't think there's anything I
want that Int can do and IntegerType can't.

*A related but slightly off-topic gripe:*
Integer protocols in Standard Library define init(_: IntMax) or init(_:
UIntMax), they assume that there isn't a wider type. When trying to make a
new type conform to IntegerType (ie. a BigInt library) this can be an issue.

It also seems to be necessary that things implementing IntegerType must
conform to _MaxBuiltinIntegerType. It's type is much wider than IntMax (64x
for me) and its interface is empty which makes it hard to conform.

I think currently _MaxBuiltinIntegerType is 4096 bits, but it is still much
smaller than what you want from a BigInt type. While I have suggested using
IntMax in this implementation I think that IntMax is inherently flawed in
its usage. However it is the best available at the moment in my opinion.

Something like this may work in a more general case:

protocol IntegerBitShiftType {
    @warn_unused_result

    func << <T: UnsignedIntegerType>(lhs: Self, rhs: T) -> Self

    @warn_unused_result

    func >> <T: UnsignedIntegerType>(lhs: Self, rhs: T) -> Self
}

···

On Sat, Dec 19, 2015 at 3:02 AM, Greg Titus via swift-evolution < swift-evolution@swift.org> wrote:

+1. In fact, I would go even farther than asking for an additional version
that uses Int on the rhs, I think all of the existing definitions are
arguably wrong and they should all just be changed to use Int. I just took
a brief scan of all uses of >> and << in the stdlib: most use constants on
the rhs, and so would be unaffected. It looks like all the rest either use
Int on the lhs or require explicit casting or calling numericCast() to get
the rhs to match.

        - Greg

> On Dec 18, 2015, at 3:55 AM, Jeremy Pereira via swift-evolution < > swift-evolution@swift.org> wrote:
>
> These are the definitions of the right shift operators
>
> public func >>(lhs: Int8, rhs: Int8) -> Int8
>
> public func >>(lhs: Int, rhs: Int) -> Int
>
> public func >>(lhs: UInt, rhs: UInt) -> UInt
>
> public func >>(lhs: Int64, rhs: Int64) -> Int64
>
> public func >>(lhs: UInt64, rhs: UInt64) -> UInt64
>
> public func >>(lhs: UInt8, rhs: UInt8) -> UInt8
>
> public func >>(lhs: UInt16, rhs: UInt16) -> UInt16
>
> public func >>(lhs: Int16, rhs: Int16) -> Int16
>
> public func >>(lhs: Int32, rhs: Int32) -> Int32
>
> public func >>(lhs: UInt32, rhs: UInt32) -> UInt32
>
>
> Note that both left and right hand side are of the same type. In my
opinion, rhs, which represents the number of bits to shift, should always
be an Int e.g.
>
> public func >>(lhs: UInt64, rhs: Int) -> UInt64
>
> The two operands are fundamentally different, the left hand one is
conceptually an array of bits and the right hand one is conceptually a
count.
>
> The current definitions mean that I almost always have to do a cast on
the right operand with shift operations. e.g. the following snippet that
converts a UInt64 into an array of boolean values.
>
> let aNumber: UInt64 = 0x123456
> var numberAsBits: [Bool] = [];
> for i in 0 ..< 64
> {
> numberAsBits.append((aNumber >> i) & 1 != 0); // Error because i
needs to be cast to a UInt64
> }
>
> I would like additional versions of the shift operator where rhs is an
Int please.
>
> Needless to say, the same applies to the left shift operators.
>
> _______________________________________________
> 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


(Jordan Rose) #5

+1 to dropping the existing signatures and providing a consistent right-hand side.

I'm a little concerned about not allowing Int as the shift type. Even though we disallow negative shifts, we generally encourage using 'Int' as the "vocabulary" type for integers, which means any shift by a non-constant amount might require a conversion. I do see that BigInts may be shifted by more than 2^64, however, so hardcoding Int wouldn't be right either.

(We do want to make sure the implementation is efficient when both argument types are a machine-representable integers, though, which may not be possible with all UnsignedIntegerTypes.)

Jordan

···

On Dec 19, 2015, at 5:54 , Andrew Bennett via swift-evolution <swift-evolution@swift.org> wrote:

+1

Something worth considering with this proposal: Should it be IntMax rather than Int? (or UIntMax, does a negative count make sense?).

Although it's probably never going to be enough if you want to calculate the next largest known prime number in swift, the last was 2^57885161 − 1.

Also if it's in scope:

Left and right shift are the only operators on integers that aren't generalised by a protocol. Every other operator is somehow part of IntegerType.

See IntegerArithmeticType, SignedNumberType and BitwiseOperationsType.

It would be nice to create a new protocol for something that can shift. The new protocol could be:
protocol IntegerBitShiftType {
    var sizeInBits: UIntMax

    @warn_unused_result
    func <<(lhs: Self, rhs: UIntMax) -> Self

    @warn_unused_result
    func >>(lhs: Self, rhs: UIntMax) -> Self
}

If IntegerType conformed to that protocol I don't think there's anything I want that Int can do and IntegerType can't.

A related but slightly off-topic gripe:
Integer protocols in Standard Library define init(_: IntMax) or init(_: UIntMax), they assume that there isn't a wider type. When trying to make a new type conform to IntegerType (ie. a BigInt library) this can be an issue.

It also seems to be necessary that things implementing IntegerType must conform to _MaxBuiltinIntegerType. It's type is much wider than IntMax (64x for me) and its interface is empty which makes it hard to conform.

I think currently _MaxBuiltinIntegerType is 4096 bits, but it is still much smaller than what you want from a BigInt type. While I have suggested using IntMax in this implementation I think that IntMax is inherently flawed in its usage. However it is the best available at the moment in my opinion.

Something like this may work in a more general case:

protocol IntegerBitShiftType {
    @warn_unused_result
    func << <T: UnsignedIntegerType>(lhs: Self, rhs: T) -> Self

    @warn_unused_result
    func >> <T: UnsignedIntegerType>(lhs: Self, rhs: T) -> Self
}

On Sat, Dec 19, 2015 at 3:02 AM, Greg Titus via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
+1. In fact, I would go even farther than asking for an additional version that uses Int on the rhs, I think all of the existing definitions are arguably wrong and they should all just be changed to use Int. I just took a brief scan of all uses of >> and << in the stdlib: most use constants on the rhs, and so would be unaffected. It looks like all the rest either use Int on the lhs or require explicit casting or calling numericCast() to get the rhs to match.

        - Greg

> On Dec 18, 2015, at 3:55 AM, Jeremy Pereira via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
> These are the definitions of the right shift operators
>
> public func >>(lhs: Int8, rhs: Int8) -> Int8
>
> public func >>(lhs: Int, rhs: Int) -> Int
>
> public func >>(lhs: UInt, rhs: UInt) -> UInt
>
> public func >>(lhs: Int64, rhs: Int64) -> Int64
>
> public func >>(lhs: UInt64, rhs: UInt64) -> UInt64
>
> public func >>(lhs: UInt8, rhs: UInt8) -> UInt8
>
> public func >>(lhs: UInt16, rhs: UInt16) -> UInt16
>
> public func >>(lhs: Int16, rhs: Int16) -> Int16
>
> public func >>(lhs: Int32, rhs: Int32) -> Int32
>
> public func >>(lhs: UInt32, rhs: UInt32) -> UInt32
>
>
> Note that both left and right hand side are of the same type. In my opinion, rhs, which represents the number of bits to shift, should always be an Int e.g.
>
> public func >>(lhs: UInt64, rhs: Int) -> UInt64
>
> The two operands are fundamentally different, the left hand one is conceptually an array of bits and the right hand one is conceptually a count.
>
> The current definitions mean that I almost always have to do a cast on the right operand with shift operations. e.g. the following snippet that converts a UInt64 into an array of boolean values.
>
> let aNumber: UInt64 = 0x123456
> var numberAsBits: [Bool] = [];
> for i in 0 ..< 64
> {
> numberAsBits.append((aNumber >> i) & 1 != 0); // Error because i needs to be cast to a UInt64
> }
>
> I would like additional versions of the shift operator where rhs is an Int please.
>
> Needless to say, the same applies to the left shift operators.
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto: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 Abrahams) #6

I don't support picking a single RHS type.

Again I'll mention that the prototype <https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L1082> I'm already working on to replace the integer protocols and types already supports any integer type appearing on the RHS of a shift operation, where the LHS is any fixed-width integer type. It also supports negative shifts and overshifts without trapping or causing undefined behavior (as suggested by Steve Canon there's also a new masking shift operator that masks the RHS before shifting, for those who can't afford the branch).

···

On Dec 19, 2015, at 7:43 PM, Jordan Rose via swift-evolution <swift-evolution@swift.org> wrote:

+1 to dropping the existing signatures and providing a consistent right-hand side.

I'm a little concerned about not allowing Int as the shift type. Even though we disallow negative shifts, we generally encourage using 'Int' as the "vocabulary" type for integers, which means any shift by a non-constant amount might require a conversion. I do see that BigInts may be shifted by more than 2^64, however, so hardcoding Int wouldn't be right either.

(We do want to make sure the implementation is efficient when both argument types are a machine-representable integers, though, which may not be possible with all UnsignedIntegerTypes.)

Jordan

On Dec 19, 2015, at 5:54 , Andrew Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

+1

Something worth considering with this proposal: Should it be IntMax rather than Int? (or UIntMax, does a negative count make sense?).

Although it's probably never going to be enough if you want to calculate the next largest known prime number in swift, the last was 2^57885161 − 1.

Also if it's in scope:

Left and right shift are the only operators on integers that aren't generalised by a protocol. Every other operator is somehow part of IntegerType.

See IntegerArithmeticType, SignedNumberType and BitwiseOperationsType.

It would be nice to create a new protocol for something that can shift. The new protocol could be:
protocol IntegerBitShiftType {
    var sizeInBits: UIntMax

    @warn_unused_result
    func <<(lhs: Self, rhs: UIntMax) -> Self

    @warn_unused_result
    func >>(lhs: Self, rhs: UIntMax) -> Self
}

If IntegerType conformed to that protocol I don't think there's anything I want that Int can do and IntegerType can't.

A related but slightly off-topic gripe:
Integer protocols in Standard Library define init(_: IntMax) or init(_: UIntMax), they assume that there isn't a wider type. When trying to make a new type conform to IntegerType (ie. a BigInt library) this can be an issue.

It also seems to be necessary that things implementing IntegerType must conform to _MaxBuiltinIntegerType. It's type is much wider than IntMax (64x for me) and its interface is empty which makes it hard to conform.

I think currently _MaxBuiltinIntegerType is 4096 bits, but it is still much smaller than what you want from a BigInt type. While I have suggested using IntMax in this implementation I think that IntMax is inherently flawed in its usage. However it is the best available at the moment in my opinion.

Something like this may work in a more general case:

protocol IntegerBitShiftType {
    @warn_unused_result
    func << <T: UnsignedIntegerType>(lhs: Self, rhs: T) -> Self

    @warn_unused_result
    func >> <T: UnsignedIntegerType>(lhs: Self, rhs: T) -> Self
}

On Sat, Dec 19, 2015 at 3:02 AM, Greg Titus via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
+1. In fact, I would go even farther than asking for an additional version that uses Int on the rhs, I think all of the existing definitions are arguably wrong and they should all just be changed to use Int. I just took a brief scan of all uses of >> and << in the stdlib: most use constants on the rhs, and so would be unaffected. It looks like all the rest either use Int on the lhs or require explicit casting or calling numericCast() to get the rhs to match.

        - Greg

> On Dec 18, 2015, at 3:55 AM, Jeremy Pereira via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
>
> These are the definitions of the right shift operators
>
> public func >>(lhs: Int8, rhs: Int8) -> Int8
>
> public func >>(lhs: Int, rhs: Int) -> Int
>
> public func >>(lhs: UInt, rhs: UInt) -> UInt
>
> public func >>(lhs: Int64, rhs: Int64) -> Int64
>
> public func >>(lhs: UInt64, rhs: UInt64) -> UInt64
>
> public func >>(lhs: UInt8, rhs: UInt8) -> UInt8
>
> public func >>(lhs: UInt16, rhs: UInt16) -> UInt16
>
> public func >>(lhs: Int16, rhs: Int16) -> Int16
>
> public func >>(lhs: Int32, rhs: Int32) -> Int32
>
> public func >>(lhs: UInt32, rhs: UInt32) -> UInt32
>
>
> Note that both left and right hand side are of the same type. In my opinion, rhs, which represents the number of bits to shift, should always be an Int e.g.
>
> public func >>(lhs: UInt64, rhs: Int) -> UInt64
>
> The two operands are fundamentally different, the left hand one is conceptually an array of bits and the right hand one is conceptually a count.
>
> The current definitions mean that I almost always have to do a cast on the right operand with shift operations. e.g. the following snippet that converts a UInt64 into an array of boolean values.
>
> let aNumber: UInt64 = 0x123456
> var numberAsBits: [Bool] = [];
> for i in 0 ..< 64
> {
> numberAsBits.append((aNumber >> i) & 1 != 0); // Error because i needs to be cast to a UInt64
> }
>
> I would like additional versions of the shift operator where rhs is an Int please.
>
> Needless to say, the same applies to the left shift operators.
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org <mailto:swift-evolution@swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

-Dave


(Chris Lattner) #7

Unless it is somehow sparsely encoded, a bigint with more than 2^64 bits couldn’t be held in memory.

-Chris

···

On Dec 19, 2015, at 7:43 PM, Jordan Rose via swift-evolution <swift-evolution@swift.org> wrote:

+1 to dropping the existing signatures and providing a consistent right-hand side.

I'm a little concerned about not allowing Int as the shift type. Even though we disallow negative shifts, we generally encourage using 'Int' as the "vocabulary" type for integers, which means any shift by a non-constant amount might require a conversion. I do see that BigInts may be shifted by more than 2^64, however, so hardcoding Int wouldn't be right either.


(Dave Abrahams) #8

I don't believe bit shifting should be supported for BigInt anyway. The lossy semantics of bit shifting is pretty closely tied to fixed-width integers.

-Dave

···

On Dec 19, 2015, at 8:02 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 19, 2015, at 7:43 PM, Jordan Rose via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

+1 to dropping the existing signatures and providing a consistent right-hand side.

I'm a little concerned about not allowing Int as the shift type. Even though we disallow negative shifts, we generally encourage using 'Int' as the "vocabulary" type for integers, which means any shift by a non-constant amount might require a conversion. I do see that BigInts may be shifted by more than 2^64, however, so hardcoding Int wouldn't be right either.

Unless it is somehow sparsely encoded, a bigint with more than 2^64 bits couldn’t be held in memory.


(Stephen Canon) #9

Yes, A BigInt type should probably eschew shift operators for this reason. Instead, I would rather have either a sparse representation for powers of two that can be used with the usual multiply / divide, or explicit multiplyByTwoToThe( ) and divideByTwoToThe( ) functions (names to be bikeshedded, obviously).

···

On Dec 19, 2015, at 11:04 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 19, 2015, at 8:02 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 19, 2015, at 7:43 PM, Jordan Rose via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

+1 to dropping the existing signatures and providing a consistent right-hand side.

I'm a little concerned about not allowing Int as the shift type. Even though we disallow negative shifts, we generally encourage using 'Int' as the "vocabulary" type for integers, which means any shift by a non-constant amount might require a conversion. I do see that BigInts may be shifted by more than 2^64, however, so hardcoding Int wouldn't be right either.

Unless it is somehow sparsely encoded, a bigint with more than 2^64 bits couldn’t be held in memory.

I don't believe bit shifting should be supported for BigInt anyway. The lossy semantics of bit shifting is pretty closely tied to fixed-width integers.