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 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

Answer 2

void reverse(int nMaxVal, int nBits)
{
   int thisVal, bit, out;

   // Calculate for each value from 0 to nMaxVal.
   for (thisVal=0; thisVal<=nMaxVal; ++thisVal)
   {
      out = 0;

      // Shift each bit from thisVal into out, in reverse order.
      for (bit=0; bit<nBits; ++bit)
         out = (out<<1) + ((thisVal>>bit) & 1)

   }
   printf("%d -> %d\n", thisVal, out);
}

Answer 3

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 4

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.

Answer 5

Maybe increment from 0 to N (the "usual" way") and do ReverseBitOrder() for each iteration. You can find several implementations here (I like the LUT one the best). Should be really quick.

Answer 6

Here's an answer in Perl. You don't say what comes after the all ones pattern, so I just return zero. I took out the bitwise operations so that it should be easy to translate into another language.

sub reverse_increment {
  my($n, $bits) = @_;

  my $carry = 2**$bits;
  while($carry > 1) {
    $carry /= 2;
    if($carry > $n) {
      return $carry + $n;
    } else {
      $n -= $carry;
    }
  }
  return 0;
}

Answer 7

With n as your power of 2 and x the variable you want to step:

(defun inv-step (x n)       ; the following is a function declaration
  "returns a bit-inverse step of x, bounded by 2^n"    ; documentation
  (do ((i (expt 2 (- n 1))  ; loop, init of i
          (/ i 2))          ; stepping of i
       (s x))               ; init of s as x
      ((not (integerp i))   ; breaking condition
       s)                   ; returned value if all bits are 1 (is 0 then)
    (if (< s i)                         ; the loop's body: if s < i
        (return-from inv-step (+ s i))  ;     -> add i to s and return the result
        (decf s i))))                   ;     else: reduce s by i

I commented it thoroughly as you may not be familiar with this syntax.

edit: here is the tail recursive version. It seems to be a little faster, provided that you have a compiler with tail call optimization.

(defun inv-step (x n)
  (let ((i (expt 2 (- n 1))))
    (cond ((= n 1)
           (if (zerop x) 1 0))         ; this is really (logxor x 1)                                                 
          ((< x i)
           (+ x i))
          (t
           (inv-step (- x i) (- n 1))))))

Answer 8

Here's a solution which doesn't actually try to do any addition, but exploits the on/off pattern of the seqence (most sig bit alternates every time, next most sig bit alternates every other time, etc), adjust n as desired:

#define FLIP(x, i) do { (x) ^= (1 << (i)); } while(0)

int main() {
    int n = 3;
    int max = (1 << n);
    int x = 0;

    for(int i = 1; i <= max; ++i) {
     std::cout << x << std::endl;
     /* if n == 3, this next part is functionally equivalent to this:
      *
      * if((i % 1) == 0) FLIP(x, n - 1);
      * if((i % 2) == 0) FLIP(x, n - 2);
      * if((i % 4) == 0) FLIP(x, n - 3);
      */
     for(int j = 0; j < n; ++j) {
      if((i % (1 << j)) == 0) FLIP(x, n - (j + 1));
     }                   
    }
}

Answer 9

How about adding 1 to the most significant bit, then carrying to the next (less significant) bit, if necessary. You could speed this up by operating on bytes:

1. Precompute a lookup table for counting in bit-reverse from 0 to 256 (00000000 -> 10000000, 10000000 -> 01000000, ..., 11111111 -> 00000000).
2. Set all bytes in your multi-byte number to zero.
3. Increment the most significant byte using the lookup table. If the byte is 0, increment the next byte using the lookup table. If the byte is 0, increment the next byte...
4. Go to step 3.