8051 Micro-controller, C Language, C++, communication protocol, Operating System

5 way to reverse bits of an integer

aticleworld.com





In the interview generally, bit reversal is the common question for the interviewer. There are several methods to reverse the bits of an integer.

If you have good knowledge of unary operators then bit reversal is a very simple question for you otherwise, it can be difficult.
So it is my personal advice before looking the example code read the unary operators and try this yourself first.

Note: Quiz on bit-wise operators.

Before going to example code I am discussing bit-wise operator which are frequently used in below example code.

There is some important list of the bitwise operator.

     Operator

           Meaning

|   (Bitwise OR)   Use to Set a Bit of a Register.

 

&  (Bitwise AND)    Use to check a Bit of Register.

 

^  (Bitwise EX-OR)    Use to toggle a Bit of a Register.

 

~  ( Bitwise complement)     Use for the compliment.
<< (Shift left)     Use to shift a sequence of Bit toward left.
>> (Shift right)     Use to shift a sequence of Bit toward Right

 

Note: In the c language, printf lacks the ability to print the data in binary format. So here, I am creating a simple program to print the number in binary format.

Example code to print the data in binary format.

In below section, I am describing 5 ways to reverse bits of an integer.

First Method:

This is a simple method, we take an integer tmp and putting set bits of the num in tmp until the num becomes zero. When num becomes zero then shift the remaining bits of temp through the count.

Let assume here is a number num (short int) which contains a value 0000000000001100. First, we assign the num value to the tmp and get the LSB of num.

After that, we iterate a loop until the num becomes zero with putting set bits in tmp. When num becomes zero then left shift tmp 12 times to get the exact reverse number 11000000000000.

OutPut 1:





Second Method:

This method is similar to the first method. It is easy and less optimized as compared to the first method. In this method we take an integer tmp, putting set bits of num in tmp until the for loop runs. In every iteration of for loop we will shift the  tmp in left direction ( tmp << 1 ) and num in the right direction (num >> 1).

OutPut 2:

 

Third Method:

In this method, we will check the set bits of num and run the loop through all the bits of an integer. If we find the ith bits of num is set then just put 1 at the ((INT_BITS – 1) – ith ) position of tmp, where INT_BITS is the number of bits of an integer.

OutPut 3:

 

Fourth Method:

It is a very simple algorithm to reverse the bits of the 32-bit integer. This algorithm uses the eight constant value for the reversing of the bits and takes five simple steps.

In below section, I am describing the functioning of each step.

Steps 1:
num = (((num & 0xaaaaaaaa) >> 1) | ((num & 0x55555555) << 1));

This expression use to swap the bits.
Let an example, suppose num is 0100, after the above expression it will be 1000.

Steps 2:
num = (((num & 0xcccccccc) >> 2) | ((num & 0x33333333) << 2));

Above expression uses to swap the 2 bits of a nibble. Suppose num is 10 00, after the above expression, it will be 00 01.

Steps 3:
num = (((num & 0xf0f0f0f0) >> 4) | ((num & 0x0f0f0f0f) << 4));

Expression use to swaps the nibbles. like if num is 0011 0010 then after the above expression it will be 0010 0011.

Steps 4:
num = (((num & 0xff00ff00) >> 8) | ((num & 0x00ff00ff) << 8));

This statement  uses to swap the bytes of an integer. Let num is 00001000 00001100, after the above expression, it will be 00001100 00001000.

Steps 5:
((num >> 16) | (num << 16));

The above expression uses to swap the half-word of an integer. Means that if the num is 0000000011001110 1000100100000110, after the above result number will be 1000100100000110 0000000011001110.

OutPut 4:

 

Fifth Method:

This is the simplest method to reverse the bits of an integer. In which we create a table of the hex value from 0 to 255. In this method, we are performing the AND operation of data with 0xFF to calculate the index of the array.

In this algorithm, we need to calculate the index of the array (look-up table) four times to getting the appropriate value from the look-up table. After getting the corresponding value we perform the bit shifting operation to get the reverse value.

OutPut 5:

 




References: http://graphics.stanford.edu/~seander/bithacks.html#SwappingBitsXOR

1 Comment

  1. sandeep

    thanks for the question

Leave a Reply

Theme by Anders Norén