## Reverse Bits

August 6, 2011

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.

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 1```

The 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.

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.

VN:F [1.9.22_1171]
Rating: 4.7/5 (35 votes cast)
Reverse Bits, 4.7 out of 5 based on 35 ratings

### 49 responses to Reverse Bits

1. Can you explain the below more ? thanks.

x ^= ((1U << i) | (1U << j));

VA:F [1.9.22_1171]
+4
• @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.

VN:F [1.9.22_1171]
+3
2. 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.

VA:F [1.9.22_1171]
0
3. Thanks for the solution, never have imagined the O(log N) one.

VN:F [1.9.22_1171]
0
• The complexity for the divide-and-conquer strategy for bit reversal is O(n).
T(n) = 2T(n/2) = 2^2T(n/2^2) = …. 2^kT(n/2^k) where 2^k = n or k = log(n)

Thus T(n) = 2^k = n, and not just simply k = log(n)

VA:F [1.9.22_1171]
-1
• No, it is O(log(n)), not O(n). Forget your math that does not even match the operation describe here. I am sure you can count so please read the code and count the instructions. The method can be generalized for integer larger than 32 bits (assuming the number of bits are power of 2).

VA:F [1.9.22_1171]
0
• No, its actually O(N Log N). Its been well proven that the best case performance of a divide and conquer algorithm is N Log N. While no code was given for D&C approach, its easy to write up a high level rundown.
Until the termination condition is met
DIVIDE n into 2 sub-problems.
Recurse on first sub-problem n/2
Recurse on second sub-problem n/2
Merge sub-problems n/2 and n/2

T(n) = DIVIDE(n) + T(n/2) + t(n/2) + Merge(n)
Divide takes constant time. O(1). Merge takes linear time O(n). So we have
T(n) = 1 + 2*T(n/2) + n
or just
T(n) = 2T(n/2) + n
You can find the solution to that recurrence relation in any programming book or you can try to do it yourself, either way i guarantee the answer is O(N Log N) as the solution.

I don’t know if the original author made a typo, or was mistaken, but unless he can produce a constant time merge algorithm the answer remains O(N Log N).

VA:F [1.9.22_1171]
+1
4. 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

VA:F [1.9.22_1171]
0
• 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

VN:F [1.9.22_1171]
0
5. Isnt this is o(nlogn) solution instead do o(logn)

VA:F [1.9.22_1171]
+1
• it’s log(n), the same as binary search.

VN:F [1.9.22_1171]
-1
• Its not the same as binary search, the first n in O(n log n) comes from the merge function.
Binary search has O(Log n) time because it is only dividing, and once it is done its done. Divide and conquer has to divide (Log N ) AND Conquer (N).

D&C algorithms have a proven best case performance of O(N Log N)

VA:F [1.9.22_1171]
+1
6. 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;
}

}
}

VA:F [1.9.22_1171]
0
• 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
)

VA:F [1.9.22_1171]
0
• 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
)”

VA:F [1.9.22_1171]
0
7. For a O(n) approach, how about using the same way to reverse a number? Like this:

Is there any potential problem?

VA:F [1.9.22_1171]
+1
• 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;
}
}

VA:F [1.9.22_1171]
0
• I just don’t understand, how the code reverse a number, is it saying, if given 115, it will return 511?

VA:F [1.9.22_1171]
0
• 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.

VN:F [1.9.22_1171]
0
8. Isn’t reversing equal to doing a circular shift by length/2 ?

VA:F [1.9.22_1171]
-1
9. If i can’t use numbers bigger than 0xFF in the code is it still possible to use the divide and conquer method ?

VA:F [1.9.22_1171]
0
10. 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:

VN:F [1.9.22_1171]
0
11. prefect list bySean Eron Anderson
http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

VA:F [1.9.22_1171]
+2
12. 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;
}

}

VA:F [1.9.22_1171]
+1
13. excellent code

VN:F [1.9.22_1171]
0
14. 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;
}

VA:F [1.9.22_1171]
0
15. public static uint Reverse(uint num)
{
uint rnum = 0;
while (num > 0)
{
rnum = (rnum <>= 1;
}
return rnum;
}

VN:F [1.9.22_1171]
0
16. #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();
}

VA:F [1.9.22_1171]
0
17. The Divide and Conquer solution has O(nLogn) running time?

VN:F [1.9.22_1171]
+1
18. unsigned reverseBit(unsigned value)
{
unsigned answer = 0;
unsigned i;

for (i = 1; i > 0; i++) {
}
}

VA:F [1.9.22_1171]
0
19. Here’s mine in C:

VN:F [1.9.22_1171]
0
20. Sorry, the for() loops got completely messed up. Here it is again:

VN:F [1.9.22_1171]
0
• Why won’t a for loop show up properly in the

?

int
reverseBits(int num)
{
int reverseBitsNum = 0;
const int wordSizeInBits = 32;
const int halfWordSizeInBits = 16;
int rightShiftStart = 31;
int leftShiftStart = 1;

for (int i = 0; i > i)) >> rightShiftStart;
rightShiftStart -= 2;
}
for (int i = halfWordSizeInBits; i > i)) << leftShiftStart;
leftShiftStart += 2;
}

return reverseBitsNum;
}

VN:F [1.9.22_1171]
0
• Sorry folks, this is embarassing that I can’t get a simple C/C++ for loop on the thread. One last time with pseudocode:

The two loops for the reversing the bits of a 32-bit integer are:
(1) To move (half the bits) the MSBs of the original int to the LSBs using Right Shift operations
(2) To move (the other half of the bits) the LSBs of the original int to the MSBs using Left Shift operations

int rightShiftStart = 31; // progresses 31, 29, 27, 25, … 1
for i = 0 to less than 16
{
reverseBitsNum |= (num & (0×80000000 >> i)) >> rightShiftStart;
rightShiftStart -= 2;
}

int leftShiftStart = 1; // it progresses 1, 3, 5, 7, … 31
for (i = 16 to less than 32)
{
reverseBitsNum |= (num & (0×80000000 >> i)) << leftShiftStart;
leftShiftStart += 2;
}

VN:F [1.9.22_1171]
0
21. #include

main()
{
int i=0;
int num,j;
int arr[10];
scanf(“%d”,&num);
while(i0)
{
arr[i]=num%2;
num=num/2;
printf(“%d”,arr[i]);
}
}
}

VN:F [1.9.22_1171]
0
22. sorry the above code is a wrong one just ignore it

VN:F [1.9.22_1171]
0
23. Here is my code (in C++) for an O(n) algorithm which reverses bits in (the binary representation of) an unsigned integer.

I’m not an expert, so I welcome any comments, suggestions and, of course, corrections. I have tested this code on a few cases and it seems to work fine. (I had to write an auxiliary function to display numbers in their binary representation).

dan

VN:F [1.9.22_1171]
0
24. The code that I posted above (not 2 minutes ago) was not posted properly. Specifically, the last few lines are wrong. I made a minor modification to the last two lines. Hopefully it will post properly.

dan

VN:F [1.9.22_1171]
0
25. Still not posting properly … one more try:

VN:F [1.9.22_1171]
0
26. Still not posting properly… I’ll post the code one last time (really, the last time) without using the code and /code tags. Sorry for the multiple posts.

void reverseBits(unsigned int &n){

// reverse the bits in the binary representation of n
// this code generalizes readily to any unsigned type (unsigned char, unsigned int, unsigned long)

int b = 8*sizeof(unsigned int);

unsigned int hi = 1 << (b-1); // in binary, lo == 000..01 and hi = 1000..0
unsigned int lo = 1;

bool loBitOfn, hiBitOfn;

while (lo < hi){

loBitOfn = (n & lo) != 0;
// loBitOfn iff the binary representation of n has a zero in the lo position

hiBitOfn = (n & hi) != 0;
// hiBitOfn iff the binary representation of n has a zero in the hi position

if ( hiBitOfn && !loBitOfn ){
n -= (hi-lo);
// toggle both the hi and the lo bits of n.
// note: hi-lo is positive and less than n so n remains nonnegative
}else if ( loBitOfn && !hiBitOfn ){
n += (hi-lo);
// toggle both the hi and the lo bits of n.
}

lo = lo <> 1; // shift the (unique) 1 digit in hi one notch to the right (ie integer-divide hi by 2)
}

}

VN:F [1.9.22_1171]
0
27. nice

VN:F [1.9.22_1171]
0
28. good job~~~

VN:F [1.9.22_1171]
0
29. This is very cool! Feel the fascination of Math

VN:F [1.9.22_1171]
0
30. Brilliant.
The devide and conquer can also be used in counting how many 1 bits in a integer.

VN:F [1.9.22_1171]
0
31. This seems like a much easier way to do it, O(n)

VA:F [1.9.22_1171]
0
32. VA:F [1.9.22_1171]
0
33. ` unsigned int reverse_bit (unsigned int num) { unsigned int bit; unsigned int rev_num=0; while (num) { bit=num&1; num=num>>1; rev_num=rev_num<<1| bit;`

` return rev_num; }`

VA:F [1.9.22_1171]
0
34. I can’t believe so many people believe so firmly that the D&C algorithm is O(logN).

“The first step is to swap all odd and even bits.” <– That alone is N/2 operations. How can the whole thing be O(logN)??

What fooled you guys is that the code uses bit masks and bit-wise operations and that makes the O(N) part seems like O(1). But no it is not. What if I give you an integer that has a billion digits?

If you say, look, the problem clearly says "unsigned integer" and that's 32-bit. Then there's no point in talking about the complexity. I can make a dedicated hardware that does it in O(1). Period.

VN:F [1.9.22_1171]
0