Odd bit operator in the increment statement of a for loop

Question

Given this for loop:

for(++i; i < MAX_N; i += i & -i)

what is it supposed to mean? What does the statement i += i & -i accomplish?

Answer 1

This loop is often observed in binary indexed tree (or BIT) implementation which is useful to update range or point and query range or point in logarithmic time. This loop helps to choose the appropriate bucket based on the set bit in the index. For more details, please consider to read about BIT from some other source. In below post I will show how does this loop help to find the appropriate buckets based on the least significant set bits.

2s complementary signed system (when i is signed)
i & -i is a bit hack to quickly find the number that should be added to given number to make its trailing bit 0(that's why performance of BIT is logarithmic). When you negate a number in 2s complementary system, you will get a number with bits in inverse pattern added 1 to it. When you add 1, all the less significant bits would start inverting as long as they are 1 (were 0 in original number). First 0 bit encountered (1 in original i) would become 1.

When you and both i and -i, only that bit (least significant 1 bit) would remain set and all lesser significant (right) bits would be zero and more significant bits would be inverse of original number.

Anding would generate a power of 2 number that when added to number i would clear the least significant set bit. (as per the requirement of BIT)

For example:

i = 28
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      *
-i
+---+---+---+---+---+---+---+---+
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+
  I   I   I   I   I   S   Z   Z
Z = Zero
I = Inverted
S = Same
* = least significant set bit

i & -i
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Adding
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      x
x = cleared now

Unsigned (when i is unsigned)
It will work even for 1s complementary system or any other representation system as long as i is unsigned for the following reason:

-i will take value of 2^{sizeof(unsigned int) * CHAR_BITS} - i. So all the bits right to the least significant set bit would remain zero, least significant bit would also remain zero, but all the bits after that would be inverted because of the carry bits.

For example:

i = 28
     +---+---+---+---+---+---+---+---+
     | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
                           *
-i
   0   1   1   1   1   1   <--- Carry bits
     +---+---+---+---+---+---+---+---+
   1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
     +---+---+---+---+---+---+---+---+
   - | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
   ----------------------------------------
     +---+---+---+---+---+---+---+---+
     | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
     +---+---+---+---+---+---+---+---+
       I   I   I   I   I   S   Z   Z
Z = Zero
I = Inverted
S = Same
* = least significant set bit

i & -i
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
+---+---+---+---+---+---+---+---+

Adding
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+
                      x
x = cleared now

Implementation without bithack

You can also use i += (int)(1U << __builtin_ctz((unsigned)i)) on gcc.

Live example here

A non obfuscated version for the same would be:

/* Finds smallest power of 2 that can reset the least significant set bit on adding */
int convert(int i) /* I purposely kept i signed as this works for both */
{
    int t = 1, d;
    for(; /* ever */ ;) {
        d = t + i; /* Try this value of t */
        if(d & t) t *= 2;  /* bit at mask t was 0, try next */
        else break; /* Found */
    }
    return t;
}

EDIT
Adding from this answer:

Assuming 2's complement (or that i is unsigned), -i is equal to ~i+1.

i & (~i + 1) is a trick to extract the lowest set bit of i.

It works because what +1 actually does is to set the lowest clear bit, and clear all bits lower than that. So the only bit that is set in both i and ~i+1 is the lowest set bit from i (that is, the lowest clear bit in ~i). The bits lower than that are clear in ~i+1, and the bits higher than that are non-equal between i and ~i.