BigInteger unsigned right shift operation is poorly designed and exposes implementation details

[LEI-Hongfaan]

Description

I found a problem with the BigInteger unsigned right shift operation (>>>) when the BigInteger is negative.

BigInteger represents an infinite-precision signed binary integer in two's complement form, but it does not have a predefined bit length. Therefore, it should not be treated as a fixed-length integer and subjected to unsigned right shift with some arbitrary or randomly chosen bit length.

Unsigned right shift can be seen as performing a signed right shift (>>) after masking the bits with ((1 << N) - 1). The current implementation incorrectly uses the total number of bits in the minimum number of UInt32 units needed to store the BigInteger as the fixed length N, which is inappropriate because it is unnatural and exposes implementation details. (Note that we may consider upgrading BigInteger to use UInt64 units instead.)

We observe that the larger N is, the more bits are preserved, so for BigInteger, the limiting case is that all bits are preserved, which means that the natural definition of unsigned right shift in infinite precision is the same as signed right shift, because the masking operation does not change any bits. (Although BigInteger has a GetBitLength() value, using it (or its variant) as the fixed length for unsigned right shift is also not very natural.)

Reproduction Steps

.

Expected behavior

The BigInteger unsigned right shift operation should behave exactly the same as the signed right shift operation, regardless of the internal representation of the BigInteger.

Actual behavior

The BigInteger unsigned right shift operation is based on the internal representation of the BigInteger, and produces unexpected results when the BigInteger is negative.

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

[ghost]

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

I found a problem with the BigInteger unsigned right shift operation (>>>) when the BigInteger is negative.

BigInteger represents an infinite-precision signed binary integer in two's complement form, but it does not have a predefined bit length. Therefore, it should not be treated as a fixed-length integer and subjected to unsigned right shift with some arbitrary or randomly chosen bit length.

Unsigned right shift can be seen as performing a signed right shift (>>) after masking the bits with ((1 << N) - 1). The current implementation incorrectly uses the total number of bits in the minimum number of UInt32 units needed to store the BigInteger as the fixed length N, which is inappropriate because it is unnatural and exposes implementation details. (Note that we may consider upgrading BigInteger to use UInt64 units instead.)

We observe that the larger N is, the more bits are preserved, so for BigInteger, the limiting case is that all bits are preserved, which means that the natural definition of unsigned right shift in infinite precision is the same as signed right shift, because the masking operation does not change any bits. (Although BigInteger has a GetBitLength() value, using it (or its variant) as the fixed length for unsigned right shift is also not very natural.)

Reproduction Steps

.

Expected behavior

The BigInteger unsigned right shift operation should behave exactly the same as the signed right shift operation, regardless of the internal representation of the BigInteger.

Actual behavior

The BigInteger unsigned right shift operation is based on the internal representation of the BigInteger, and produces unexpected results when the BigInteger is negative.

Regression?

No response

Known Workarounds

No response

Configuration

No response

Other information

No response

Author:	LEI-Hongfaan
Assignees:	-
Labels:	area-System.Numerics, untriaged
Milestone:	-

[tannergooding]

This is functionally "by design".

There were two options possible, one of which always treated the bit sequence as the shortest possible two's complement representation and thus -1 is 1 while +1 is 01. The other of which is to treat it in terms of the underlying storage unit. The latter was chosen as it was overall more consistent with existing behavior, especially when viewed across all possible types. Types like byte and sbyte (when thinking of the concrete types) similarly upcast to the nearest operating unit (int).

Computer math is not the same as real math, it never has been and is instead a rough approximation. There are many concepts that break down in practice and which require special consideration or handling. One could also, for example, argue that x << n should be equivalent to doing x << 1 n-times, but that isn't true because C# opted to mask to the bitcount instead 20 years ago (many other languages and hardware implementations have opted to do the same, for scalars and/or vectors; others provide support for both masked and unmasked shifting or leave it UB).

It's a bit too late to change this behavior at this point and if you want the other behavior then I'd suggest you workaround it by taking the absolute value and then shifting instead.