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

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

Niall
  • 30,036
  • 10
  • 99
  • 142
thephoquang
  • 63
  • 1
  • 8
  • 1
    You're seeing an arithmetic shift right, but this is implementation-defined. – Paul R Oct 04 '14 at 11:21
  • As @PaulR says (me too). – Cheers and hth. - Alf Oct 04 '14 at 11:56
  • Did you mean to use unsigned integers? – Neil Kirk Oct 04 '14 at 12:54
  • @PaulR It's implementation defined as the result may differ on architectures that don't use two's complement. All implementations except for some very exotic ones implement signed right-shift with the semantics you would expect. – fuz Oct 04 '14 at 14:29
  • @FUZxxl: I don't think it's quite as simple that, e.g. if a particular 2's complement CPU lacks an ASR instruction then it might make more sense to use LSR for `>>`. – Paul R Oct 04 '14 at 16:29
  • @PaulR Point is, none of them (except for some very old old ones) lack this instruction. – fuz Oct 04 '14 at 21:07
  • @FUZxxl: that's simply not true, unless you just restrict yourself to the world of modern desktop and server CPUs and ignore the much larger field of embedded CPUs. For example the 8051 core, which is still widely used, has no arithmetic shift right. – Paul R Oct 05 '14 at 07:00
  • 1
    @PaulR Good point. I was talking about hosted systems. – fuz Oct 05 '14 at 12:05

6 Answers6

9
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 × 2E2 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.

Community
  • 1
  • 1
AlexD
  • 32,156
  • 3
  • 71
  • 65
  • Which standard and which version are you quoting? – T.C. Oct 04 '14 at 13:00
  • @T.C.: Looks like C99. C++11 is almost identical (just specifying a "value" rather than a "result" to match C++ terminology). – Mike Seymour Oct 04 '14 at 13:10
  • It is worse than this: a C++ compiler who knew you started with a positive number could optimize `x>>31` to be `x=0`. Similarly it could treat `x<<31` as proof that `x<=0` (snd `x>=-1` maybe? unsure), as anythimg else leads to undefined behaviour. – Yakk - Adam Nevraumont Oct 04 '14 at 15:46
6

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).

tangrs
  • 9,709
  • 1
  • 38
  • 53
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 231 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 231 is representable in an unsigned 32-bit int, the behavior is defined and the result is 231 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 -231, 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.

T.C.
  • 133,968
  • 17
  • 288
  • 421
0

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, 231 is not representable in a 32-bit int whose maximum value is 231 - 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.

Community
  • 1
  • 1
M.M
  • 138,810
  • 21
  • 208
  • 365
0

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.

Chintan Patel
  • 310
  • 1
  • 2
  • 11
0

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.

Luis Colorado
  • 10,974
  • 1
  • 16
  • 31