Why doesn't left bit-shift, “<<”, for 32

Question

When I write the following program and use the GNU C++ compiler, the output is 1 which I think is due to the rotation operation performed by the compiler.

#include <iostream>

int main()
{
    int a = 1;
    std::cout << (a << 32) << std::endl;

    return 0;
}

But logically, as it's said that the bits are lost if they overflow the bit width, the output should be 0. What is happening?

The code is on ideone, http://ideone.com/VPTwj.

Answer 1

You could try the following. This actually gives the output as 0 after 32 left shifts.

#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
  int a = 1;
  a <<= 31;
  cout << (a <<= 1);
  return 0;
}

Answer 2

Shifting a 32 bit variable by 32 or more bits is undefined behavior and may cause the compiler to make daemons fly out of your nose.

Seriously, most of the time the output will be 0 (if int is 32 bits or less) since you're shifting the 1 until it drops off again and nothing but 0 is left. But the compiler may optimize it to do whatever it likes.

See the excellent LLVM blog entry What Every C Programmer Should Know About Undefined Behavior, a must-read for every C developer.

Answer 3

This is caused due to a combination of an undefined behaviour in C and the fact that code generated for IA-32 processors has a 5 bit mask applied on the shift count. This means that on IA-32 processors, the range of a shift count is 0-31 only. ¹

From The C programming language ²

The result is undefined if the right operand is negative, or greater than or equal to the number of bits in the left expression’s type.

From IA-32 Intel Architecture Software Developer’s Manual ³

The 8086 does not mask the shift count. However, all other IA-32 processors (starting with the Intel 286 processor) do mask the shift count to 5 bits, resulting in a maximum count of 31. This masking is done in all operating modes (including the virtual-8086 mode) to reduce the maximum execution time of the instructions.

---

¹ http://codeyarns.com/2004/12/20/c-shift-operator-mayhem/

² A7.8 Shift Operators, Appendix A. Reference Manual, The C Programming Language

³ SAL/SAR/SHL/SHR – Shift, Chapter 4. Instruction Set Reference, IA-32 Intel Architecture Software Developer’s Manual

Answer 4

In C++, shift is only well-defined if you shift a value less steps than the size of the type. If int is 32 bits, then only 0 to, and including, 31 steps is well-defined.

So, why is this?

If you take a look at the underlying hardware that performs the shift, if it only has to look at the lower five bits of a value (in the 32 bit case), it can be implemented using less logical gates than if it has to inspect every bit of the value.

Answer to question in comment

C and C++ are designed to run as fast as possible, on any available hardware. Today, the generated code is simply a ''shift'' instruction, regardless how the underlying hardware handles values outside the specified range. If the languages would have specified how shift should behave, the generated could would have to check that the shift count is in range before performing the shift. Typically, this would yield three instructions (compare, branch, shift). (Admittedly, in this case it would not be necessary as the shift count is known.)

Answer 5

It doesn't work as expected because you're expecting too much.

In the case of x86 the hardware doesn't care about shift operations where the counter is bigger than the size of the register (see for example SHL instruction description on x86 reference documentation for an explanation).

The C++ standard didn't want to impose an extra cost by telling what to do in these cases because generated code would have been forced to add extra checks and logic for every parametric shift.

With this freedom implementers of compilers can generate just one assembly instruction without any test or branch.

A more "useful" and "logical" approach would have been for example to have (x << y) equivalent to (x >> -y) and also the handling of high counters with a logical and consistent behavior.

However this would have required a much slower handling for bit shifting so the choice was to do what the hardware does, leaving to the programmers the need to write their own functions for side cases.

Given that different hardware does different things in these cases what the standard says is basically "Whatever happens when you do strange things just don't blame C++, it's your fault" translated in legalese.

Answer 6

The answers of Lindydancer and 6502 explain why (on some machines) it happens to be a 1 that is being printed (although the behavior of the operation is undefined). I am adding the details in case they aren't obvious.

I am assuming that (like me) you are running the program on an Intel processor. GCC generates these assembly instructions for the shift operation:

movl $32, %ecx
sall %cl, %eax

On the topic of sall and other shift operations, page 624 in the Instruction Set Reference Manual says:

The 8086 does not mask the shift count. However, all other Intel Architecture processors (starting with the Intel 286 processor) do mask the shift count to five bits, resulting in a maximum count of 31. This masking is done in all operating modes (including the virtual-8086 mode) to reduce the maximum execution time of the instructions.

Since the lower 5 bits of 32 are zero, then 1 << 32 is equivalent to 1 << 0, which is 1.

Experimenting with larger numbers, we would predict that

cout << (a << 32) << " " << (a << 33) << " " << (a << 34) << "\n";

would print 1 2 4, and indeed that is what is happening on my machine.