72

I am trying to figure out how exactly arithmetic bit-shift operators work in C, and how it will affect signed 32-bit integers.

To make things simple, let's say we work within one byte (8 bits):

x = 1101.0101
MSB[ 1101.0101 ]LSB

Reading other posts on Stack Overflow and some websites, I found that: << will shift toward MSB (to the left, in my case), and fill "empty" LSB bits with 0s.

And >> will shift toward LSB (to the right, in my case) and fill "empty" bits with MS bit

So, x = x << 7 will result in moving LSB to MSB, and setting everything to 0s.

1000.0000

Now, let's say I would >> 7, last result. This would result in [0000.0010]? Am I right?

Am I right about my assumptions about shift operators?

I just tested on my machine, **

int x = 1;   //000000000......01

x = x << 31; //100000000......00

x = x >> 31; //111111111......11 (Everything is filled with 1s !!!!!)

Why?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
newprint
  • 6,936
  • 13
  • 67
  • 109
  • 3
    possible duplicate of [Shift operator in C](http://stackoverflow.com/questions/7622/shift-operator-in-c) – Jens Gustedt Oct 24 '10 at 19:42
  • 5
    "Why?" Because **your implementation** says so. Check the documentation: it **must** define the behaviour of right shifting a negative value (or you do not have a C compiler). – pmg Oct 24 '10 at 20:02
  • @pseudonym27 that you have to find in documentation – newprint Nov 21 '14 at 18:55
  • @pseudonym27: right shifting is well defined, left shifting isn't. Consider left shifting as successive multiplications by `2`. If any multiplication overflows you have **Undefined Behaviour**. – pmg Nov 22 '14 at 10:23
  • The [draft of the C11 Standard (PDF document)](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) is freely available online. – pmg Nov 23 '14 at 10:26
  • superset: http://stackoverflow.com/questions/11644362/are-the-results-of-bitwise-operations-on-signed-integers-defined – Ciro Santilli OurBigBook.com Aug 10 '16 at 13:27

6 Answers6

74

Right shift of a negative signed number has implementation-defined behaviour.

If your 8 bits are meant to represent a signed 8 bit value (as you're talking about a "signed 32 bit integer" before switching to 8 bit examples) then you have a negative number. Shifting it right may fill "empty" bits with the original MSB (i.e. perform sign extension) or it may shift in zeroes, depending on platform and/or compiler.

(Implementation-defined behaviour means that the compiler will do something sensible, but in a platform-dependent manner; the compiler documentation is supposed to tell you what.)

A left shift, if the number either starts out negative, or the shift operation would shift a 1 either to or beyond the sign bit, has undefined behaviour (as do most operations on signed values which cause an overflow).

(Undefined behaviour means that anything at all could happen.)

The same operations on unsigned values are well-defined in both cases: the "empty" bits will be filled with 0.

Matthew Slattery
  • 45,290
  • 8
  • 103
  • 119
  • 2
    It should be said that the right shift with standard, portable semantics is also known as division by a power-of-two literal. Most compilers will generate arithmetic shifts for such divisions, resulting in fast code that does sign extension as desired. – Kuba hasn't forgotten Monica Jun 16 '14 at 17:51
  • 5
    @KubaOber: Modern standards require that `x/2` behave differently from a right shift in the case where `x` is a negative odd number. A normal arithmetic right shift will perform floored division (so in cases that don't overflow `(n+d)/d == (n/d)+1`, but division is required to use truncated division, thus preventing compilers from using a simple shift. – supercat Jul 09 '14 at 18:02
  • @KubaOber: It should be noted that left-shift of a signed value used to be a power-of-two-signed multiply, but newer compilers seem to have deprecated support for left-shifting of negative numbers. – supercat Apr 16 '15 at 05:49
  • 3
    It might be good to indicate that on hyper-modern compilers, "anything at all" includes rearranging program logic to pretend negative values are positive. Given `void foo(int x) { if (x >= 0) printf("Kaboom!"); int y= x<<4; }` calling `foo(-1);` could very likely print "Kaboom!". – supercat Apr 16 '15 at 05:56
45

Bitwise shift operations are not defined for negative values

for '<<'

6.5.7/4 [...] 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.

and for '>>'

6.5.7/5 [...] If E1 has a signed type and a negative value, the resulting value is implementation- defined.

It's a waste of time to study the behaviour of these operations on signed numbers on a specific implementation, because you have no guarantee it will work the same way on any other implementation (an implementation is, for example, you compiler on your computer with your specific commad-line parameters).

It might not even work for an older or a newer version of the very same compiler. The compiler might even define those bits as random or undefined. This would mean that the very same code sequence could produce totally different results when used across your sources or even depend on things like assembly optimisation or other register usage. If encapsulated in a function it might not even produce the same result in those bits on two consecutive calls with the same arguments.

Considering only non-negative values, the effect of left shifting by 1 (expression << 1) is the same as multpliying the expression by 2 (provided expression * 2 does not overflow) and the effect of right shifting by 1 (expression >> 1) is the same as dividing by 2.

Alexander Stohr
  • 159
  • 1
  • 18
pmg
  • 106,608
  • 13
  • 126
  • 198
15

As of c++20 the bitwise shift operators for signed integers are well defined.

The left shift a<<b is equivalent to a*2^b modulus 2^N where N is the number of bits in the resulting type. In particular 1<<31 is in fact the smallest int value.

The right shift a>>b is equivalent to a/2^b, rounded down (ie. towards negative infinity). So e.g. -1>>10 == -1.

For some more details see https://en.cppreference.com/w/cpp/language/operator_arithmetic .

(for the older standards see the answer by Matthew Slattery)

example
  • 3,349
  • 1
  • 20
  • 29
  • And how about golang, or any other language with a faint resemblance to C? – mevets Jun 18 '20 at 18:43
  • @mevets: All the sane ones (or at least sane implementations of them) already worked this way, with `>>` on signed types required to be an arithmetic right shift. C++ is only finally just getting around to actually documenting what everyone wants their compilers to do anyway, and which languages like Rust and Java have done from the start. Guaranteed arithmetic right right, instead of implementation-defined. – Peter Cordes Apr 30 '21 at 07:29
  • @mevets: Check here regarding Python: https://realpython.com/python-bitwise-operators/ – Hari Jan 24 '22 at 20:04
  • C++20 does not guarantee that "`1<<31` is in fact the smallest `int` value." `int` is not necessarily `int32_t`. – Ben Voigt Jul 07 '22 at 16:44
7

As others said shift of negative value is implementation-defined.

Most of implementations treat signed right shift as floor(x/2N) by filling shifted in bits using sign bit. It is very convenient in practice, as this operation is so common. On the other hand if you will shift right unsigned integer, shifted in bits will be zeroed.

Looking from machine side, most implementations have two types of shift-right instructions:

  1. An 'arithmetic' shift right (often having mnemonic ASR or SRA) which works as me explained.

  2. A 'logic' shift right (oftem having mnemonic LSR or SRL or SR) which works as you expect.

Most of compilers utilize first for signed types and second for unsigned ones. Just for convenience.

Vovanium
  • 3,798
  • 17
  • 23
0

In the 32 bit compiler

x = x >> 31;

here x is the signed integer so 32nd bit is sign bit.

final x value is 100000...000. and 32nd bit indicate -ive value.

here x value implement to 1's compliment.

then final x is -32768

user3060837
  • 1
  • 1
-2

On my i7:

uint64_t:

0xffffffffffffffff >> 0 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 1 is 0b0111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 2 is 0b0011111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 3 is 0b0001111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 4 is 0b0000111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 62 is 0b0000000000000000000000000000000000000000000000000000000000000011
0xffffffffffffffff >> 63 is 0b0000000000000000000000000000000000000000000000000000000000000001
0xffffffffffffffff >> 64 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 65 is 0b0111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 66 is 0b0011111111111111111111111111111111111111111111111111111111111111

int64_t -1

0xffffffffffffffff >> 0 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 1 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 2 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 3 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 4 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 62 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 63 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 64 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 65 is 0b1111111111111111111111111111111111111111111111111111111111111111
0xffffffffffffffff >> 66 is 0b1111111111111111111111111111111111111111111111111111111111111111

int64_t 2^63-1

0x7fffffffffffffff >> 0 is 0b0111111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 1 is 0b0011111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 2 is 0b0001111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 3 is 0b0000111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 4 is 0b0000011111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 62 is 0b0000000000000000000000000000000000000000000000000000000000000001
0x7fffffffffffffff >> 63 is 0b0000000000000000000000000000000000000000000000000000000000000000
0x7fffffffffffffff >> 64 is 0b0111111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 65 is 0b0011111111111111111111111111111111111111111111111111111111111111
0x7fffffffffffffff >> 66 is 0b0001111111111111111111111111111111111111111111111111111111111111
Andreas Haferburg
  • 5,189
  • 3
  • 37
  • 63