3

I saw the link http://pvtridvs.net/pool/bithacks.html#BitReverseObvious and posted the code here:

unsigned int v;         // reverse the bits in this
unsigned int t = v;     // t will have the reversed bits of v
int i;

for (i = sizeof(v) * 8 - 1; i; i--)
{
  t <<= 1;
  v >>= 1;
  t |= v & 1;
}

Would someone explain a little bit why this look-simple algorithm works? I tested on paper some of the simplest examples, say 4-bit 0011 etc, it works, but I simply do not understand why these 3 lines of shift and bit-wise op can achieve it.

1
  • The URL has "The first method takes about 18 operations ..." which I disagree with. The first method does 6 operations per iteration and 32 iterations for other 180 operations. Feb 20, 2013 at 4:20

2 Answers 2

5

It shifts bits "out" of the low positions of v and "in" to the low positions of t. Think of the variables as stacks of bits. You're popping bits from v and pushing them into t. Popping from one list and pushing onto another initially empty list is a simple way to reverse any list. The intialization just performs the initial "push" of the lowest order bit onto the result. This trick saves one pup and push (i.e. a right and left shift). E.g. for a byte, only 7 more pop-pushes are needed.

1
  • "Note the intialization of t is useless." Not true — it's essential, in order to get the least-significant-bit of v. Feb 20, 2013 at 4:14
0

Each round t is shifted one position up, v is shifted one position down; and the currently last but of v is placed at the end of t.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.