CODEWITHSUNDEEP
javabit-manipulationreversebit
Ravi Krishna
Ravi Krishna

Reputation: 67

reverse bits in Java - O(n)

I'm trying to understand this code which reverses bits in O(n) time. I understand the time complexity, but I'm not able to understand the logic behind this code. 

public static long reverse(long a) {
    long result = 0;
    int i = 31;
    while(a > 0){

        result += (a % 2) * Math.pow(2, i);
        i--;                        
        a = a/2;
    }
    return result;
}

To keep it simple, for example, if I take 12 (1100) and only 4 bits (set i = 3), my output will be 3 (0011). I get that and I'm able to derive the answer as well.

But can someone explain the logic behind this code? Thanks!

Upvotes: 2

Views: 305

Answers (2)

Jim Garrison
Jim Garrison

Reputation: 86774

That code is

  1. broken for half the possible bit patterns (all the negative numbers), and
  2. O(n), not O(log n), where n is the number of bits in a
  3. Very inefficient
  4. Confusingly written

The algorithm works only for positive numbers and does:

extract the rightmost bit from a
set the corresponding bit from the left end
shift a one position to the right

It repeats as long as a > 0. If the value of a has some leading zero bits then this algorithm will be a little better than O(n).

Inefficiency results from remainder and division for bit extraction when masking and shifting would be much faster, although a modern compiler should be able to convert a/2 to a >> 1 and a%2 to a & 0x00000001. However I don't know if it would recognize Math.pow(2, i) as 0x00000001 << i;

Upvotes: 2

11thdimension
11thdimension

Reputation: 10653

Here's the explanation

i = 31 //number of bits in integer

Following has two parts

result += (a % 2) * Math.pow(2, i);

(a % 2) calculates last bit. Multiplying anything with a positive power of 2 has the effect of left shifting the bits. (Math.pow(2, i) shifts to left i times.

so we are calculating unit place bit and placing it at ith position from the unit place, which is (31 - i) from the right, which effectively reverses the bit's position from left to right.

and finally 

i--; //move to next bit
a = a/2; //chop the unit place bit to proceed to next.

That's it.

Upvotes: 1

Related Questions