Bit Twiddling Hacks

5 Replies to “Bit Twiddling Hacks”

1. Usually I look these kinds of things up in the "Hacker's Delight" book (http://www.hackersdelight.org). They also have many code snippets online under http://www.hackersdelight.org/hdcode.htm. Unfortunately, they only present an efficient algorithm for generating a single user-defined permutation, but none for this lexicographically-next permutation problem :-(

   Reply
2. First of all, fancy seeing you here! Second, thanks for the crazy awesome links. Since I am sporting Firefox now, I can even bookmark those.

   Reply
3. Yeah, "bit fiddling hacks" is a nice one. I found out about it exactly like you did: Subsets encoded as binary string. But in the end I took the piece of code I needed (how to compute the size of my subset) from wikipedia … http://en.wikipedia.org/wiki/Hamming_weight But exactly this lexicographically next permutation thingy might come in handy for a side/subproject in the next weeks.

   Reply
4. This is fun. :) First, going to the next permutation is very much like counting in binary, except that the number of 1s has to stay the same. It's just the smallest number that is both greater than the current one and has the same number of ones. So we calculate the smallest possible increase while maintaining the number of ones as follows: 1. Take the rightmost maximal block of 1s. Assume it has length n and there are m 0s to its right. 2. Change the 0 to its left to a 1. 3. Zero out the block of 1s and 4. set n-1 bits of lowest significance to 1s. The algorithm, slightly modified using chars and more step-by-step, looks like this:

   unsigned char const a = cur_perm | (cur_perm - 1);
   unsigned char const b = a+1;
   unsigned char const c = (~a & b) - 1;
   unsigned char const d = c >> __builtin_ctz(cur_perm) + 1;
   unsigned char const next_perm = b | d;
   

   Note that -~x is just a stupid way of writing x+1, as arithmetic negation in two's complement is equivalent to negating bit-wise and adding 1 after. Also, __builtin_ctz(cur_perm) equals m. For example, say cur_perm = 0b10111000. 1. Step a sets the rightmost 0s to 1: a=10111111. 2. Step b flips the 0 left of the rightmost block of 1s and zeroes out everything to its right: b=11000000. 3. Step c consists (exactly) of all 1s to the right of the flipped bit: c=00111111. That are m+n 1s. 4. Step d shifts c by m+1, therefore leaving the n-1 least significant bits as 1s: d=00000011. 5. The final step puts together the more significant bits in b and the bits of lower significance in d.

   Reply
5. Awesome! Thanks for explaining it.

   Reply