3

I have a specific C bit-shifting scenario that I do not believe is covered on Stack Overflow yet. (If it is, I haven't been able to find it!)

This exercise is using signed ints as the data type.

Take the value 0x80000000 (which is just a 1 in the most significant bit.)

Shift it right once on a machine using arithmetic right-shifts (which mine does).

Result = 0xC0000000 (1100 0000 in leftmost byte).

Continue shifting it and you should be filling up with ones, from the left to the right.

Result = 0xFFFFFFFF (All ones.)

However: Try the same example but shift one extra position, all together:

0x80000000 >> 0x00000020 (Right shift 32 times)

Your result? I don't know. My result was not all ones. In fact, I got 0x00000001 which was NOT my desired behavior. Why is this? Is it machine specific?

(Context: Homework assignment limiting my operations to a few bit operators to solve a puzzle. This is an aspect to a puzzle but is far from the entire question.)

Mat
  • 202,337
  • 40
  • 393
  • 406
BlackVegetable
  • 12,594
  • 8
  • 50
  • 82
  • 3
    Heaven forbid that one day every single "bit shifting scenario" should be covered on Stack Overflow. We can help you *understand* C, but I sure hope we won't have to spell out every possible similar problem. – Kerrek SB Aug 27 '12 at 16:16
  • I'm sorry, if this is not an appropriate question, I will remove it. Can you clarify on why this question is an issue? – BlackVegetable Aug 27 '12 at 16:17
  • shift right just takes the 1 and move right not clone it so after shift one time 0x1000000 >> 1 ,, you get 0x0100000 – Rami Jarrar Aug 27 '12 at 16:17
  • 2
    @Rami, actually that depends on whether the value is signed or unsigned – Michael Goldshteyn Aug 27 '12 at 16:18
  • @RamiJarrar That is correct for logical right shifts, but my machine (and most, I believe) use arithmetic right shifts which copy the leftmost bit. – BlackVegetable Aug 27 '12 at 16:18
  • 1
    Don't worry, I was just amused by what sounded like a hope that there will eventually be one question for every type of bit shift on SO. The question is fine, though it's certainly one of many duplicates, and the answer would have been in any good C++ text book. – Kerrek SB Aug 27 '12 at 16:19

4 Answers4

6

It's undefined behavior

Why doesn't left bit-shift, "<<", for 32-bit integers work as expected when used more than 32 times?

which means you should avoid it like the plague. Here's some links including "What every C programmer should know about undefined behavior": http://lwn.net/Articles/511767/

Community
  • 1
  • 1
sourcejedi
  • 3,051
  • 2
  • 24
  • 42
  • Hey thank you. I am primarily a Java/C# programmer and am not used to "undefined behavior." I am getting a couple of C programming books in a month (birthday gifts!) but have yet to get the hang of the C/C++ mentality. Those articles look promising. – BlackVegetable Aug 27 '12 at 16:23
5

Shifting by the number of bits of the operands has undefined behavior, which is why you're getting "unexpected" results.

unwind
  • 391,730
  • 64
  • 469
  • 606
  • I realize this is a silly situation, and in a real programming setting, something to be avoided, but is there any way to know what is going on internally here? – BlackVegetable Aug 27 '12 at 16:20
  • This can be easily analyzed by means of disassembly and gdb, but I would not spend time on that ;) – Andrejs Cainikovs Aug 27 '12 at 16:23
  • 1
    If you want the machine-specific answer, what's happening is that the CPU shift instruction only looks at the low 5 bits of the shift value, and ignores the high bits. – sourcejedi Aug 27 '12 at 16:29
  • @sourcejedi **That** was what I was looking for! Are you sure? – BlackVegetable Aug 27 '12 at 16:39
  • 2
    @BlackVegetable "underlying shift operations on various CPUs do different things with this: for example, X86 truncates 32-bit shift amount to 5 bits (so a shift by 32-bits is the same as a shift by 0-bits)" blog.llvm.org/2011/05/what-every-c-programmer-should-know.html – sourcejedi Aug 28 '12 at 18:48
  • Turns out some processors shift 6 bits, so on such a machine, it would fill the bits with all 0s. I suppose it depends. – BlackVegetable Sep 04 '12 at 23:25
2

Here is a quote about this from the C99 standard:

6.5.7 Bitwise Shift Operators [...]

3 [...] 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.

With credit to the original source.

Michael Goldshteyn
  • 71,784
  • 24
  • 131
  • 181
1

You are not allowed to shift a value more than it's width. How much is the with of an int number ? Well, in a 32-bit system it's 32 bit. If you try to shift an int with more than 32 in gcc, you get this warning :

warning: right shift count >= width of type [enabled by default]

If you want to get 0xFFFFFFFF you have to shift if 31 times, not 32 times. Think about it !

Rsh
  • 7,214
  • 5
  • 36
  • 45
  • You are *allowed* to shift a value more than it's width, and GCC gives just a *warning*. The question was not about that. – Andrejs Cainikovs Aug 27 '12 at 16:37
  • No, I understand that. The exact way I am trying to solve this puzzle involves bit shifting 32 times, but now I see that is completely a bad idea. Even in a silly academic puzzle-solving setting. – BlackVegetable Aug 27 '12 at 16:38
  • @AndrejsCainikovs yes, it is allowed and as we can see it just gives a warning. But does it make any sense to shift it more than 32 bits ? – Rsh Aug 27 '12 at 17:39
  • Yes, it makes sense if you are doing math computing. Unfortunately due to this and other undefined behavior root causes, it is required to implement workarounds and do calculation often in a non-straightforward way. – Andrejs Cainikovs Aug 28 '12 at 09:04