What does (number & -number) mean in bit programming? [duplicate]

Question

For example:

int get(int i) {     int res = 0;     while (i) {         res = (res + tree[i]) % MOD;         i -= ( (i) & (-i) );     }     return res; } 

A tree update function:

void update(int i, int val) {     while (i <= m) {         tree[i] = (tree[i] + val) % MOD;         i += ( (i) & (-i) );     } } 

Can you please explain what they do in the code by using ( (i) & (-i) )?

Answer 1

Let me assume that negative value is represented using two's complement. In this case, -i can be calculated as (~i)+1 (flip bits, then add 1).

For example, let me consider i = 44. Then, in binary,

i           = 0000 0000 0000 0000 0000 0000 0010 1100 ~i          = 1111 1111 1111 1111 1111 1111 1101 0011 -i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100 (i) & (-i)  = 0000 0000 0000 0000 0000 0000 0000 0100 

As you see, the least bit that is 1 can be calculated using (i) & (-i).