Right bit-shift giving wrong result, can someone explain

Question

I'm right-shifting -109 by 5 bits, and I expect -3, because -109 = -1101101 (binary) shift right by 5 bits -1101101 >>5 = -11 (binary) = -3

But, I am getting -4 instead. Could someone explain what's wrong?

Code I used:

int16_t a = -109;
int16_t b = a >> 5;
printf("%d %d\n", a,b);

I used GCC on linux, and clang on osx, same result.

Answer 1

The thing is you are not considering negative numbers representation correctly. With right shifting, the type of shift (arithmetic or logical) depends on the type of the value being shifted. If you cast your value to an unsigned value, you might get what you are expecting:

int16_t b = ((unsigned int)a) >> 5;

You are using -109 (16 bits) in your example. 109 in bits is:

00000000 01101101

If you take's 109 2's complement you get:

11111111 10010011

Then, you are right shifting by 5 the number 11111111 10010011:

__int16_t a = -109;
__int16_t b = a >> 5; // arithmetic shifting
__int16_t c = ((__uint16_t)a) >> 5; // logical shifting
printf("%d %d %d\n", a,b,c);

Will yield:

-109 -4 2044

Answer 2

The result of right shifting a negative value is implementation defined behavior, from the C99 draft standard section 6.5.7 Bitwise shift operators paragraph 5 which says (emphasis mine going forward):

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 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

If we look at gcc C Implementation-defined behavior documents under the Integers section it says:

The results of some bitwise operations on signed integers (C90 6.3, C99 and C11 6.5).

Bitwise operators act on the representation of the value including both the sign and value bits, where the sign bit is considered immediately above the highest-value value bit. Signed ‘>>’ acts on negative numbers by sign extension.

Answer 3

That's pretty clear what's happening, when representing signed integers, negative integers have a property which is, sign extension, and the left most significant bit is the sign bit.

So, 1000 ... 0000 (32 bit) is the biggest negative number that you can represent, with 32 bits.

Because of this, when you have a negative number and you shift right, a thing called sign extension happens, which means that the left most significant bit is extended, in simple terms it means that, for a number like -109 this is what happens:

Before shifting you have (16bit):

1111 1111 1001 0011

Then you shift 5 bits right (after the pipe are the discarded bits):

1XXX X111 1111 1100 | 1 0011

The X's are the new spaces that appear in your integer bit representation, that due to the sign extension, are filled with 1's, which give you:

1111 1111 1111 1100 | 1 0011

So by shifting: -109 >> 5, you get -4 (1111 .... 1100) and not -3.

Confirming results with the 1's complement:

+3 = 0... 0000 0011

-3 = ~(0... 0000 0011) + 1 = 1... 1111 1100 + 1 = 1... 1111 1101

+4 = 0... 0000 0100

-4 = ~(0... 0000 0100) + 1 = 1... 1111 1011 + 1 = 1... 1111 1100

Note: Remember that the 1's complement is just like the 2's complement with the diference that you first must negate the bits of positive number and only then sum +1.

Answer 4

Pablo's answer is essentially correct, but there are two small bits (no pun intended!) that may help you see what's going on.

C (like pretty much every other language) uses what's called two's complement, which is simply a different way of representing negative numbers (it's used to avoid the problems that come up with other ways of handling negative numbers in binary with a fixed number of digits). There is a conversion process to turn a positive number in two's complement (which looks just like any other number in binary - except that the furthest most left bit must be 0 in a positive number; it's basically the sign place-holder) is reasonably simple computationally:

Take your number

00000000 01101101 (It has 0s padding it to the left because it's 16 bits. If it was long, it'd be padded with more zeros, etc.)

Flip the bits

11111111 10010010

Add one.

11111111 10010011.

This is the two's complement number that Pablo was referring to. It's how C holds -109, bitwise.

When you logically shift it to the right by five bits you would APPEAR to get

00000111 11111100.

This number is most definitely not -4. (It doesn't have a 1 in the first bit, so it's not negative, and it's way too large to be 4 in magnitude.) Why is C giving you negative 4 then?

The reason is basically that the ISO implementation for C doesn't specify how a given compiler needs to treat bit-shifting in negative numbers. GCC does what's called sign extension: the idea is to basically pad the left bits with 1s (if the initial number was negative before shifting), or 0s (if the initial number was positive before shifting).

So instead of the 5 zeros that happened in the above bit-shift, you instead get:

11111111 11111100. That number is in fact negative 4! (Which is what you were consistently getting as a result.)

To see that that is in fact -4, you can just convert it back to a positive number using the two's complement method again:

00000000 00000011 (bits flipped) 00000000 00000100 (add one).

That's four alright, so your original number (11111111 11111100) was -4.