Categories
bit-shift c++

Why doesn’t left bit-shift, “

74

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.

20

  • 1

    You might want to show exactly what command line (switches) you have used, what version of GCC and also on which platform.

    Sep 13, 2011 at 12:35

  • 3

    @xanatos How do you know that this is a “wrong” question?!

    Sep 13, 2011 at 12:36

  • 5

    @awoodland I too think so. According to latest draft: “The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.” (5.8) N3291

    Sep 13, 2011 at 12:38

  • 1

    The problem is that, as given by the OP, the question was illogical. He said “look here, it gives me 1”, but the example he gave returned 0 🙂

    – xanatos

    Sep 13, 2011 at 12:38

  • 3

    @Arak Before speaking, at least follow the link and watch the history. His original message was: when i write the following program on GNU C++ compiler http://ideone.com/VPTwj it shows me an output of 1 then please follow the link and look at the upper left: language: C++ (gcc-4.3.4). I think it’s as much clear as it can be.

    – xanatos

    Sep 13, 2011 at 12:47

51

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

From The C programming language 2

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 3

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.


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

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

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

1

48

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

7

  • But… why is this undefined behavior? Why couldn’t the low-level code perform the subtraction, determine that it need consider only the lowest zero bits, and return 0 without inspecting the value at all?

    – Beta

    Sep 13, 2011 at 12:43

  • 5

    @Beta – it’s undefined so as not to encumber implementations with the burden of emulating in software what was “the norm” in hardware at the point in time when the standard was conceived.

    – Flexo

    Sep 13, 2011 at 12:46

  • 2

    @Beta: interesting question ! Most of those undefined operations map directly to processor instructions. The behavior is generally undefined because doing otherwise would require checks prior to the operations that would not be implemented efficiently on most architectures. Typical safety/speed tradeof.

    Sep 13, 2011 at 12:49


  • 11

    @Beta: “Don’t pay for what you don’t need” principle. You can do the check, if your code needs it. But if the check was automatic, you could not not do it.

    – MSalters

    Sep 13, 2011 at 13:53

  • 1

    @Beta, Imagine the instruction for shift in a certain computer takes 5 bits. No matter what you do, you just can’t shift a variable by 32! (Something like 01011 (shift) 010 (to register 2) 110 (from register 6) ????? (shift amount) (This is an imaginary but very possible instruction))

    – Shahbaz

    Oct 14, 2011 at 12:39


23

It’s undefined behaviour according to the C++ standard:

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
.

9

  • 5

    that’s some mighty quick standard searching!

    – Flexo

    Sep 13, 2011 at 12:39

  • 3

    @awoodland Yes, Google is seriously impressive!

    Sep 13, 2011 at 12:39

  • 2

    @AnkitSablok Undefined behavior means that any behavior can happen 😉 check: stackoverflow.com/questions/2397984/…

    Sep 13, 2011 at 12:42

  • 3

    @Ankit The answer should not be 0. The answer is undefined. The answer could be anything. This is the essence of undefined behaviour.

    Sep 13, 2011 at 12:44

  • 2

    @AnkitSablok – it DOES justify the behaviour. The point is that when behaviour is undefined the compiler is allowed to do anything it pleases. At best guess the compiler has simply decided to do nothing (which is perfectly valid according to the standard)

    – V.S.

    Sep 13, 2011 at 12:45