Right Shift and Signed Integer

Arithmetic bit-shift on a signed integer

Right shift of a negative signed number has implementation-defined behaviour.

If your 8 bits are meant to represent a signed 8 bit value (as you're talking about a "signed 32 bit integer" before switching to 8 bit examples) then you have a negative number. Shifting it right may fill "empty" bits with the original MSB (i.e. perform sign extension) or it may shift in zeroes, depending on platform and/or compiler.

(Implementation-defined behaviour means that the compiler will do something sensible, but in a platform-dependent manner; the compiler documentation is supposed to tell you what.)

---

A left shift, if the number either starts out negative, or the shift operation would shift a 1 either to or beyond the sign bit, has undefined behaviour (as do most operations on signed values which cause an overflow).

(Undefined behaviour means that anything at all could happen.)

---

The same operations on unsigned values are well-defined in both cases: the "empty" bits will be filled with 0.

Right shift and signed integer

From the following link:

INT34-C. Do not shift an expression by a negative number of bits or by greater than or equal to the number of bits that exist in the operand

Noncompliant Code Example (Right Shift)

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 and can be either an arithmetic (signed) shift:

Or a logical (unsigned) shift:

This noncompliant code example fails to test whether the right operand is greater than or equal to the width of the promoted left operand, allowing undefined behavior.

unsigned int ui1;
unsigned int ui2;
unsigned int uresult;
 
/* Initialize ui1 and ui2 */
 
uresult = ui1 >> ui2;

Making assumptions about whether a right shift is implemented as an arithmetic (signed) shift or a logical (unsigned) shift can also lead to vulnerabilities. See recommendation INT13-C. Use bitwise operators only on unsigned operands.

Right shift for signed integer

From the C99 standard N1256 (emphasis mine):

6.5.7 Bitwise shift operators

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

Arithmetic right-shift of signed integer

Most embedded compilers for microcontrollers tend to favour logical shift (shift in zeroes) instead of arithmetic shift (shift in the sign bit).

This is probably because signed numbers are somewhat rare in embedded systems, since such programming is much closer to the hardware and further away from users, than for example desktop programming with screens.

Signed numbers is nothing but user presentation after all. If you have no need to print numbers to a user, then you don't need signed numbers very often at all.

And of course, it doesn't really make any sense to use shift on signed numbers to begin with. I have never in my programming career encountered a scenario when I had needed to do that. Meaning in most cases, such shifts are just accidental bugs.

Are the shift operators (, ) arithmetic or logical in C?

According to K&R 2nd edition the results are implementation-dependent for right shifts of signed values.

Wikipedia says that C/C++ 'usually' implements an arithmetic shift on signed values.

Basically you need to either test your compiler or not rely on it. My VS2008 help for the current MS C++ compiler says that their compiler does an arithmetic shift.

Bitwise shift operators on signed types

Q1: The behaviour of the left shift operator on negative values of signed integer types is undefined, as is the behaviour for positive values of signed integer types when the result E1 * 2^E2 is not representable in the type.

That is explicitly mentioned in section 6.5.7, paragraph 4 and 5 of the standard (n1570 draft):

4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2^E2 , reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

Q2: The reduction modulo one more than the maximum value representable in the unsigned integer type means that the bits that are shifted out on the left are simply discarded.

Mathematically, if the maximal value of the unsigned type is 2^n - 1 (and it is always of that form), the result of shifting E1 left by E2 bits is the value V in the range from 0 to 2^n - 1 such that the difference

(E1 * 2^E2 - V)

is divisible by 2^n, that is, it's the remainder you get when dividing E1 * 2^E2 by 2^n.

Q3: The behaviour upon shifting right negative values of signed integer types is implementation-defined. The most common behaviour (at least on two's complement machines) is an arithmetic shift, that is, the result is the quotient rounded down (towards negative infinity).

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.

Signed and unsigned right shift seem to have the same behaviour

This is normal behavior. Any integer with a negative value has a binary representation starting with infinite 1s.

So if you start out with say: -3 the binary representation looks like this:

...11 1101

So if we right shift this by 2 we get

...11 1111

Now for the unsgined/signed right shift. This relies on the fact that we don't have infinite digits in our integer. So say we have an 8bit integer assigned as -3 it looks like this:

1111 1101

If we do a signed shift, it will look at the MSB (most significant bit, the most left one) and preserve the value of that when shifting. So a signed shift right by 3 looks like this:

1111 1111

On the contrary, a unsigned right shift will not check the MSB and just shift right and fill with zeroes resulting in this:

0011 1111

This is exactly what you're seeing but the output truncates the preceding zeroes away.

---

If you don't know why negative integers are stored that way, check this answer.

---

As for why (b & 0xff) >>> 5 behaves differently

Integers in java are 32bit, that means the binary representation will have 32 digits. Your -59 will look like the following binary representation:

1111 1111 1111 1111 1111 1111 1100 0101 == -59
0000 0111 1111 1111 1111 1111 1111 1110 == -59 >>> 5

If you now and this together with 0xff you get the following:

1111 1111 1111 1111 1111 1111 1100 0101 == -59
0000 0000 0000 0000 0000 0000 1111 1111 == 0xff
0000 0000 0000 0000 0000 0000 1100 0101 == -59 & 0xff
0000 0000 0000 0000 0000 0000 0000 0110 == (-59 & 0xff) >>> 5

---

Related Topics