Bit operation used in a for loop

Question

I found this loop in the source code of an algorithm. I think that details about the problems aren't relevant here, because this is a really small part of the solution.

    void update(int i, int value, int array[], int n) {
        for(; i < n; i += ~i & (i + 1)) {
            array[i] += value;
        }
}

I don't really understand what happens in that for loop, is it some sort of trick? I found something similar named Fenwick trees, but they look a bit different than what I have here.

Any ideas what this loop means?

Also, found this :

"Bit Hack #9. Isolate the rightmost 0-bit.

y = ~x & (x+1) "

Answer 1

You are correct: the bit-hack ~i & (i + 1) should evaluate to an integer which is all binary 0's, except the one corresponding to the rightmost zero-bit of i, which is set to binary 1.

So at the end of each pass of the for loop, it adds this value to itself. Since the corresponding bit in i is zero, this has the effect of setting it, without affecting any other bits in i. This will strictly increase the value of i at each pass, until i overflows (or becomes -1, if you started with i<0). In context, you can probably expect that it is called with i>=0, and that i < n is set terminate the loop before your index walks off the array.

The overall function should have the effect of iterating through the zero-bits of the original value of i from least- to most-significant, setting them one by one, and incrementing the corresponding elements of the array.

Fenwick trees are a clever way to accumulate and query statistics efficiently; as you say, their update loop looks a bit like this, and typically uses a comparable bit-hack. There are bound to be multiple ways to accomplish this kind of bit-fiddling, so it is certainly possible that your source code is updating a Fenwick tree, or something comparable.

Answer 2

Assume that from the right to the left, you have some number of 1 bits, a 0 bit, and then more bits in x.

If you add x + 1, then all the 1's at the right are changed to 0, the 0 is changed to 1, the rest is unchanged. For example xxxx011 + 1 = xxxx100.

In ~x, you have the same number of 0 bits, a 1 bit, and the inverses of the other bits. The bitwise and produces the 0 bits, one 1 bit, and since the remaining bits are and'ed with their negation, those bits are 0.

So the result of ~x & (x + 1) is a number with one 1 bit where x had its rightmost zero bit.

If you add this to x, you change the rightmost 0 to a 1. So if you do this repeatedly, you change the 0 bits in x to 1, from the right to the left.

Answer 3

The update function iterates and sets the 0-bits of i from the leftmost zero to the rightmost zero and add value to the ith element of array.

The for loop checks if i is less than n, if so, ~i & (i + 1) would be an integer has all binary 0's, except for the rightmost bit ( i.e. 1). Then array[i] += value adds value to iterated itself.

Setting i to 8 and going through iterations may clear things to you.