Counting, reversed bit pattern

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

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

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.