C# binary shift rotates automatically

Question

I searched for methods to do a binary rotating shift in C#, and came across good answers, like https://stackoverflow.com/a/812039/204693 or https://stackoverflow.com/a/35172/204693

I wanted to create a testcase for this scenario, where a non-rotating shift would serve as a negative-test, but then I stumbled upon the fact that this:

public static void Main()
{
    Debug.WriteLine("1<<31 = " + Convert.ToString(1 << 31, 2).PadLeft(32, '0'));
    Debug.WriteLine("1<<32 = " + Convert.ToString(1 << 32, 2).PadLeft(32, '0'));
}

Provides the following output:

1<<31 = 10000000000000000000000000000000
1<<32 = 00000000000000000000000000000001

Now, this seeems strange to me, as there are many answers out there that provide a method to binary shift and rotate with tricks like binary OR etc. But, it seems that the default behaviour of .NET is to rotate.

Has this behaviour changed in a new verison of .NET? I have tried this in Visual Studio 2010 down to .NET 2.0, and it always shows the above behaviour.

Why have people created "clever" solutions to rotating bits, if this is default behaviour? Am I missing something here?

score 8 · Accepted Answer · answered Dec 09 '13 at 10:25

8

It doesn't "rotate" as such; simply - only some of the bits of the operand are considered. Basically, 1 << 32 is identical to 1 << 0.

From MSDN

If the first operand is an int or uint (32-bit quantity), the shift count is given by the low-order five bits of the second operand. That is, the actual shift count is 0 to 31 bits.

If the first operand is a long or ulong (64-bit quantity), the shift count is given by the low-order six bits of the second operand. That is, the actual shift count is 0 to 63 bits.

answered Dec 09 '13 at 10:25

Marc Gravell

1,026,079
266
2,566
2,900

Which of course also means that `(1 << 31) << 4` is *not* "rotated". So you still have to implement your own rotating bitshift. – Luaan Dec 09 '13 at 10:26
In other words: the "real" shift count being used is `(specified shift count)`%`(word length)` – Alex Dec 09 '13 at 10:28
Can you maybe provide an example where I can see that it is not actually rotated and that demonstrates the "low-order" shifting? I'm very interested in seeing this happen (or rather: not happen). – F.P Dec 09 '13 at 10:28
@FlorianPeschka watch what happens when you `<<` or `>>` values outside of the number; they are backfilled with 0s (or 1s on the left for signed negative numbers) – Marc Gravell Dec 09 '13 at 10:31
@FlorianPeschka: I've added an example in a separate answer. – Luaan Dec 09 '13 at 10:32
1

I personally think that the language should throw an exception in this case (at least, in `checked` blocks) – Matthew Watson Dec 09 '13 at 10:37
1

@MatthewWatson personally, I think it should simply *do what it was told* - resulting in either 0 or -1 (for right shifts of negative numbers); if you shifted away all the values: that's your problem. Result being: `>>10`, `>>10`, `>>10` would have the same result as `>>30` – Marc Gravell Dec 09 '13 at 10:59

Luaan · Answer 2 · 2013-12-09T10:34:51.513

An example of how it doesn't rotate the bitshifting if it's not done in one operation:

var a = 1 << 16;
a.ToString("X8").Dump();

a = a << 8;
a.ToString("X8").Dump();

a = a << 8;
a.ToString("X8").Dump();

The last dump will show that a is now in fact zero.

In other words, if you do all the bitshifting in one operation, you're fine and dandy, and you get rotating behaviour (after all, it's a simple modulo 32 on the operand). However, as long as you call the bitshifts more often than just once, you lose parts of the number until you get zero.

Also, you get there faster if you use more than just one bit:

var a = 0xA1A2A3A4;
a.ToString("X8").Dump(); // "A1A2A3A4"

a = a << 8;
a.ToString("X8").Dump(); // "A2A3A400"!

a = a << 8;
a.ToString("X8").Dump(); // "A3A40000"

a = a << 8;
a.ToString("X8").Dump(); // "A4000000"

C# binary shift rotates automatically

2 Answers2