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

<p>For n=3: </p>

<pre><code>000 -&gt; 0
100 -&gt; 4
010 -&gt; 2
110 -&gt; 6
001 -&gt; 1
101 -&gt; 5
011 -&gt; 3
111 -&gt; 7
</code></pre>

<p>You get the idea.</p>

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

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

<p>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.</p>

This solution was originally in binary and converted to conventional math as the requester specified.
It would make more sense as binary, at least the multiply by 2 and divide by 2 should be << 1 and >> 1 for speed, the additions and subtractions probably don't matter one way or the other.
If you pass in mask instead of nBits, and use bitshifting instead of multiplying or dividing, and change the tail recursion to a loop, this will probably be the most performant solution you'll find since every other call it will be nothing but a single add, it would only be as slow as Alnitak's solution once every  4, maybe even 8 calls.
```
```
int incrementBizarre(int initial, int nBits)
    // in the 3 bit example, this should create 100
    mask=2^(nBits-1)
    // This should only return true if the first (least significant) bit is not set
    // if initial is 011 and mask is 100
    //                3               4, bit is not set
    if(initial < mask)
        // If it was not, just set it and bail.
        return initial+ mask // 011 (3) + 100 (4) = 111 (7)
    else
        // it was set, are we at the most significant bit yet?
        // mask 100 (4) / 2 = 010 (2), 001/2 = 0 indicating overflow
        if(mask / 2) > 0
            // No, we were't, so unset it (initial-mask) and increment the next bit
            return incrementBizarre(initial - mask, mask/2)
        else
            // Whoops we were at the most significant bit.  Error condition
            throw new OverflowedMyBitsException()
```
```
Wow, that turned out kinda cool.  I didn't figure in the recursion until the last second there.
It feels wrong--like there are some operations that should not work, but they do because of the nature of what you are doing (like it feels like you should get into trouble when you are operating on a bit and some bits to the left are non-zero, but it turns out you can't ever be operating on a bit unless all the bits to the left are zero--which is a very strange condition, but true.
Example of flow to get from 110 to 001 (backwards 3 to backwards 4):
```
```
mask 100 (4), initial 110 (6); initial < mask=false; initial-mask = 010 (2), now try on the next bit
mask 010 (2), initial 010 (2); initial < mask=false; initial-mask = 000 (0), now inc the next bit
mask 001 (1), initial 000 (0); initial < mask=true;  initial + mask = 001--correct answer
```
```