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.

Can you explain the below more ? thanks.

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

+5@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.

+4thanks, 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.

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

0The 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)

-2No, 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).

+2No, 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).

+1You are all right in the context that D&C does not have a better than O(NlogN) solution,

But the solution here is a trick that is visualised as a D&C approach.

Assume a 32 bit number, Swapping all even and odd bits -O(1)

swapping all consecutive groups of 2 bits at a time -O(1)

Next, swapping all consecutive groups of 4 bits at a time -O(1)

Next, swapping all consecutive groups of 8 bits at a time -O(1)

Next, swapping all consecutive groups of 16 bits at a time -O(1)

This is all, We get our answer.

Total time complexity-O(LogN).

+2Hi

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

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

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

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

-1Its 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)

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

}

}

}

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

)

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

)”

0For a O(n) approach, how about using the same way to reverse a number? Like this:

Is there any potential problem?

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

}

}

0I just don’t understand, how the code reverse a number, is it saying, if given 115, it will return 511?

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

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

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

-1If i can’t use numbers bigger than 0xFF in the code is it still possible to use the divide and conquer method ?

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

0prefect list bySean Eron Anderson

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

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

}

}

+1excellent code

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

}

0Pingback: Amazon interview preparation | What I learn, I blog !

public static uint Reverse(uint num)

{

uint rnum = 0;

while (num > 0)

{

rnum = (rnum <>= 1;

}

return rnum;

}

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

}

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

+1unsigned reverseBit(unsigned value)

{

unsigned answer = 0;

unsigned i;

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

answer <>= 1;

}

return answer;

}

0Here’s mine in C:

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

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

?

#define MASK 0x80000000

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;

}

0Sorry 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 & (0x80000000 >> i)) >> rightShiftStart;

rightShiftStart -= 2;

}

int leftShiftStart = 1; // it progresses 1, 3, 5, 7, … 31

for (i = 16 to less than 32)

{

reverseBitsNum |= (num & (0x80000000 >> i)) << leftShiftStart;

leftShiftStart += 2;

}

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

}

}

}

0sorry the above code is a wrong one just ignore it

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

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

0Still not posting properly … one more try:

0Still 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)

}

}

0nice

0good job~~~

0This is very cool! Feel the fascination of Math

0Brilliant.

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

0Pingback: 反转比特位(文章最后有干货) | 新热网—关注互联网，打造互联网知识与技术分享的科技博客

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

0Pingback: Reverse the bits of an integer | kiddy

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

}

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

0Here is how I did it:

0Pingback: LeetCode Reverse Bits | bitJoy > code