Bitwise circular rotation

Bitwise rotation is a method widely use in computer science, the mainly reason using Bitwise instead of normal arithmetic is it provides a highly performance in the program.

Basic concept

In basic part of bitwise operation, we’ll have two flag in the number: MSB (most significant bit), LSB(least significant bit). Suppose a bitwise number 0011 1001, left most bit will mostly set as MSB, right most bit will be the LSB instead.

If operating a left circular rotation on the number 1101 0010 will become 1010 0101 because the of the operation which display in the figure below.

1 time left circular rotation

Implement in c

After understanding the basic operation of the bitwise circular rotation, it’s not hard to implement the basic circular bitwise rotation. In c language, it only provides the non-circular bitwise rotate operator >>and <<, so the circular bitwise rotation will need to implement by basic shift operator.

The easiest way to implement circular bitwise rotation is to shift the bits we expect, then make the removed bits go back to the head/tail of the number.
We’ll still take number 1101 0010 as example. suppose we’ll want to do 3 bits left circular shift the operation will be like the figure below.

Or we can simplify the operation like the figure below

full operation

So we can simply implement the code like below

unsigned int _8bit_rotl(unsigned int word, unsigned int shift) {
    return ( (word << (shift & 7)) | ((word >> ((8-shift) & 7)));
}

In Linux

While the code above seems perfect, but in linux kernel, the rol/ror function didn’t implement like this

How comes the 8-shift same as -shift ????

The figure below will proof how the negative operator works.

In computer, the negative will operate like bitwise not then addition 1, meanwhile suppose a unsigned int number a as 5, a+a’+1 will be 2⁶⁴
As we operate bitwise not and addition 1, and bitwise and with the mask 7, the result will become the same as (8-a)

So the proof above shows how -shift works.

Hope this introduction helps you understanding about the bitwise rotation, enjoy :)