Aseem Goyal - 6 months ago 39

C Question

What is the meaning of

`(number) & (-number)`

I want to use

`i & (-i)`

`for (i = 0; i <= n; i += i & (-i))`

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`

.

Using it in a loop seems odd unless the loop body modifies `i`

, because `i = i & (-i)`

is an idempotent operation: doing it twice gives the same result again.

[Edit: in a comment elsewhere you point out that the code is actually `i += i & (-i)`

. So what that does for non-zero `i`

is to clear the lowest group of set bits of `i`

, and set the next clear bit above that, for example 101100 -> 110000. For `i`

with no clear bit higher than the lowest set bit (including `i = 0`

), it sets `i`

to 0. So if it weren't for the fact that `i`

starts at `0`

, each loop would increase `i`

by *at least* twice as much as the previous loop, sometimes more, until eventually it exceeds `n`

and breaks or goes to `0`

and loops forever.

It would normally be inexcusable to write code like this without a comment, but depending on the domain of the problem *maybe* this is an "obvious" sequence of values to loop over.]