Counting, reversed bit pattern

Question

I am trying to find an algorithm to count from 0 to 2ⁿ-1 but their bit pattern reversed. I care about only n LSB of a word. As you may have guessed I failed.

For n=3:

000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7

You get the idea.

Answers in pseudo-code is great. Code fragments in any language are welcome, answers without bit operations are preferred.

Please don't just post a fragment without even a short explanation or a pointer to a source.

Edit: I forgot to add, I already have a naive implementation which just bit-reverses a count variable. In a sense, this method is not really counting.

Answer 1

This is, I think easiest with bit operations, even though you said this wasn't preferred

Assuming 32 bit ints, here's a nifty chunk of code that can reverse all of the bits without doing it in 32 steps:

 unsigned int i;
 i = (i & 0x55555555) <<  1 | (i & 0xaaaaaaaa) >>  1;
 i = (i & 0x33333333) <<  2 | (i & 0xcccccccc) >>  2;
 i = (i & 0x0f0f0f0f) <<  4 | (i & 0xf0f0f0f0) >>  4;
 i = (i & 0x00ff00ff) <<  8 | (i & 0xff00ff00) >>  8;
 i = (i & 0x0000ffff) << 16 | (i & 0xffff0000) >> 16;
 i >>= (32 - n);

Essentially this does an interleaved shuffle of all of the bits. Each time around half of the bits in the value are swapped with the other half.

The last line is necessary to realign the bits so that bin "n" is the most significant bit.

Shorter versions of this are possible if "n" is <= 16, or <= 8

Answer 2

At each step, find the leftmost 0 digit of your value. Set it, and clear all digits to the left of it. If you don't find a 0 digit, then you've overflowed: return 0, or stop, or crash, or whatever you want.

This is what happens on a normal binary increment (by which I mean it's the effect, not how it's implemented in hardware), but we're doing it on the left instead of the right.

Whether you do this in bit ops, strings, or whatever, is up to you. If you do it in bitops, then a clz (or call to an equivalent hibit-style function) on ~value might be the most efficient way: __builtin_clz where available. But that's an implementation detail.