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) "

I'd suggest you step thru this with pencil and paper, keeping track of i in either hex or binary. ~i & (i + 1) will be the lowest power of two that evenly divides i. After i += ~i & (i + 1), i will then be divisible by the next power of two (since the lowest bit got added, which will set the lowest nonzero bit to 0 and carry the 1 into the next higher position). — Logicrat
– Logicrat, Commented Mar 28, 2016 at 22:59
I can't even guess at what the point of doing that would be, but I can tell how the bits would move around. — Logicrat
– Logicrat, Commented Mar 28, 2016 at 23:00

comingstorm · Accepted Answer · 2016-03-28 23:51:55Z

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.

"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. " Well, this is wrong and it makes the answer particularly confusing.
Please explain: where do you think it is wrong? The rightmost zero-bit in a i is zero. When adding a 1 in that bit-position, there will be no carry. So the result, in this case, is the same as or-ing with a 1 in that bit-position: it is set, without affecting any other bits.

gnasher729 · Accepted Answer · 2016-03-28 23:28:49Z

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.

Ali Abbasinasab · Accepted Answer · 2016-03-28 23:24:29Z

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.

Collectives™ on Stack Overflow

Bit operation used in a for loop

3 Answers 3

2 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Related