Strange behavior with << operator

3

When dealing with the C# shift operators, I encountered a unexpected behavior of the shift-left operator.
Then I tried this simple function:

for (int i = 5; i >= -10; i--) {
    int s = 0x10 << i;
    Debug.WriteLine(i.ToString().PadLeft(3) + "   " + s.ToString("x8"));
}

With this result:

  5   00000200
  4   00000100
  3   00000080
  2   00000040
  1   00000020
  0   00000010
 -1   00000000     -> 00000008 expected
 -2   00000000     -> 00000004 expected
 -3   00000000     -> 00000002 expected
 -4   00000000     -> 00000001 expected
 -5   80000000
 -6   40000000
 -7   20000000
 -8   10000000
 -9   08000000
-10   04000000

Until today, I expected that the << operator can deal with negative values of the second operand.
MSDN tells nothing about the behavior when using negative values of the second operand. But MSDN says that only the lower 5 bits (0-31) are used by the operator, which should fit for negative values.

I also tried with long values: long s = 0x10L << i;, but with the same result.

So what happens here?

EDIT
As stated in your answers, the negative value representation is not the reason for this.
I got the same wrong result for all cases:

0x10<<-3                    = 0x00000000    (wrong!)
0x10<<(int)(0xfffffffd)     = 0x00000000    (wrong!)
0x10<<(0x0000001d           = 0x00000000    (wrong!)
                   expected = 0x00000002

EDIT #2
One of these two should be true:

1) The shift operator is a real shift-operator, so the results should be:
1a) 0x10 << -3 = 00000002
1b) 0x10 << -6 = 00000000

2) The shift operator is a rotate-operator, so the results should be:
2a) 0x10 << -3 = 00000002 (same as 1a)
2b) 0x10 << -6 = 40000000

But the shown results does not fit either to 1) nor to 2) !!!

c#
bit-shift
asked on Stack Overflow Aug 8, 2013 by joe • edited Aug 8, 2013 by joe

3 Answers

3

Negative numbers are two complemented, so -1 == 0xFFFFFFFF, and 0xFFFFFFFF & 31 == 31, -2 == 0xFFFFFFFE, and 0xFFFFFFFE & 31 == 30 and so on.

-10 == 0xFFFFFFF6, and 0xFFFFFFF6 & 31 == 22, in fact:

(0x10 << 22) == 04000000

Some code to show:

const int num = 0x10;
int maxShift = 31;

for (int i = 5; i >= -10; i--)
{
    int numShifted = num << i;
    uint ui = (uint)i;
    int uiWithMaxShift = (int)(ui & maxShift);
    int numShifted2 = num << uiWithMaxShift;

    Console.WriteLine("{0,3}: {1,8:x} {2,2} {3,8:x} {4,8:x} {5}",
        i,
        ui,
        uiWithMaxShift,
        numShifted,
        numShifted2,
        numShifted == numShifted2);
}

With long it's the same, but now instead of & 31 you have & 63. -1 == 63, -2 == 62 and -10 == 54

Some example code:

const long num = 0x10;
int maxShift = 63;

for (int i = 5; i >= -10; i--)
{
    long numShifted = num << i;
    uint ui = (uint)i;
    int uiWithMaxShift = (int)(ui & maxShift);
    long numShifted2 = num << uiWithMaxShift;

    Console.WriteLine("{0,3}: {1,8:x} {2,2} {3,16:x} {4,16:x} {5}", 
        i, 
        ui, 
        uiWithMaxShift, 
        numShifted, 
        numShifted2, 
        numShifted == numShifted2);
}

Just to be clear:

(int x) << y == (int x) << (int)(((uint)y) & 31)
(long x) << y == (long x) << (int)(((uint)y) & 63)

and not

(int x) << y == (int x) << (Math.Abs(y) & 63)
(long x) << y == (long x) << (Math.Abs(y) & 63)

And what you think "should be" "it would be beautiful if it was" "has to be" ecc is irrelevant. While 1 and 0 are "near" (their binary representation has a "distance" of 1 in number of different bits), 0 and -1 are "far" (their binary representation has a "distance" of 32 or 64 in number of different bits)

You think you should get this:

-1   00000000     -> 00000008 expected
-2   00000000     -> 00000004 expected
-3   00000000     -> 00000002 expected
-4   00000000     -> 00000001 expected

but in truth what you don't see is that you are getting this:

-1   (00000008) 00000000
-2   (00000004) 00000000
-3   (00000002) 00000000
-4   (00000001) 00000000
-5   (00000000) 80000000 <-- To show that "symmetry" and "order" still exist
-6   (00000000) 40000000 <-- To show that "symmetry" and "order" still exist

where the part in (...) is the part that is to the "left" of the int and that doesn't exist.

answered on Stack Overflow Aug 8, 2013 by xanatos • edited Aug 9, 2013 by xanatos
3

It has to do with the representation of negative numbers. -1 corresponds to all-ones, so its five least significant bits sum to 31 and left-shifting 0x10 by 31 bits gives all zeroes (the high-order bit that is already set is discarded as per the documentation).

Increasingly larger negative numbers correspond to shifting by 30, 29, etc bits. The bit that is already set in 0x10 is in zero-based position 4, so in order for it to not be discarded the shift has to be at most 31 - 4 = 27 bits, which happens when i == -5.

You can easily see what's going on if you try e.g. Console.WriteLine((-1).ToString("x8")):

ffffffff

Update: when first operand is a long you see similar behavior because now six least significant bits are counted from the second operand: 0x10L << -1 shifts left 63 bits, etc.

answered on Stack Overflow Aug 8, 2013 by Jon • edited Aug 8, 2013 by Jon
3

The left shift operator doesn't see a negative second operand as a right shift. It will just use the lower five bits of the value and make a left shift using that.

The lower five bits of the value -1 (0xFFFFFFFF) will be 31 (0x0000001F), so the first operand 0x10 is shifted to the left 31 steps leaving just the least significant bit in the most significant bit of the result.

In other words, 0x10 << -1 is the same as 0x10 << 31 which will be 0x800000000, but the result is just 32 bits so it will be truncated to 0x00000000.

When you are using a long value, the six least significant bits are used of the second operand. The value -1 becomes 63, and the bits are still shifted out outside the range of the long.

answered on Stack Overflow Aug 8, 2013 by Guffa • edited Aug 8, 2013 by Guffa

User contributions licensed under CC BY-SA 3.0