Bit Manipulations - rotateLeft

Question

The goal is to write a method that moves n number of bits in a 32 bit machine to the left by only using ~, !, |, &, ^, +, >>, << (no for loops, if statements, so on...). I think that what I've got should work. My problem is that the variable move_left seems to not behave properly. Here is my code which is broken down into steps in order for me to track down the problem:

int rotateLeft(int x, int n) 
 {
     int move_left = (0x20 + (~n + 1)); // 32 - n
     int expr1 = x >> n; // chopping off n bits on the right
     int expr2 = ~((~0x0) << n); // n number of 1s on the right
     int expr3 = expr2 & x; // the bits that now need to be on the left
     int expr4 = expr3 << move_left; // the correct bits on the left
     int expr7 = ~0x0 << move_left; // breaking down expr5
     int expr5 = (~((~0x0) << move_left)); //
     int expr6 = expr5 & expr1; // copying the right sided body
     int result = expr6 | expr4; //adding the left side

     printf("%d\n%d\n%d\n%d\n%d\n%d\n", move_left, expr1, expr7, expr5, expr6, expr4);

     return result;
 }

When testing with rotateLeft(-2147483648[0x80000000],0[0x0]) the result, however, is incorrect. When tracking down my arguments, the print is:

32
-2147483648
-1
0
0
0

I do not understand how move_left is 32 (which is right), but ~0x0 << move_left is somehow -1 when it should be 0! (When I substitute left_right with 0x20 in expr7, then it prints 0 correctly.)

I appreciate any help!

possible duplicate of [Bitwise rotate left function](http://stackoverflow.com/questions/10134805/bitwise-rotate-left-function) — CrazyDart, Feb 05 '15 at 19:41
Why are you allowed to use `~`? It's not on your list of permissible operations. — EOF, Feb 05 '15 at 19:49
EOF, we are allowed to use it! Whoops, will add it to my question. — Sasha, Feb 05 '15 at 19:51

score 1 · Accepted Answer · answered Feb 05 '15 at 20:26

From the C99 standard, clause 6.5.7 (3), on bitshift operators:

(...) 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.

As you have experienced, this is not a purely theoretical concern; there are platforms on which bitshift operations with operands outside this range do any number of things because it was easier/faster/more efficient/required less space to build the hardware that way. But it doesn't end there. Quoth 6.5.7(4):

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeroes. If E1 has an unsigned type, the value of the result is E1 x 2^E2, reduced modulo one more than the maximum value representable in the result type. If E1 has signed type and nonnegative value, and E1 x 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

and (5):

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Often a signed left shift beyond the defined range will behave predictably, and there will often be sign-extension on a signed right shift (meaning that ones are shifted in for negative values and zeroes for positive ones), but you can't depend on that.

Long story short: If you're trying to use bitshifts with signed integer types, you're gonna have a bad time. Use unsigned int for everything, including literals on the left side of a shift (for example, use ~0u instead of 0) and take care that your right-hand side operands remain in the legal range.

So how do you do the last bit without if and ?:? One way is to split the shift:

 unsigned int expr1 = (x >> (n & 0xf)) >> (n & 0x10);
 unsigned int expr2 = ~((~0u << (n & 0xf)) << (n & 0x10));

This works because (n & 0xf) + (n & 0x10) == (n & 0x1f) and ((x >> a) >> b) == (x >> (a + b)). I'm assuming unsigned x here, otherwise you need a cast.

I can think of simpler ways to do leftwise rotation, but, well, it's your homework.

thank you, sir! I am not allowed to use unsigned but at least I now understand the issue — Sasha, Feb 05 '15 at 21:14

score 0 · Answer 2 · answered Feb 05 '15 at 20:15

Your code is really complicated for task of left rotation. What I see in your code, that can be a problem, is a data type. When signed int is shided rignt sign bit is coppying, e.g. the foolowing code

    int x = 0x80000000;
    x >>=3;
    printf("%X\n", x);

prints result:

F0000000

But if data type is changed to unsigned:

    unsigned int x = 0x80000000;
    x >>=3;
    printf("%X\n", x);

result will be:

10000000

So, try to output in hexadecimal to see what happened, and then try to use unsigned type to change bitwise operations logic.

Bit Manipulations - rotateLeft

2 Answers2