Circular shift in c

Question

How does the following code work and what do the variables mean:

y = (x << shift) | (x >> (sizeof(x)*CHAR_BIT - shift));

I found in a circular shift article but with no explanation on how this works.

Solution 1

CHAR_BIT is the number of bits per byte, should be 8 always.

shift is the number of bits you want to shift left in a circular fashion, so the bits that get shifted out left, come back on the right.

     1110 0000 << 2 results in:
     1000 0011

code for the example:

   y = (x << 2) | (x >> (8 - 2));

Solution 2

This is a method of doing a circular shift. Suppose that x is 8 bits.

+----+----+----+----+----+----+----+----+
| x1   x2   x3   x4   x5   x6   x7   x8 |
+----+----+----+----+----+----+----+----+

Then, shifting it left by 3 gives us:

+----+----+----+----+----+----+----+----+
| x4   x5   x6   x7   x8    0    0    0 |
+----+----+----+----+----+----+----+----+

Now, CHAR_BIT*sizeof(x) is the same as the width of x in bits, 8. So shifting x to the right by 8 - 3 gives us:

+----+----+----+----+----+----+----+----+
| 0    0    0    0    0    x1   x2   x3 |
+----+----+----+----+----+----+----+----+

And taking the OR you get:

+----+----+----+----+----+----+----+----+
| x4   x5   x6   x7   x8   x1   x2   x3 |
+----+----+----+----+----+----+----+----+

This is technically non-portable because it is non-portable to shift by an amount equal to the width of the type -- so if shift is 8, then the left shift is wrong, and if the shift is 0, then the right shift is wrong. However, this works in practice on all three common behaviors when shifting by the type width. (In practice, the shift amount is reduced by some modulo -- either the bit width of the type or some larger number.)

It is called a circular shift or "rotation" because the bits that get shifted out on the left get shifted back in on the right.

Sophisticated compilers will actually compile the code down to a hardware rotation instruction.

Solution 3

(x << shift) 

Shifts it 'shift' number of bits to the left, returns the shifted out bits

(x >> (sizeof(x)*CHAR_BIT - shift));

Makes space for accommodating those bits

CHAR_BIT is the number of bits in char, so is 8 mostly. In C, you don't handle one bit at a time, but at a minimum, char number of bits. So that is the granularity you get.

In general,

For a char, when you do a bit-rotate, you would do it on an 8-bit field (1 byte)

For an int, when you do a rotate, you would do it on a 32-bit field (4 bytes)

---

Example with 8 bits:

x = 11010101
shift = 2
x << (shift) = 01010100 //shifted left by 2 bits
= x >> ((1 * CHAR_BIT) - shift)
= x >> (6) 
= 00000011 //shifted right by 6bits

OR these bit-wise to give

01010100 //x << 2
00000011 //x >> 6
________
01010111

That is the circular shifted value by 2 bits

Solution 4

This works with unsigned types only. In the case with a signed negative number most left bits will be substituted by the value of most significant bit (with 1-s) by the right-shift operator (">>")

I'd write it like this:

y = (x << shift) | ( (x >> (sizeof(x)*CHAR_BIT - shift)) & (0x7F >> (sizeof(x)*CHAR_BIT - shift) );

In here before "|" operator we do confirm that first n bits ( n = sizeof(x)*CHAR_BIT - shift) are zeroed. We also assume, that x is short (2-bytes long). So, it's also type-dependent.

View more solutions

Comments

[user1809300]

and if i want to cirlular shift a number with a bitstream of 10 digits ex 1111101010 then CHAR_BIT is 10 or i am wrong?

[xanatos]

CHAR_BIT is always 8 for any sane architecture you'll use in the 21st century :-)

[user1809300]

i have a question : when i m using the << command for 10101 it gives 1010100 instead of 10100 why?

[Anirudh Ramanathan]

@user1809300 That is because of 8 bit granularity. 10101 is 00010101. The example above doesn't apply directly to C. It just illustrates how it works. In C/C++, you would deal with 8 bit chars at a time.

[Anirudh Ramanathan]

@user1809300 I don't understand. What input did you give and what did you get as the result?

[user1809300]

and the result was 84 insead of 20

[Anirudh Ramanathan]

@user1809300 And x was? Also, see updated example above. I made it 8bits. was too confusing previously.

[Anirudh Ramanathan]

@user1809300 84 is correct, if you are rotating left. 00010101. Rotate this by 2 bits, you get 01010100 which is 84. Rotate-left v/s Rotate-right probably is making this harder to understand?

[Anirudh Ramanathan]

let us continue this discussion in chat

[Pascal Cuoq]

+1, but 8 is not a good example of amount by which it is undefined to shift, because per usual arithmetic conversions, the shifted type is at least (signed or unsigned) int, and int is at least 16 bits.

[fujianjin6471]

@PascalCuoq x >> 8 - 2 is parsed as x >> (8 - 2) with a warning: operator '>>' has lower precedence than '-'; '-' will be evaluated first [-Wshift-op-parentheses]

[Pascal Cuoq]

@fujianjin6471 Indeed. I have deleted my comment, but I would say it is as well the parentheses stay in the answer, seeing how the people less familiar with C get confused otherwise.

[Leopoldo Sanczyk]

Nice warning about unsigned types!

[sudoCoder]

Very good explanation, but I am facing a problem while doing bit-wise left shift. The compiler seems to take the bits in group of 32 but I need to work only on 8 bits while doing the cyclic left shift. This means 1111 0000 when shifted to left by 1 should give 1110 0001 instead of 1111 00000 as it gives now by the compiler. Can you help?