Reverse Bits
August 6, 2011 in bit operations
Reverse bits of an unsigned integer.
There are several methods of reversing the bits of an unsigned integer. Here, we devise an algorithm using the XOR swap trick, and then optimize it using a divide and conquer methodology.
Hint:
How do you swap the ith bit with the jth bit? Try to figure out if you could use the XOR operation to do it.
The XOR swap trick:
Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits. The trick is to implement a function called swapBits(i, j), which swaps the ith bit with the jth bit. If you still remember how XOR operation works: 0 ^ 0 == 0, 1 ^ 1 == 0, 0 ^ 1 == 1, and 1 ^ 0 == 1.
We only need to perform the swap when the ith bit and the jth bit are different. To test if two bits are different, we could use the XOR operation. Then, we need to toggle both ith and jth bits. We could apply the XOR operation again. By XOR-ing the ith and jth bit with 1, both bits are toggled.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | typedef unsigned int uint; uint swapBits(uint x, uint i, uint j) { uint lo = ((x >> i) & 1); uint hi = ((x >> j) & 1); if (lo ^ hi) { x ^= ((1U << i) | (1U << j)); } return x; } uint reverseXor(uint x) { uint n = sizeof(x) * 8; for (uint i = 0; i < n/2; i++) { x = swapBits(x, i, n-i-1); } return x; } |
The run time complexity using the XOR trick to reverse bits is O(n), where n is the total number of bits in an unsigned integer.
The divide and conquer approach:
Remember how merge sort works? Let us use an example of n == 8 (one byte) to see how this works:
01101001
/ \
0110 1001
/ \ / \
01 10 10 01
/\ /\ /\ /\
0 1 1 0 1 0 0 1The first step is to swap all odd and even bits. After that swap consecutive pairs of bits, and so on…
Therefore, only a total of log(n) operations are necessary.
The below code shows a specific case where n == 32, but it could be easily adapted to larger n‘s as well.
1 2 3 4 5 6 7 8 9 | uint reverseMask(uint x) { assert(sizeof(x) == 4); // special case: only works for 4 bytes (32 bits). x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1); x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2); x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4); x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16); return x; } |
Note:
These are not the only methods for reversing bits, and not necessarily the fastest way. For more ideas/algorithms to reverse bits, please visit Bit Twiddling Hacks.
john said on November 3, 2011
Can you explain the below more ? thanks.
x ^= ((1U << i) | (1U << j));
1337c0d3r said on November 3, 2011
@john:
This line:
x ^= ((1U < < i) | (1U << j));
simply means to toggle the ith and jth bits.
( ie, x = 1001,
--> x ^= ((1U < < 1) | (1U << 3))
--> x = 1001 ^ (1010)
–> x = 0011 )
This is possible because xor-ing a bit with 1 will toggle the bit.
Therefore, xor-ing itself with 1 both set on the ith and jth bit (white other bits are zeroes) will toggle only the ith and jth bits.
john said on November 4, 2011
thanks, 1337c0d3r.
I have thought 1U<<j means that the number j is shifted to left one bit. It should be the number 1 shift to left j bits. That makes sense for me now.
flo said on November 10, 2011
Thanks for the solution, never have imagined the O(log N) one.
Ankur said on November 11, 2011
Hi
How abt if we do the following ..
First take the NOT of the number say y = NOT(x)
and then x^y and then subtract x from this . This can also reverse the bits say ex
X=10110001
Y =NOT (X) = 01001110
X^Y = 11111111
X^Y -X = 010011110 — Answer
Is this wat is meant by reversing the bits . Please tell
1337c0d3r said on November 11, 2011
Your method is inverting the bits, which can be done in one operation, ie, ~X. Reversing the bits is like reversing a string, ie: 0010 -> 0100
Sonali said on December 29, 2011
Isnt this is o(nlogn) solution instead do o(logn)
Balaji said on January 3, 2012
How about this – we can compare the 1st and 32nd bit, 2nd and 31st bit and so on… if they are same then no need to do anything, if they are different then flip them:
int reverse_bits(int a){
for(i=1;i<=32/2;i++){ // assuming ints are 32 bits- use sizeof(int)
if(a&1<<i == (a&1<>32-i) //if ith bit and 32-i th bit are same
continue;//no need to do any thing
else{ // if they are different, then flip both bits
a^1<<i;
a^1<<32-i;
}
}
}
Balaji said on January 3, 2012
typo in the if condition:
if((a&1<>i == (a&1<>32-i)
(compare the number obtained by taking the i th and 32-i th bits and bringing them to 0th bit
)
Balaji said on January 3, 2012
my bit shift operators are disappearing
“typo in the if condition:
if((a&1\<\\>i == (a&1\<\\>32-i)
(compare the number obtained by taking the i th and 32-i th bits and bringing them to 0th bit
)”
mirokuneal said on January 6, 2012
For a O(n) approach, how about using the same way to reverse a number? Like this:
Is there any potential problem?
mirokuneal said on January 6, 2012
An easy-to-look version
unsigned int reverseBit(unsigned int x) {
unsigned int num = 0;
while( x > 0) {
int bit = x % 2;
x = x >> 1;
num = num * 2 + bit;
}
}
vq said on April 11, 2013
I just don’t understand, how the code reverse a number, is it saying, if given 115, it will return 511?
Gordon said on April 17, 2013
Do not use x % 2 , use x & 1
Do not use num = num *2 + bit , use (num << 1) & bit
All bit operations, should be faster than yours.
srikanth said on January 24, 2012
Isn’t reversing equal to doing a circular shift by length/2 ?
Matn said on February 8, 2012
If i can’t use numbers bigger than 0xFF in the code is it still possible to use the divide and conquer method ?
Karthick said on February 22, 2012
I think the following method can also be used to reverse bits though I am not sure if it is fail-proof. If there are loop-holes, then I would be glad,if someone could point them out.
Method:
1)Check the first and the last bit.
2) If they are same, continue.
3)Otherwise, swap them both using bitwise ‘OR’ of ‘AND’ correspondingly.
4)Continue until we get to the middle.
Code:
sandyfriend said on March 16, 2012
prefect list bySean Eron Anderson
http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
prashanth said on April 5, 2012
int bitrevert (int a)
{
x= 1<<0;
y = 1 << 31;
while (x<y)
{
if (a&x != a&y)
{
a= a^x;
a=a^y;
}
x= x<>1;
}
}
Karthik Rajendran said on August 19, 2012
excellent code
Jiefu zheng said on October 5, 2012
unsigned ReverseIntBit(unsigned x){
unsigned i = 1;
unsigned j = i << (sizeof(unsigned)*8-1);
while(i < j){
x ^= (x & i) ^ (x & j);
i <>= 1;
}
return x;
}
Yi Shan said on March 26, 2013
public static uint Reverse(uint num)
{
uint rnum = 0;
while (num > 0)
{
rnum = (rnum <>= 1;
}
return rnum;
}
nishant said on April 6, 2013
#include
using namespace std;
// flipping even bits of 32 bit number
int main()
{
int a = 5555;
cout<<hex<<a<<endl;
cout<<hex<< ((a&(~(a & 0xaaaaaaaa))) | ((~a) & (0xaaaaaaaa)))<<endl;
getchar();
}
Mukesh Barman said on April 28, 2013
The Divide and Conquer solution has O(nLogn) running time?
qinchen said on May 15, 2013
unsigned reverseBit(unsigned value)
{
unsigned answer = 0;
unsigned i;
for (i = 1; i > 0; i++) {
answer <>= 1;
}
return answer;
}