Aseem Goyal - 1 year ago 65
C Question

# meaning of (number) & (-number)

What is the meaning of

`(number) & (-number)`
? I have searched it but was unable to find the meaning

I want to use
`i & (-i)`
in for loop like:

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

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.]

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download