I recently implemented an algorithm that has to perform checks on all subsets of some large set. A subset of an $n$-sized set can be understood as a binary string of length $n$ where bit $i$ is set if and only if the $i$-th element is in the subset. During my search for code to enumerate such bitstrings, I found the greatest page in the entire internet. If anyone can explain to me how computing the next bit permutation (the last version) works, please do.

# Bit Twiddling Hacks

## 5 Replies to “Bit Twiddling Hacks”

## Leave a Reply

Your email address will not be published. Required fields are marked *

Timonsays:rattlesays:Phillesays:tobisays:`1`

s 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`1`

s. Assume it has length`n`

and there are`m`

`0`

s to its right. 2. Change the`0`

to its left to a`1`

. 3. Zero out the block of`1`

s and 4. set`n-1`

bits of lowest significance to`1`

s. The algorithm, slightly modified using chars and more step-by-step, looks like this: 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`0`

s to`1`

:`a=10111111`

. 2. Step`b`

flips the`0`

left of the rightmost block of`1`

s and zeroes out everything to its right:`b=11000000`

. 3. Step`c`

consists (exactly) of all`1`

s to the right of the flipped bit:`c=00111111`

. That are`m+n`

`1`

s. 4. Step`d`

shifts`c`

by`m+1`

, therefore leaving the`n-1`

least significant bits as`1`

s:`d=00000011`

. 5. The final step puts together the more significant bits in`b`

and the bits of lower significance in`d`

.rattlesays: