1

I am trying to clearly understand the behaviour of the shift operators (especially for the boundary cases), so I devised a little test written in C++.

    int a = odd_value; //321 in my case but it should not matter (the last bit to be 1)
    print(0, a);

    a = a << 31; // (this gives a segmentation fault, as normal because it tries the sign bit becomes 1 but all the other bits are 0).
    print(0, a); //the segmentation fault happens here - it prints the minimum integer value and then gives the fault
    a = (a << 1) + 1; // but if then I do this, shouldn't it set a to -1 ??
    print(a); //gives 0

   void print(int stackCallIndex, int nb)
   {
     if(nb)
     {
        print(++stackCallIndex, nb >> 1);
        if(nb & 1) printf("%d", 1);
        else       printf("%d", 0);

        if(stackCallIndex % 8 == 0) printf(" ");
     }
   }
Slow Trout
  • 492
  • 3
  • 13
  • This is what I get if I try to print a just after the bitshift. Let me edit the post so it's a bit clearer. – Slow Trout May 23 '15 at 00:19
  • 3
    You should never get a segmentation fault from printing an `int` O.o – AliciaBytes May 23 '15 at 00:19
  • What compiler are you using? – Scott Hunter May 23 '15 at 00:20
  • 1
    @SlowTrout What is the actual value of `a`, and how are you defining `print`? – jwodder May 23 '15 at 00:21
  • The shift operator wouldn't generate the segmentation fault. If print expects a char* (string), or maybe an integer that you try printing as a string, then naturally blammo. – Ron Kuper May 23 '15 at 00:23
  • My bad. The segmentation fault is happening when trying to print the binary form of the integer. I will add the print function just now. – Slow Trout May 23 '15 at 00:24
  • @SlowTrout wait, do you even get any output? To me it looks like infinite recursion for negative numbers... – AliciaBytes May 23 '15 at 00:31
  • Raphael Miedl, you are just right. I have just put a print inside the function and indeed it is an infinite recursion - i've missed this. Though by adding a new bit at the end should it show -1? 1(30 x 0)1 – Slow Trout May 23 '15 at 00:33

3 Answers3

3

If you want the standard behavior, then it's undefined. According to [expr.shift]:

The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, [...]. Otherwise, if E1 has a signed type and non-negative value, and E1×2E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

Any (odd number > 1) x 231 is not representable by uint32_t, so the behavior is undefined. Your compiler apparently chooses to implement this as a segmentation fault, which is perfectly conforming behavior (edit: er, at least it would be, if that were where it is happening).

A more typical approach would be just to let bits "fall off" the end. That is, a << 31 for an odd number would become 0x80000000. But even in that case, another left-shift of 1 would result in 0, so you'd have to subtract 1 to get -1, not add 1.

Barry
  • 286,269
  • 29
  • 621
  • 977
  • Strictly according to standard, yes. Doubt any compiler actually does that though and I'd guess for infinite recursion with OP's no added code. – AliciaBytes May 23 '15 at 00:30
  • This makes sense.Can you please point me out towards the documentation you have just posted. There are tones of posts across the web, but no one fully explains the boundary cases. – Slow Trout May 23 '15 at 00:31
  • @SlowTrout The reference is from the C++ standard, in this case specifically revision N4140. – Barry May 23 '15 at 01:05
3

According to your code I'd bet on a stackoverflow due to infinite recursion if you try to print negative values.

   void print(int stackCallIndex, int nb)
   {
     if(number)
     {
        print(++stackCallIndex, nb >> 1); // likely an infinite recursion here.
        if(nb & 1) printf("%d", 1);
        else       printf("%d", 0);

        if(stackCallIndex % 8 == 0) printf(" ");
     }
   }

so why would it be infinite recursion? Strictly according to standard right shifting negative signed integers is implementation defined.

In most implementations it will do an arithmetic right shift, meaning that 1111 1100 (-4 in two's complement 8bit) shifted to the right by 1 would result in 1111 1110 (-2 in two's complement 8bit) as you can see you always fill up the sign bit again so your number would never get to 0 and the if condition is always true.

Generally doing bit manipulation on signed values is a bad idea, they involve implementation/undefined behavior in a few cases. Better cast all values to unsigned before using bit manipulation.

AliciaBytes
  • 7,300
  • 6
  • 36
  • 47
  • So it will never go to 0 because the sign bit is always preserved? – Slow Trout May 23 '15 at 00:47
  • @SlowTrout Yes. Try changing the parameter from `int nb` to `unsigned nb` and it should work. – AliciaBytes May 23 '15 at 00:50
  • It does. Thanks a lot. Can you please point me towards a sound piece of documentation regarding these operators? – Slow Trout May 23 '15 at 00:52
  • Sadly [the standard](http://stackoverflow.com/a/4653479/1942027) would probably be the best here (although hard due to the legalise writing style). You can find the shift operators by searching `expr.shift`. I usually use [cppreference](http://en.cppreference.com/w/) as a easier reference but I don't find it's pages about the built in operators all that good... – AliciaBytes May 23 '15 at 01:03
1

When I try that I get -214783648 which is the smallest known value in integer... this means that you are making an integer bigger than the allowed range that's why in your case you get a segmentation fault...

Good Luck
  • 1,104
  • 5
  • 12