Bitwise Leftshift (<<) strange behavior

Question

gcc bitwise Leftshift (<<) strange behavior. Here is my code:

#include <stdio.h> #include <string.h> void foo(int n){ printf("1<<32:%d\n", 1<<32); printf("1<<(32-n):%d\n", 1<<(32-n)); } int main(){ foo(0); }

If I pass 0 as parameter, the result could be different. Compiling the source code:

$gcc main.c -o demo -lm -pthread -lgmp -lreadline 2>&1 main.c: In function 'foo': main.c:5:3: warning: left shift count >= width of type [enabled by default]

Executing the program:

$demo 1<<32:0 1<<(32-n):1

This result is what I've got from compile online site

How can I make the foo function output 0 if I pass 0 to it? (currently it outputs 1 instead)

I get this warning as expected: shift.c:5:3: warning: left shift count >= width of type. 32 bits is a problem for a 32 bit data type - too big. — jim mcnamara
– jim mcnamara, Commented Jun 2, 2013 at 2:43
Possible duplicate of What does the C standard say about bitshifting more bits than the width of type? — phuclv
– phuclv, Commented Sep 8, 2018 at 5:56

caf · Accepted Answer · 2013-06-02 03:04:51Z

Shifting by a value that is equal or greater than the width of the promoted type of the left operand is undefined behaviour, so you must specifically test for and avoid this. In addition, a left-shift of a signed type that results in overflow is also undefined behaviour, so you need to also avoid a shift of 31, too:

printf("1<<(32-n):%d\n", (n > 1 && n < 33) ? 1 << (32-n) : 0);

This particular expression uses 0 for the cases that are otherwise undefined, but you can handle those differently if you need to.

and, for portability, instead of 32 use sizeof(int)*8 ... (As well as for variations of it like 33 ~= 1+sizeof(int)*8 etc...)
@technosaurus for portability, use sizeof(int)*CHAR_BIT instead. A byte is not always 8 bits

Stian Ellingsen · Accepted Answer · 2013-06-02 03:07:48Z

Since you're shifting 32-bit ints, shifting by 32 bits would result in a zero value. However, the bitshift operation of the CPU can only shift by 0 to 31 bits as anything else is generally not useful and would only complicate the computation.

The reason that the first example, 1<<32, seems to work, is that the compiler optimises this to 0 at compile time, while also printing a warning. The other example, 1<<(32-n), however, has a shift value that cannot be determined at compile time (thus no warning either). Instead, the CPU uses the result of the subtraction 32 - n == 32 for its shift operation, but the CPU only takes the five lowest bits and thus overflows to 0, and the result is 1 << 0 == 1.

To work around this, you will have to either special-case n == 0, use a wider data type, or simply use fewer bits.

Marc B · Accepted Answer · 2013-06-02 02:43:40Z

Don't be surprised. you're dealing with a 32bit int, so when you do 1<<32, you've shifted that set bit right off the end of the int and zeroed out the whole thing.

e.g. in binary:

 33222222 22211111 11111000 00000000 10987654 32109876 54321098 76543210 1: 00000000 00000000 00000000 00000001 ^--- position #32

Yeah, I understand how it works. The only thing I got confused is that why the two lines of code inside foo function behaves differently. Is there any way that I could make them behave to be the same?

Shafik Yaghmour · Accepted Answer · 2013-10-29 19:15:00Z

gcc is telling you what the problem is with the warning:

main.c:5:3: warning: left shift count >= width of type [enabled by default]

Your shifts need to be less than the size of the type otherwise it is undefined behavior. The C99 draft standard section 6.5.7 Bitwise shift operators paragraph 3 says:

[...]If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

Why is the first printf different from the second one? If you build using -fdump-tree-original you will see the following code generated for foo:

printf ((const char * restrict) "1<<32:%d\n", 0); printf ((const char * restrict) "1<<(32-n):%d\n", 1 << 32 - n);

It seems the first case it being optimized away to 0 which is consistent with undefined behavior, the compiler can do anything, including behavior that appears to work.

I saw the warning as well. But in this case I have to shift out the MSB bit 1 on purpose.
@QSortBSearch The problem is that shifting by >= to the width of the type is undefined behavior, which means any predictions about the output are impossible.

Sufian · Accepted Answer · 2014-07-10 06:27:28Z

According to the C standard ISO 9899:1999 Chapter 6.5.7 Bitwise shift operators:

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undeﬁned.

It is strange that the compiler treats the two expressions differently. But since this causes undefined behavior anyway, it's not a problem. What you need to do is to check the operands before evaluation to make sure it's a valid expression.

spiralmoon · Accepted Answer · 2013-06-02 16:33:05Z

I finally figure out a work-around solution, at least make the output identical.

#include <stdio.h> #include <string.h> void foo(int n){ printf("1<<32:%d\n", 1<<32); printf("1<<(32-n):%d\n", (1<<(31-n))<<1); } int main(){ foo(0); }

Collectives™ on Stack Overflow

Bitwise Leftshift (<<) strange behavior

6 Answers 6

3 Comments

Comments

1 Comment

2 Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

Comments

1 Comment

2 Comments

Comments

Comments

Linked

Related