Inverse Bit Counting Chart

Question

I am trying to find an algorithm for counting from 0 to 2 ⁿ -1, but their bit diagram has changed. I only care about n LSB words. 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.

The answers in the pseudo code are wonderful. Code snippets in any language are appreciated; responses without bitwise operations are preferred.

Please do not just post the snippet without a short explanation or a pointer to the source.

Edit: I forgot to add, I already have a naive implementation that simply inverts the variable count. In a sense, this method does not actually count.

Answer 1

This, I think, is easiest with bit operations, although you said it was not preferred

Assuming 32-bit ints, here is a great piece of code that can undo all bits without doing this 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 alternates with interleaving all the bits. Each time, about half the bits in the value are swapped with the other half.

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

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

Answer 2

This solution was originally binary and converted to ordinary math as the specified requester.

It will make more sense as binary, at least multiply by 2 and divide by 2, should be <<1 and → 1 for speed, addition and subtraction probably do not matter in one form or another.

If you pass the mask instead of nBits and use bitrate instead of multiplication or division and change the tail recursion to a loop, this will probably be the most efficient solution you will find, since every other call will be nothing but one addition, it will only be so slow. as Alnitak’s solution, 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, it turned out pretty cool. I did not figure in recursion until the last second.

It doesn’t feel right - for example, there are some operations that should not work, but they do because of the nature of what you are doing (for example, it seems like you have to worry when you work a little and some bits to the left are different from zero, but it turns out that you can never work on a bit if all the bits to the left are equal to zero - this is a very strange condition, but true.

An example of a flow to obtain from 110 to 001 (3 back to 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 3

At each step, find the leftmost digit 0 of your value. Install it and clear all the numbers to the left of it. If you do not find the number 0, you overflow: return 0 or stop, or fail, or whatever you want.

This is what happens in normal binary increment (by which I mean the effect, not how it is implemented in hardware), but we do it on the left, and not on the right.

Whether you do this in bit operations, strings, or something else is up to you. If you do this in bitograms, then clz (or calling an equivalent hibit-style function) on ~value : __builtin_clz where possible is the most efficient way. But this is an implementation detail.

Answer 4

Here, the solution from mine answers another question that computes the next bit-reverse index without a loop. However, it relies mainly on bit operations.

The basic idea is that incrementing a number simply flips the sequence of the least significant bits, for example, from nnnn0111 to nnnn1000 . Therefore, to calculate the next bit-reverse index, you need to flip the sequence of the most significant bits. If your target platform has a CTZ ("count trailing zeros") instruction, this can be done efficiently.

Example in C using GCC __builtin_ctz :

 void iter_reversed(unsigned bits) { unsigned n = 1 << bits; for (unsigned i = 0, j = 0; i < n; i++) { printf("%x\n", j); // Compute a mask of LSBs. unsigned mask = i ^ (i + 1); // Length of the mask. unsigned len = __builtin_ctz(~mask); // Align the mask to MSB of n. mask <<= bits - len; // XOR with mask. j ^= mask; } } 

Without the CTZ instruction, you can also use integer division:

 void iter_reversed(unsigned bits) { unsigned n = 1 << bits; for (unsigned i = 0, j = 0; i < n; i++) { printf("%x\n", j); // Find least significant zero bit. unsigned bit = ~i & (i + 1); // Using division to bit-reverse a single bit. unsigned rev = (n / 2) / bit; // XOR with mask. j ^= (n - 1) & ~(rev - 1); } } 

Answer 5

 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 6

Maybe increment from 0 to N (the "normal" way) and do ReverseBitOrder () for each iteration. You can find several implementations here (I like LUT one best). It must be very fast.

Answer 7

Here is the answer to Perl. You do not say what happens after all the templates, so I just return zero. I took out bitwise operations so that they could be easily translated 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 8

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

 (defun inv-step (xn) ; 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 (sx)) ; init of s as x ((not (integerp i)) ; breaking condition s) ; returned value if all bits are 1 (is 0 then) (if (< si) ; the loop body: if s < i (return-from inv-step (+ si)) ; -> add i to s and return the result (decf si)))) ; else: reduce s by i 

I commented on this completely since you are not familiar with this syntax.

edit: here is the tail recursive version. This seems a little faster if you have a tail call optimizer compiler.

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

Answer 9

Here's a solution that doesn't really try to make any addition, but uses the seqence on / off pattern (most sig bits are interleaved each time, the next sig bit is interleaved each time, etc.), configure 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 10

How about adding 1 to the most significant bit, and then, if necessary, transferring it to the next (less significant) bit. You can speed this up by byte:

• Pre-copy the lookup table to count in the bit-reverse direction from 0 to 256 (00000000 → 10000000, 10000000 → 01000000, ..., 11111111 → 00000000).
• Set all bytes in your multibyte number to zero.
• Increase the most significant byte using the lookup table. If the byte is 0, add the next byte using the lookup table. If the byte is 0, add the next byte ...
• Go to step 3.

Answer 11

When you cancel 0 to 2^n-1 , but their bitmap is canceled, you pretty much cover the whole sequence 0-2^n-1

 Sum = 2^n * (2^n+1)/2 

O(1) . There is no need to do a bit reversal.

Answer 12

Edit: Of course, the original question on posters was to make the increment on (the opposite), which makes things simpler than adding two random values. So, nwellnhof answer contains the algorithm already.

---

Sum of two bit reversal values

Here is one solution in php:

 function RevSum ($a,$b) { // loop until our adder, $b, is zero while ($b) { // get carry (aka overflow) bit for every bit-location by AND-operation // 0 + 0 --> 00 no overflow, carry is "0" // 0 + 1 --> 01 no overflow, carry is "0" // 1 + 0 --> 01 no overflow, carry is "0" // 1 + 1 --> 10 overflow! carry is "1" $c = $a & $b; // do 1-bit addition for every bit location at once by XOR-operation // 0 + 0 --> 00 result = 0 // 0 + 1 --> 01 result = 1 // 1 + 0 --> 01 result = 1 // 1 + 1 --> 10 result = 0 (ignored that "1", already taken care above) $a ^= $b; // now: shift carry bits to the next bit-locations to be added to $a in // next iteration. // PHP_INT_MAX here is used to ensure that the most-significant bit of the // $b will be cleared after shifting. see link in the side note below. $b = ($c >> 1) & PHP_INT_MAX; } return $a; } 

Note: see this negative offset question .

As for the test; start from zero and increase the value by 8-bit inverted (10000000):

 $value = 0; $add = 0x80; // 10000000 <-- "one" as bit reversed for ($count = 20; $count--;) { // loop 20 times printf("%08b\n", $value); // show value as 8-bit binary $value = RevSum($value, $add); // do addition } 

... will output:

  00000000 10000000 01000000 11000000 00100000 10100000 01100000 11100000 00010000 10010000 01010000 11010000 00110000 10110000 01110000 11110000 00001000 10001000 01001000 11001000