Why in two's complement (-1 >> 1) == -1 and not 0?

Question

Note I think some commenters misunderstand my question that I don't understand integer division and floating point division - More clarification: I expected -1/2 == -1 >> 1 == 0, but in fact -1 >> 1 = -1.

I'm learning two's complement. I understand a special thing about bit shifting in two's complement's context is that right shifting needs to maintain the sign of the bit, such that right shifting a negative number should fill in 1 instead of 0. And left shifting should always fill 0. This is explained in the Wikipedia's article.

According to the article, the motivation behind this is to maintain the equivalency of bit shifting operation and the corresponding multiplication or division by 2. However, a special case I immediately noticed is -1. Under the above mentioned rule, -1>>1 does not equal to -1/2.

My question is how should I understand this? And what precautions should I take when applying bit shifts in optimization of multiplication and division?

Here's a C# (should be equivalent in other languages) code illustrating what I meant:

class Program
{
    static void Main(string[] args)
    {
        foreach (int x in new[] { 0, 1, 2, 3, -1, -2, -3 })
        {
            int a = x >> 1;
            int b = x / 2;
            Console.WriteLine($"Number:{x}, x>>1: {a}, x/2: {b}");
        }
    }
}

This produces the output of:

Number:0, x>>1: 0, x/2: 0
Number:1, x>>1: 0, x/2: 0
Number:2, x>>1: 1, x/2: 1
Number:3, x>>1: 1, x/2: 1
Number:-1, x>>1: -1, x/2: 0
Number:-2, x>>1: -1, x/2: -1
Number:-3, x>>1: -2, x/2: -1

Answer 1

The Wiki article is wrong for c. This statement: These rules preserve the common semantics that left shifts multiply the number by two and right shifts divide the number by two. is not correct for c when looking at odd negative integers.

For integer division c uses round towards zero (or truncation toward zero as it is stated in the standard), i.e. if the real result is 1.5 the integer result will be 1. If the real result is -1.5 the integer result will be -1.

For c the standard doesn't specify what should happen to negative integers when doing a right shift - it is implementation-defined.

If your system uses two's complement right shift doesn't work the same way as division. In general shifting has nothing to do with rounding. However, if you want to look at a two's complement right shift as a division, you got to notice that it rounds towards minus infinity. That is: if the real result is 1.5 the integer result will be 1. If the real result is -1.5 the integer result will be -2.

Conclusion: Rigth shift is not the same as division by 2 for odd negative integers.

Your direct question:

-1 >> 1 is ??

If you consider right shift as a division by 2, the real result would be -0.5 but since it works like round towards minus infinity, the result will be rounded to -1

But as stated - right shift is not a division by 2. You have to look at the bit level.

At bit level it is simply because the bit pattern for -1doesn't change. In two's complement -1 is an all-ones bit pattern, e.g.

int a = -1; // Pattern 11111111.11111111.11111111.11111111

when you right shift a two complements integer being -1 you simply get the same bit pattern and therefore the same value. You shift out a 1at LSB and shift in a 1 at MSB. So the binary pattern stays the same.

So what happens to -3:

int a = -3; // Pattern 11111111.11111111.11111111.11111101
a = a >> 1; // Pattern 11111111.11111111.11111111.11111110 = -2

Answer 2

You should not use shift operatings in your code, if you are trying to do division. The optimizer is able to figure this out better than you can. Of course, if you really know what you are doing and you are using unsigned integers entirely and you are writing in assembly, go ahead. Until then, just use the normal math operators for doing normal math operations.

If you are asking why -1 >> 1 == -1, well that's easy. The value negative one looks like all ones in binary, or 0xFFFFFFFF in hex. Shift the bits to the right and shift-in in a new 1 to the empty hole on the left, and you are left with what you started !

Answer 3

Why does -1 >> 1 == -1?

Whenever you shift, the machine must fill in a missing value. We'll use four bits just to keep things simple. When you shift left, the bit that must be replaced is the trailing bit:

0101 << 1  // equivalent of 5 * 2
101_  // This is filled in with a zero
1010  // 5 * 2 == 10

When you shift right, the leading bit must be replaced. But since the leading bit determines sign in signed 2s complement, we don't want to lose that sign (shifting left, or int dividing by some power of 2, should never cause a negative number to become positive or vice versa). So the replacement value is whatever the leading (sign) bit already was:

0111 >> 1  // equivalent of 7 intdiv 2
_011  // Signed, so this is filled in with a zero
0011  // 7 intdiv 2 == 3

1111 >> 1  // equivalent of -1 intdiv 2, kinda
_111  // Signed, so this is filled in with a 1
1111  // -1 intdiv 2 == -1

However, if this was unsigned representation, the leading bit would simply be filled in with a zero:

1111 >> 1  // equivalent of 15 intdiv 2
_111  // Unsigned, so this is filled in with a 0
0111  // 15 intdiv 2 == 7

Further reading: https://msdn.microsoft.com/en-us/library/336xbhcz.aspx

Answer 4

Consider this case:

-1 = 0b11

-1 >> 1 => 0b11 >> 1 => 0b11 (Many 1s on the left) (= -1)

If you look back -3 >> 1 case (prepare your computer's calc in programmer's mode) you should see 0b111101 >> 1 becomes 0b111110 (-2)

Answer 5

The results are still consistent. The effect that a right shift by 1 has is division by 2 rounded down.

In the case of an odd positive value, the "extra" 0.5 gets dropped. In the case of an odd negative value, it goes the other way.

In the examples you give above, half of -1 is -0.5, rounded down to -1. Similarly, half of -3 is -1.5, rounded down to -2.