Why Was 1 << 31 Changed to Be Implementation-Defined in C++14

Why was 1 31 changed to be implementation-defined in C++14?

The relevant issue is CWG 1457, where the justification is that the change allows 1 << 31 to be used in constant expressions:

The current wording of 5.8 [expr.shift] paragraph 2 makes it undefined
behavior to create the most-negative integer of a given type by
left-shifting a (signed) 1 into the sign bit, even though this is not
uncommonly done and works correctly on the majority of
(twos-complement) architectures:

...if E1 has a signed type and non-negative value, and E1 * 2^E2 is
representable in the result type, then that is the resulting value;
otherwise, the behavior is undefined.

As a result, this technique
cannot be used in a constant expression, which will break a
significant amount of code.

Constant expressions can't contain undefined behavior, which means that using an expression containing UB in a context requiring a constant expression makes the program ill-formed. libstdc++'s numeric_limits::min, for example, once failed to compile in clang due to this.

Why does (1 31) 31 result in -1?

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.

Why is 0x7FFFFFFFull | (1 31) returning 0xFFFFFFFFFFFFFFFF in C++?

Firstly your code does not do what you say in your title/question; I have edited the title.

The problem is 1 << 31. If you have 32-bit int (which apparently you do, judging by the results), this cause arithmetic overflow. In C++14 this is implementation-defined behaviour; prior to C++14 it causes undefined behaviour. Reference.

Usually the implementation-defined behaviour will be to generate the int with the sign bit set and the other bits unset. In 2's complement this value is INT_MIN. You then perform arithmetic between an unsigned long long and an int. This is defined as: the int is converted to unsigned long long.

Converting signed integers to unsigned is done by wrapping it around (modular arithmetic) modulo ULLONG_MAX+1. So the result of (unsigned long long)INT_MIN is a very large positive number, in fact 0xFFFFFFFF80000000. (To check this, add 0x80000000 to it to get 0).

So you are actually doing 0x7FFFFFFF | 0xFFFFFFFF80000000 which gives the observed result.

---

Later on it gets worse: 1 << 32 and larger causes undefined behaviour due to shifting by the whole width of the type.

To fix this, change 0x1 in your code to 1ull. The you will be shifting an unsigned long long, instead of an int.

Defining (1 31) or using 0x80000000? Result is different

1 << 31 is undefined behavior on most platforms (e. g., systems with 16-bit or 32-bit int) as its result cannot be represented in an int (the resulting type of the expression). Don't use that expression in code. On the other hand 1U << 31 is a valid expression on systems with 32-bit int as its result is representable in an unsigned int (the resulting type of the expression).

On a 32-bit int system, 0x80000000 is a (relatively) big positive integer number of type unsigned int. If you are lucky (or unlucky) enough to not have demons to fly out of your nose by using 1 << 31 expression, the most likely result of this expression is INT_MIN which is a (relatively) big negative integer number of type int.

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

What you are missing is that in C++ right shift >> is implementation defined. It could either be logical or arithmetic shift for a signed value. In this case it's shifting in 1s from the left to retain the sign of the shifted value. Typically you want to avoid doing shifts on signed values unless you know precisely that they will be positive or that the shift implementation doesn't matter.

1 31 produces the error, The result of the '' expression is undefined

2³¹ isn't representable in a int32_t, which goes from -2³¹ to (2³¹-1). This is undefined behavior in C11 and C++11, and 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 representable, 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 int32_t; this conversion is implementation-defined per §4.7 [conv.integral]/p3. In a typical system using two's complement you'd get -2³¹.

Why not C++ define INT_MIN as (131)

That prevent the overflow and also easy to understand

How could it prevent the overflow, if by left-shifting a positive number you are trying to obtain a negative one? ;)

Keep in mind, that signed integer overflow is Undefined Behavior. Per paragraph 5.8/2 of the C++11 Standard:

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

Also, per paragraph 5/4:

If during the evaluation of an expression, the result is not mathematically defined or not in the range of
representable values for its type, the behavior is undefined. [...]

Doubts on bit-shifting behavior

1. 
   

   is this perfectly fine?

   Yes. i will become 4093640704, in hexadecimal 0xf4000000.

2. 
   

   Is that an overflow?

   No. It is a right shift (division-like operation), so i will become zero.

Note, that the rules about shift are very likely to change. Currently, several cases are undefined behavior or implementation defined. As the next standard will require two's complement arithmetic, the rules about shifting will be relaxed: the only undefined behavior will be, if the shift amount is larger or equal than the types' width. Here are the current draft rules: link.

Why does left shift operation invoke Undefined Behaviour when the left side operand has negative value?

The paragraph you copied is talking about unsigned types. The behavior is undefined in C++. From the last C++0x draft:

The value of E1 << E2 is E1
left-shifted E2 bit positions; vacated
bits are zero-filled. 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. Otherwise, if E1
has a signed type and non-negative
value, and E1×2^E2 is representable in
the result type, then that is the
resulting value; otherwise, the
behavior is undefined.

EDIT: got a look at C++98 paper. It just doesn't mention signed types at all. So it's still undefined behavior.

Right-shift negative is implementation defined, right. Why? In my opinion: It's easy to implementation-define because there is no truncation from the left issues. When you shift left you must say not only what's shifted from the right but also what happens with the rest of the bits e.g. with two's complement representation, which is another story.

---

Related Topics