Left shift bits in c

Question

I have been making some stupid test about bits manipulation, and I found this issue. I execute this code:

int main(){
  unsigned int i;
  for (i=1; i<34; i++)
  {
    unsigned long temp = i;
    unsigned long mul = 1;
    unsigned long val;
    unsigned long one = 1;

    // Way 1
    while (temp--)
      mul = mul << one;

    // Way 2
    val = (one<<i);

    printf(" \n 1<<%i \n mul: 0x%X , val: 0x%X\n",i, mul, val); 
  }
}

Of course, I know that when i>31, an overflow will be produced. I think that both parts of code (way1 and way2) should output the same result. But I get this (at the end):

 /* ... correct results from i=1 to i=31 ... */
 1<<30 
 mul: 0x40000000 , val: 0x40000000 

 1<<31 
 mul: 0x80000000 , val: 0x80000000 

 1<<32 
 mul: **0x0** , val: **0x1** 

 1<<33 
 mul: **0x0** , val: **0x2**

Why, if both instructions are left shifts, the program produces different outputs? It seems that the part way2 produces a round shift, but I don't know why, I really think that "mul" gets always the correct value.

I compile under a Intel 32bits machine, gcc version 4.4.7

The result of a shift operations with a shift amount larger than the operands width is undefined per C standard. — Eugene Sh., Jun 21 '16 at 15:52
Just an opinion, but I'd say that in these cases: `mul << one` and `one< — Michael Burr, Jun 21 '16 at 15:53
That's the problem, yes. In this case, it probably ANDs the right operand with 0x3F before doing the shft. — Mr Lister, Jun 21 '16 at 15:54
@MichaelBurr The main problem with that is that `one` is a variable, not a constant. — Mr Lister, Jun 21 '16 at 15:55
@EugeneSh.: It's not just the result that's undefined. The *behavior* is undefined. And a shift with a right operand greater than *or equal to* the width of the left operand's type, the behavior is undefined. — Keith Thompson, Jun 21 '16 at 16:03
Possible duplicate of [Why doesn't left bit-shift, "<<", for 32-bit integers work as expected when used more than 32 times?](http://stackoverflow.com/questions/7401888/why-doesnt-left-bit-shift-for-32-bit-integers-work-as-expected-when-used) — anatolyg, Jun 21 '16 at 16:04
In addition to the UB for the shift, your `printf` also invokes undefined behaviour. — too honest for this site, Jun 21 '16 at 16:20

score 9 · Answer 1 · answered Jun 21 '16 at 15:53

9

Probably because that's undefined behaviour? According to §6.5.7:

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.

answered Jun 21 '16 at 15:53

Aif

11,015
1
30
44

Well, I could expect some of both behavior, but only one of them in both cases. Don't you think that both operations are equal? EDIT: I see the deepmax answer and I understand you now. Thanks! – Alexi Jun 21 '16 at 16:13
@Alexi Do you understand the meaning of something being undefined? – Eugene Sh. Jun 21 '16 at 16:18
@EugeneSh. Yes, my problem was that I understood the "undefined behavior" meaning, but I didn't know why there were two diferents "undefined behavior" whith the (aparently) same operation. – Alexi Jun 23 '16 at 06:55

masoud · Accepted Answer · 2016-06-21T18:56:43.427

2

In case of

val = (one<<i);

when i gets greater than or equal to 32, the behavior is undefined.

However, in case of

while (temp--)
   mul = mul << one;

for shifts more than 32, it will shift zero and the result is defined (zero).

edited Jun 21 '16 at 18:56

answered Jun 21 '16 at 15:57

masoud

55,379
16
141
208

Yes. I think you are right. With the answer of Aif I think it is clear. Thanks a lot! – Alexi Jun 21 '16 at 16:18

score 0 · Answer 3 · answered Jun 21 '16 at 16:45

When you do this:

val = (one<<i);

You're doing a single left shift by i. If i is greater than 31, this results in undefined behavior, meaning the result may or may not be what you expect.

From section 6.5.7.3 of the C standard:

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

However, when you do this:

while (temp--)
  mul = mul << one;

You're doing a left shift by 1 i times. This is well defined, so it gives you the value you expect.

Also, you're using %X to print a long when you should be using %lX. This causes undefined behavior as well.

score -3 · Answer 4 · answered Jun 21 '16 at 16:02

-3

When I compile Your code with -Wall I got complaints:

BASH> gcc -Wall left-shift.c 
left-shift.c: In function ‘main’:
left-shift.c:21:12: warning: format ‘%X’ expects argument of type ‘unsigned int’, but argument 3 has type ‘long unsigned int’ [-Wformat=]
     printf(" \n 1<<%i \n mul: 0x%X , val: 0x%X\n",i, mul, val); 
            ^
left-shift.c:21:12: warning: format ‘%X’ expects argument of type ‘unsigned int’, but argument 4 has type ‘long unsigned int’ [-Wformat=]

So I changed printf to

printf(" \n 1<<%i \n mul: 0x%lX , val: 0x%lX\n",i, mul, val);

With this change "mul" and "val" shows the same results:

 1<<30 
 mul: 0x40000000 , val: 0x40000000

 1<<31 
 mul: 0x80000000 , val: 0x80000000

 1<<32 
 mul: 0x100000000 , val: 0x100000000

 1<<33 
 mul: 0x200000000 , val: 0x200000000

System information:

BASH> gcc --version
gcc (Ubuntu 5.3.1-14ubuntu2.1) 5.3.1 20160413
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
BASH> uname -a
Linux bm-pc-ubuntu 4.4.0-24-generic #43-Ubuntu SMP Wed Jun 8 19:27:37 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux
BASH> lsb_release --all
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 16.04 LTS
Release:    16.04
Codename:   xenial

answered Jun 21 '16 at 16:02

Boris Mühmer

476
3
10

This is because your machine is 64-bit and his is 32-bit. – s7amuser Jun 21 '16 at 16:04
Ignoring this warning, gives me even strnager output than the original ones: 1<<30 mul: 0x40000000 , val: 0x40000000 1<<31 mul: 0x80000000 , val: 0x80000000 1<<32 mul: 0x0 , val: 0x0 1<<33 mul: 0x0 , val: 0x0 – Boris Mühmer Jun 21 '16 at 16:06
You should not ignore the warning. If you want to see results similar to the OP, try increasing the loop counter to 66. – s7amuser Jun 21 '16 at 16:08
This is awesome... even if absolut logical! Is there a gcc switch to "warn about undefined behaviours"? – Boris Mühmer Jun 21 '16 at 16:21
@s7amuser: The wrong type-specifier invokes UB even on a 32 bit machine, where `int` and `long` have the same width. – too honest for this site Jun 21 '16 at 16:24
@bsmr: You already got warnings for detected UB. But how should the compiler be able to warn about UB at run-time without solving the Halting Problem? – too honest for this site Jun 21 '16 at 16:25
@Olaf I don't see how your comment relates to my comment. I didn't suggest ignoring the warning. – s7amuser Jun 21 '16 at 16:26
@s7amuser: Your comment invokes the impression the reason for the warnings is the machine OP works on (64 vs. 32 here). That is wrong. It should warn even if both types have the same representation/range, as that UBN is not dependent on the representation, but the type. – too honest for this site Jun 21 '16 at 16:33
@Olaf Again, *I didn't suggest ignoring the warning* and *I didn't say the warning is because the machine word size* (this is only your wrong interpretation). The reason the OP *gets different results* is because the machine word size. The warning is *not* dependent on the machine word size. I hope everything is clear now. – s7amuser Jun 21 '16 at 16:42

Left shift bits in c

4 Answers4