(-1 >> 1) == -1 - Why?

Question

Why does (-1 >> 1) result in -1? I'm working in C, though I don't think that should matter.

I can not figure out what I'm missing...

Here is an example of a C program that does the calc:

#include <stdio.h>



int main()
{
    int num1 = -1;

    int num2 = (num1 >> 1);

    printf( "num1=%d", num1 );

    printf( "\nnum2=%d", num2 );

    return 0;
}

Answer 1

sign extension.

Answer 2

Bit shifting a negative number is implementation-behavior in C. The results will depend on your platform, and theoretically could be completely nonsensical. From the C99 standard (6.5.7.5):

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2 . If E1 has a signed type and a negative value, the resulting value is implementation-defined.

The reason this happens is most likely because your compiler uses the x86 SAR (Shift Arithmetic Right) instruction to implement >>. This means sign extension will occur - the most significant bit will be replicated into the new MSB once the value is shifted over. From the intel manuals:

The shift arithmetic right (SAR) and shift logical right (SHR) instructions shift the bits of the destination operand to the right (toward less significant bit locations). For each shift count, the least significant bit of the destination operand is shifted into the CF flag, and the most significant bit is either set or cleared depending on the instruction type. The SHR instruction clears the most significant bit (see Figure 7-8 in the Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 1); the SAR instruction sets or clears the most significant bit to correspond to the sign (most significant bit) of the original value in the destination operand. In effect, the SAR instruction fills the empty bit position’s shifted value with the sign of the unshifted value (see Figure 7-9 in the Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 1).

Answer 3

Because signed integers are represented in two's complement notation.

-1 will be 11111111 (if it was an 8 bit number).

-1 >> 1 evidently sign extends so that it remains 11111111. This behaviour depends on the compiler, but for Microsoft, when shifting a signed number right (>>) the sign bit is copied, while shifting an unsigned number right causes a 0 to be put in the leftmost bit.

Answer 4

When you right shift and the leftmost bit is a 1, some platforms/compilers will bring in a 0 and some will preserve the 1 and make the new leftmost bit a 1. This preserves the sign of the number so a negative number stays negative and is called sign extension.

You'll see the difference if you try ((unsigned) -1) >> 1, which will do an unsigned right shift and so will always shift in a 0 bit.

Answer 5

An Arithmetic right shift will preserve the sign when shifting a signed number:

11111111 (-1) will stay 11111111 (-1)

In contrast, a Logical right shift won't preserve the sign:

11111111 (-1) will become 01111111 (127)

Your code clearly does an arithmetic shift, so the sign bit (MSB) is repeated. What the operator (>>) does depends on the implementation details of the platform you're using. In most cases, it's an arithmetic shift.

Also, note that 11111111 can have two different meanings depending on the representation. This also affects they way they'll be shifted.

• If unsigned, 11111111 represents 255. Shifting it to the right won't preserve the sign since the MSB is not a sign bit.
• If signed, 11111111 represents -1. Arithmetically shifting it to the right will preserve the sign.