C rotate bitfield (explanation needed)

Question

I want to rotate a byte 1 bit to the left. I was looking at several examples from this site and came across this code. Though it works, I'd appreciate any step by step into how does it works.

unsigned int _rotl(const unsigned int value, int shift) 
{
    if ((shift &= sizeof(value)*8 - 1) == 0)           //What does this do?
      return value;
    return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

First of all, what does the first part does? And for the last part wouldn't shifting by that much you'd pretty much be erasing some of the bits?

For example:

Say

value= 0x50    //01010000
shift = 4

I'll have for

value << shift

01010000 << 4  =>   00000000

And for value >> (sizeof(value)*8 - shift)

01010000>> (4*8 - 4)   => 00000000

So doing the OR operation for both would give me 0. My understanding is wrong obviously, but I'd appreciate anyone 'dumbing' it down for a begginer like me. Thanks.

Answer 1

unsigned int _rotl(const unsigned int value, int shift) 
{
    // If all bits in value are zero, do nothing and return
    int bitmaskOfAllOnes = sizeof(value)*8 - 1;
    if ((shift &= bitmaskOfAllOnes) == 0)           //What does this do?
      return value;

    // Shift value to the left
    (value << shift) 
    // shifting right to handle the wrap around
    | (value >> (sizeof(value)*8 - shift));
}

e.g. using 16-bit ints 
value = 0x1001
shift = 4
sizeof(value) => 2
//sizeof(value)*8 - 1 => 0xffff
sizeof(value)*8 - 1 => 15 Decimal
shift &= bitmaskOfAllOnes => 0x1001 (i.e. not zero)
value << shift => 0x0010
sizeof(value)*8 - shift => 12
value >> (sizeof(value)*8 - shift) => 0x001
0x0010 | 0x001 => 0x0011

Answer 2

Let's take it step by step:

unsigned int _rotl(const unsigned int value, int shift) 
{
  if ((shift &= sizeof(value)*8 - 1) == 0)           //What does this do?
    return value;
  return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

First line:

if ((shift &= sizeof(value)*8 - 1) == 0)           //What does this do?

This statement is an optimization and a check rolled into one line. It returns TRUE if one of two conditions is met:

1. Shift is zero (i.e. don't rotate any bits)
2. The number of rotations specified by shift would have no effect

That statement returns FALSE otherwise, but also calculates the minimum number of rotations necessary to achieve the desired result, and stores that value in shift. In other words, it calculates shift = shift % size_of_integer_data_type.

For example, if you have a 32-bit integer, then rotating it by 32 bits does nothing. If you rotate it by 64, 96, or any other multiple of 32, that also accomplishes nothing. If the effect of our rotation does nothing then we save ourselves a lot of time and just quit early.

However, we might also specify a lot more work than is necessary. If you have a 32-bit integer, then rotating it by one bit has the same effect as rotating it by 33 bits, or by 65 bits, or 97 bits, etc. This code recognizes this fact, so if you specify shift as 97, it reassigns shift=1 and cuts out the extraneous rotations.

The statement sizeof(value)*8 - 1 returns one less than the number of bits in the representation of value. For example, if sizeof(value) evaluates to 4 (which it will on a system with 32-bit integers), then 4*8 - 1 = 31.

The &= operator is a bitwise-AND with assignment. This means we're doing a bitwise-AND between shift and sizeof(value)*8 - 1 and assigning that result to shift. As before, the right hand side of that expression is equal to the number of bits in value minus one. Thus, this has the effect of masking out all bits of shift that are greater than the size of the representation of value, which in turn has the effect of computing shift = shift % size_of_integer_data_type.

To be concrete, reconsider the 32-bit case. As before, sizeof(value)*8-1 evaluates to 31. Bitwise, this value is 0000 0000 0000 0000 0000 0000 0001 1111. That value is bitwise-ANDed with shift. Any bits in shift's 6th to 32nd positions are set to zero, while the bits in the 1st to 5th positions are unchanged. If you were to specify 97 rotations the result would be one.

  0000 0000 0000 0000 0000 0000 0110 0001 (97)
& 0000 0000 0000 0000 0000 0000 0001 1111 (31)
=========================================
  0000 0000 0000 0000 0000 0000 0000 0001 (1)

The last thing to do here is to recall that, in C, the return value of an assignment statement is the value that was assigned. Thus, if the new value of shift is zero, then we return immediately, otherwise we continue.

Second line:

return (value << shift) | (value >> (sizeof(value)*8 - shift));

Since C doesn't have a rotation operator (it only has left and right shifts) we have to compute the low-order bits and the high-order bits separately, and then combine them with a bitwise-OR. This line is a simple matter of calculating each side separately.

The statement value << shift calculates the high order bits. It shifts the bit pattern to the left by shift places. The other statement calculates the low order bits by shifting the bit pattern to the right by size_of_integer_type - shift bits. This is easy to see in an example.

Suppose that value has the decimal value 65535 and that shift has the value 26. Then the starting value is:

  0000 0000 0000 0000 1111 1111 1111 1111 (65535)

The left shift gives us:

  1111 1100 0000 0000 0000 0000 0000 0000 (65535 << 26)

The right shift gives us:

  0000 0000 0000 0000 0000 0011 1111 1111 (65535 >> 6)

Then the bitwise-OR combines these results:

  1111 1100 0000 0000 0000 0000 0000 0000 (65535 << 26)
| 0000 0000 0000 0000 0000 0011 1111 1111 (65535 >> 6)
=========================================
  1111 1100 0000 0000 0000 0011 1111 1111 (65535 rot 26)

You could re-write this code and achieve the same correct result:

unsigned int _rotl(const unsigned int value, int shift)
{
    //Assume 8 bits in a byte
    unsigned bits_in_integer_type = sizeof(value)*8;
    shift = shift % bits_in_integer_type;

    if( shift == 0 ) return value; //rotation does nothing

    unsigned high_bits = value << shift;
    unsigned low_bits = value >> (bits_in_integer_type - shift);

    return high_bits | low_bits;
}