## 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 i^{th} bit with the j^{th} 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 i^{th} bit with the j^{th} 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 i^{th} bit and the j^{th} bit are different. To test if two bits are different, we could use the XOR operation. Then, we need to toggle both i^{th} and j^{th} bits. We could apply the XOR operation again. By XOR-ing the i^{th} and j^{th} 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 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.

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));

+41337c0d3r 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.

+3john 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.

0flo said on November 10, 2011

Thanks for the solution, never have imagined the O(log N) one.

0Debasis Ganguly said on August 15, 2013

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)

-1DavidH said on May 18, 2014

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

0Jeff R said on October 26, 2014

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

+1Ankur 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

01337c0d3r 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

0Sonali said on December 29, 2011

Isnt this is o(nlogn) solution instead do o(logn)

+1zhiming wang said on March 17, 2014

it’s log(n), the same as binary search.

-1Jeff R said on October 26, 2014

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)

+1Balaji 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;

}

}

}

0Balaji 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

)

0Balaji 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

)”

0mirokuneal 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?

+1mirokuneal 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;

}

}

0vq 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?

0Gordon 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.

0mattz said on July 29, 2013

I think it should be: (num << 1) | bit

+2srikanth said on January 24, 2012

Isn’t reversing equal to doing a circular shift by length/2 ?

-1Matn 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 ?

0Karthick 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:

0sandyfriend said on March 16, 2012

prefect list bySean Eron Anderson

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

+2prashanth 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;

}

}

+1Karthik Rajendran said on August 19, 2012

excellent code

0Jiefu 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;

}

0Yi Shan said on March 26, 2013

public static uint Reverse(uint num)

{

uint rnum = 0;

while (num > 0)

{

rnum = (rnum <>= 1;

}

return rnum;

}

0nishant 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();

}

0Mukesh Barman said on April 28, 2013

The Divide and Conquer solution has O(nLogn) running time?

+1qinchen said on May 15, 2013

unsigned reverseBit(unsigned value)

{

unsigned answer = 0;

unsigned i;

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

answer <>= 1;

}

return answer;

}

0foobar said on June 27, 2013

Here’s mine in C:

0foobar said on June 27, 2013

Sorry, the for() loops got completely messed up. Here it is again:

0foobar said on June 27, 2013

Why won’t a for loop show up properly in the

?

#define MASK 0×80000000

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;

}

0foobar said on June 27, 2013

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;

}

0rohit said on July 13, 2013

#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]);

}

}

}

0rohit said on July 13, 2013

sorry the above code is a wrong one just ignore it

0danlior said on August 21, 2013

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

0danlior said on August 21, 2013

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

0danlior said on August 21, 2013

Still not posting properly … one more try:

0danlior said on August 21, 2013

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)

}

}

0Neo said on September 26, 2013

nice

0duter said on December 2, 2013

good job~~~

0Ze Wang said on February 11, 2014

This is very cool! Feel the fascination of Math

0zhiming wang said on March 17, 2014

Brilliant.

The devide and conquer can also be used in counting how many 1 bits in a integer.

0Chris said on April 23, 2014

This seems like a much easier way to do it, O(n)

0akluch said on November 25, 2014

0ee said on December 1, 2014

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

}

0rpzw said on December 10, 2014

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.

0