0

I'm independently studying bit-shifting by porting some C++ functions to .NET's BigInteger. I noticed that when I shifted BigInteger the void was filled in with ones.

I believe this has to do with the negative number being stored in twos compliment form.

BigInteger num = -126;
compactBitsRepresentation = (uint)(int)(num << 16);

Here is what happened after the shift (most significant bit first)

10000010 will be shifted 16
11111111100000100000000000000000 was shifted 16

Should I always expect a similar bit-shift operation to act this way? Is this consistent with different languages and implementations of "bigNumber" such as OpenSSL?

Tuxdude
  • 47,485
  • 15
  • 109
  • 110
makerofthings7
  • 60,103
  • 53
  • 215
  • 448

3 Answers3

1

From the BigInteger.LeftShift operator docs:

Unlike the bitwise left-shift operation with integer primitives, the LeftShift method preserves the sign of the original BigInteger value.

So .NET guarantees the behavior that you see.

I'm not that familiar with bignum libraries, but the docs for OpenSSL's BIGNUM BN_lshift()` function says:

BN_lshift() shifts a left by n bits and places the result in r ("r=a*2^n"). BN_lshift1() shifts a left by one and places the result in r ("r=2*a").

Since the operation is defined in terms of multiplication by a power of two, if you convert the resulting BIGNUM to a two's complement number (I have no idea how BIGNUM represents numbers internally) then you'll see similar behavior to .NET.

I wouldn't be surprised if other bignum libraries behaved similarly, but you'd really need to check the docs if you want to depend on the behavior. However, since shifting is very similar to multiplication or division by powers of two, you can probably get 'portable' behavior by using an appropriate multiplication or division instead of a shift. Then all you'd need to ensure is that you can get the conversion to a two's complement representation (which is an issue that is really independent of the behavior of the shift operation).

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
Michael Burr
  • 333,147
  • 50
  • 533
  • 760
1

Should I always expect a similar bit-shift operation to act this way?

You should if the number format in question uses two's complement to represent negative numbers (and many do). To form the two's complement of a number, you invert all the bits and add one, so for example:

23 is represented as 00010111
-23 is represented as 11101001 (that is, 11101000 + 1)

Furthermore, when you convert a type to a larger type, the value is usually sign-extended, i.e. the leftmost bit is extended into the extra bits in the larger type. That preserves the sign of the number.

So yes, it's quite common for numeric representations to be "filled" with 1 for numeric values.

Caleb
  • 124,013
  • 19
  • 183
  • 272
0

10000010 is first changed to a bigger width. In this case, 4 bytes:

10000010 --> 11111111 11111111 11111111 10000010

You get 1s on the left since the number is negative.

Now the left shift simply inserts 0s from the right and throw bits from the left:

11111111 11111111 11111111 10000010 << 16 -->
11111111 10000010 00000000 00000000
Shahbaz
  • 46,337
  • 19
  • 116
  • 182
  • 1
    Is it standard C++ behavior? IIRC it's implementation defined, not standard behavior. – Richard J. Ross III Mar 11 '13 at 00:04
  • 1
    It's actually undefined behavior to left shift a negative number in C or C++. – Michael Burr Mar 11 '13 at 01:00
  • Yup, see http://stackoverflow.com/questions/3784996/why-does-left-shift-operation-invoke-undefined-behaviour-when-the-left-side-oper – MSalters Mar 11 '13 at 12:34
  • @RichardJ.RossIII, I didn't know that. I didn't mean to use the phrase as "defined by the standard", but rather that "it's a C++ thing, and has nothing to do with .net or biginteger". Removed it nevertheless. – Shahbaz Mar 11 '13 at 12:42