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.

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.6/5 (29 votes cast)
Reverse Bits, 4.6 out of 5 based on 29 ratings

44 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]
      +2
  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]
    +1
    • 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]
      0
      • 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]
        +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]
    0
  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]
    0
  18. unsigned reverseBit(unsigned value)
    {
    unsigned answer = 0;
    unsigned i;

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

    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

      ?

      #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;
      }

      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

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.