Why does (1 << 31>> 31 result in -1? [duplicate

Question

This question already has an answer here:

• why shift int a=1 to left 31 bits then to right 31 bits, it becomes -1 4 answers

int z = 1;
z <<= 31;
z >>= 31;
printf ("%d\n",z);

When I run the code, z=-1, why?

Answer 1

Right, shifting a signed integer and negative numbers is implementation defined I believe.

Your implementation is probably doing a sign bit extension when you shift to the right.

So instead of shifting in zeros from the left, it's shifting in the sign bit. z <<= 31; is probably setting the sign bit to 1, then z >>= 31; is shifting in ones from the left so you end up with a bit pattern of 0xFFFFFFFF which is interpreted as the value -1 on your platform (which probably uses two's complement).

Answer 2

Assuming 32-bit ints, this is undefined behavior in C11 and C++11, but implementation-defined in C++14.

C11 §6.5.7/p4 (quoting N1570):

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. [...] If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

The C++11 rule in N3337 §5.8 [expr.shift]/p2 is pretty much identical. Since 2³¹ isn't usually representable in a signed 32-bit int, the behavior is undefined.

C++14 §5.8 [expr.shift]/p2 (quoting N3936; see also CWG issue 1457):

The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. [...] Otherwise, if E1 has a signed type and non-negative value, and E1×2E2is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

As 2³¹ is representable in an unsigned 32-bit int, the behavior is defined and the result is 2³¹ converted to (signed) int; this conversion is implementation-defined per §4.7 [conv.integral]/p3. In a typical system using two's complement you'd get -2³¹, in which case the subsequent right shift is also implementation defined since the value is negative. If an arithmetic shift is performed, then the sign bit is shifted in, and you end up with -1.

Answer 3

If you were using unsigned int you'll get the same results. The issue is you have used << to left shift a 31 bits plus a bit sign 31 times to the left. This is unsigned behaviour, as you have lost the most significant bit on the left side into the sign bit (this is what are you getting as the result of that undefined behaviour)

When you do a right shift, this is made differently when you have signed integers (you get a copy of the sign bit into the most significant bit) than when you have unsigned ones (you get a zero bit shifted from the left side). Normally, this means you get a right arithmetical shift instruction for signed integers (equivalent to a divide by two) when you do a right shift and a right logical shift instruction (equivalent also to a divide by two, but with unsigned numbers) when you do a right shift with unsigned numbers.

just try the same declaring z as unsigned int z; and you'll get the expected behaviour.

Answer 4

Assuming you are talking about int being 32-bit or smaller here. (If int is larger then this code is well-defined and results in z being 1).

In C and C++, z <<= 31 is defined as z = z << 31.

In C11, << is explained as (6.5.7/4):

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. [...] If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

In this case E1 is z which is 1, and E2 is 31. However, 2³¹ is not representable in a 32-bit int whose maximum value is 2³¹ - 1, therefore the behaviour is undefined.

When undefined behaviour occurs anything can happen, ranging from you seeing unexpected output, to the program crashing, to missiles being launched, and so on.

In C99, C++98 and C++03 << has a similar definition; 1 << 31 is undefined behaviour in all of those (for 32-bit or smaller ints).

---

In C++11 and C++14 there is an option you can test, std::numeric_limits<int>::is_modulo . If this is true then in some people's opinion, it means that integer overflow is no longer undefined, and so the result of 1 << 31 must be INT_MIN. For further discussion of this topic see this thread.

Supposing we get this far (i.e. your system has 32-bit ints, and std::numeric_limits<int>::is_modulo == true, and you side with those who interpret the standard as saying that there is no UB on signed int overflow in this situation) then we have the following:

assert( CHAR_BIT * sizeof(int) == 32 );
assert( std::numeric_limits<int>::is_modulo == true );
int z = 1;
z <<= 31;
assert(z == INT_MIN);

Now to discuss z >>= 31. This is defined as z = z >> 31;. In C++11 5.8/3:

The value of E1 >> E2 is E1 right-shifted E2 bit positions. [...] If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Since INT_MIN is a negative value, the behaviour is implementation-defined. This means that your implementation must document what it does, so you can consult your compiler's documentation to find out what is happening here.

A likely explanation is that it performs an arithmetic shift, which means that the bits are shifted right, but the sign bit retains its value. This means you end up with all-bits-one, which is -1 in two's complement.

Answer 5

this is because sign copy mechanism, when ever you are left shifting z by 31 times, 1 is shifted from 0th bit position to 31st bit position. now on you are having 1 in 31st bit which will be treated as negative numbers. and in negative numbers, sign copy mechanism is used, in which if you right shift on negative numbers, sign bit is preserved. so you are having 1's in every bit position which is -1 in decimal.

Answer 6

int z = 1;
z <<= 31;

Assuming int is 32 bit and two's complement representation is used, the left shift is undefined behavior in C because the result if not representable in the int type. From the standard:

The result of E1 << E2 is E1 left-shifted E2 bit positions

...

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.

In practice, it is likely to result in 0x80000000, which is treated as a negative number.

And right-shifting of negative integers is implementation-defined behavior:

The result of E1 >> E2 is E1 right-shifted E2 bit positions.

...

If E1 has a signed type and a negative value, the resulting value is implementation-defined.

---

In C++ left shift is defined in a similar way till C++14, as @T.C. mentioned (or, with some restrictions, might be even till C++11, as @MattMcNabb wrote).

But even if left-shift is defined and 0x8000000 is the expected value, the result of a right shift of a negative number is still implementation-defined.