Iterate through all combinations in Gray code order

Question

Let's say i have n integers in an array a, and i want to iterate through all possible subsets of these integers, find the sum, and then do something with it.

What i immedieatelly did, was to create a bit field b, which indicated which numbers were included in the subset, and iterate through its possible values using ++b. Then, to compute the sum in each step, i had to iterate through all bits like this:

int sum = 0;
for (int i = 0; i < n; i++)
    if (b&1<<i)
        sum += a[i];

Then i realized that if i iterated through the possible values of b in a Gray code order, so that each time only a single bit is flipped, i wouldn't have to reconstruct the sum completely, but only needed to add or subtract the single value that is being added or removed from the subset. It should work like this:

int sum = 0;
int whichBitToFlip = 0;
bool isBitSet = false;
for (int k = 0; whichBitToFlip < n; k++) {
    sum += (isBitSet ? -1 : 1)*a[whichBitToFlip];

    // do something with sum here

    whichBitToFlip = ???;
    bool isBitSet = ???;
}

But i can't figure out how to directly and efficiently compute whichBitToFlip. The desired values are basically sequence A007814. I know that i can compute the Gray code using the formula (k>>1)^k and xor it with the previous one, but then i need to find the position of the changed bit, which might not be much faster.

So is there any better way to determine these values (index of flipped bit), preferably without a cycle, faster than recomputing the whole sum (of at most 64 values) every time?

[Gray code](http://en.wikipedia.org/wiki/Gray_code). – President James K. Polk Sep 27 '14 at 23:31 — President James K. Polk, Sep 27 '14 at 23:31

rici · Answer 1 · 2014-09-28T01:04:51.697

1

To convert a bitmask to a bit index, you can use the ffs function (if you have one), which corresponds to a machine opcode on some machines.

Otherwise, the bit changed in the gray code corresponds to the ruler function:

0, 1, 0, 2, 0, 1, 0, 3, 0, 1...

for which there is a simple recursion. You can simulate the recursion with a stack (it will have maximum depth O(log N), so it's not much space), but probably ffs is a lot faster.

(By the way, even if you were to count bits one at a time from right-to-left, the increment function would be O(1) on average because the total number of trailing 0s in the integers from 1 to 2^k is 2^k-1.)

edited Sep 28 '14 at 01:04

answered Sep 28 '14 at 00:31

rici

234,347
28
237
341

I just realized that i don't need to xor the gray codes, because i can get the "ruler function" just from counting the trailing zeroes of `k`, right? Also thanks for the last part, i didn't think of that. – Detheroc Sep 28 '14 at 07:15

score 0 · Accepted Answer · answered Sep 28 '14 at 11:44

So i came up with this:

int sum = 0;
unsigned long grayPos = 0;
int graySign = 1;
for (uint64 k = 2; grayPos < n; k++) {
    sum += graySign*a[grayPos];

    // Do something with sum

    #ifdef _M_X64
        grayPos = n;
        _BitScanForward64(&grayPos, k);
    #else
        for (grayPos = 0; !(k&1ull<<grayPos); grayPos++);
    #endif
    graySign = 2-(k>>grayPos&0x3);
}

It works really well, brought down the execution time (in comparison to always recomputing the whole sum) from 254 to only 7 seconds for n = 32. I also found that counting trailing zeroes with the for cycle is only slightly (~15%) slower than using _BitScanForward64 for the reasons mentioned by rici. So thanks.

Iterate through all combinations in Gray code order

2 Answers2