CODEWITHSUNDEEP
c++bit
Tanmay Jha
Tanmay Jha

Reputation: 11

Reversal of a binary number using bit hacks

Can someone please explain how the binary number is being reversed.

unsigned rev = 0;
unsigned k = n;

while (k)
{
// add rightmost bit to rev 
    rev = (rev << 1) | (k & 1);
    k = k >> 1;     // drop last bit
            cout<<"k val is "<<bitset<8>(k)<<endl;
    cout<<"rev val is "<<{bitset<8>(rev)<<endl;
}

Output if n=9

k val is 00000100
rev val is 00000001
k val is 00000010
rev val is 00000010
k val is 00000001
rev val is 00000100
k val is 00000000
rev val is 00001001
9 is Palindrome

I was referring question 2 from here: http://www.techiedelight.com/bit-hacks-part-6-random-problems/

As far as I know, only first expression is executed if it is true for "|" condition statement. So, here rev<<1 will be false only for first execution of loop but not for rest. Therefore how does rev get 1 in the end for last condition because (k&1) won't be executed. Only left shift will be executed right?

Upvotes: 1

Views: 221

Answers (3)

Adrien Suau
Adrien Suau

Reputation: 289

One visualisation that may be useful is a stack: imagine your number n is represented by a stack of binary digits, the least significant digit being at the top of the stack.

A common algorithm for bit reversing is then to iteratively pop the digits one by one from the n stack and stack them in an other stack (representing rev in your case).

  • k = k >> 1; pops one binary digit from the stack n (renamed as k in your code)

  • rev = (rev << 1) | (k & 1); stacks the binary digit on the top of the k stack.

In the code, the pop/stack operations are reversed to avoid temporaries.

Finally, this operation of pop/stack should be repeated as long as there are digits in the n stack. This is because the while condition is only k, it tests whether or not k is 0 (no digits left).

PS: you have some low-level algorithms to perform bit-reversing on the Bit Twiddling Hacks website. The algorithms aim at performance and so may not be easily understandable.

Upvotes: 1

Codor
Codor

Reputation: 17605

The variable rev is initialized with 0, it will contain the result. The while loop iterates while k, which is the input, has any set bits left. The first statement of the loop's body masks out the last bit of k and copies it it rev, which is shifted one bit to the left in the process (by the shift operator). In the loop iteration, both the input and the output are shifted - the inpu is shifted to the right, the output to the left.

Upvotes: 0

Bob Jacobsen
Bob Jacobsen

Reputation: 1160

As far as I know, only first expression is executed if it is true for "|" condition statement.

The | operator is a bit-wise OR: it’s value is the OR operation on the bit patterns of its two operands. It always evaluated both operands because it needs their full values. Example: 3 | 5 is 7.

The || is a logical OR: it’s true if either operands (as an entire value) is true. It does not evaluate the 2nd operands if the first was true.

The code is using the | bit-wise OR to build up the answer one bit at a time.

Upvotes: 0

Related Questions