meaning of (number) & (-number)
Olivia Zamora 
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))4 Answers
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.]
2I thought I'd just take a moment to show how this works. This code gives you the lowest set bit's value:
int i = 0xFFFFFFFF; //Last byte is 1111(base 2), -1(base 10)
int j = -i; //-(-1) == 1
int k = i&j; // 1111(2) = -1(10) // & 0001(2) = 1(10) // ------------------ // 0001(2) = 1(10). So the lowest set bit here is the 1's bit
int i = 0x80; //Last 2 bytes are 1000 0000(base 2), 128(base 10)
int j = -i; //-(128) == -128
int k = i&j; // ...0000 0000 1000 0000(2) = 128(10) // & ...1111 1111 1000 0000(2) = -128(10) // --------------------------- // 1000 0000(2) = 128(10). So the lowest set bit here is the 128's bit
int i = 0xFFFFFFC0; //Last 2 bytes are 1100 0000(base 2), -64(base 10)
int j = -i; //-(-64) == 64
int k = i&j; // 1100 0000(2) = -64(10) // & 0100 0000(2) = 64(10) // ------------------ // 0100 0000(2) = 64(10). So the lowest set bit here is the 64's bitIt works the same for unsigned values, the result is always the lowest set bit's value.
Given your loop:
for(i=0;i<=n;i=i&(-i)) There are no bits set (i=0) so you're going to get back a 0 for the increment step of this operation. So this loop will go on forever unless n=0 or i is modified.
Assuming that negative values are using two's complement. Then -number can be calculated as (~number)+1, flip the bits and add 1.
For example if number = 92. Then this is what it would look like in binary:
number 0000 0000 0000 0000 0000 0000 0101 1100
~number 1111 1111 1111 1111 1111 1111 1010 0011
(~number) + 1 1111 1111 1111 1111 1111 1111 1010 0100
-number 1111 1111 1111 1111 1111 1111 1010 0100
(number) & (-number) 0000 0000 0000 0000 0000 0000 0000 0100You can see from the example above that (number) & (-number) gives you the least bit.
You can see the code run online on IDE One:
Here is some C code:
#include <iostream>
#include <bitset>
#include <stdio.h>
using namespace std;
void printIntBits(int num);
void printExpression(char *text, int value);
int main() { int number = 92; printExpression("number", number); printExpression("~number", ~number); printExpression("(~number) + 1", (~number) + 1); printExpression("-number", -number); printExpression("(number) & (-number)", (number) & (-number)); return 0;
}
void printExpression(char *text, int value) { printf("%-20s", text); printIntBits(value); printf("\n");
}
void printIntBits(int num) { for(int i = 0; i < 8; i++) { int mask = (0xF0000000 >> (i * 4)); int portion = (num & mask) >> ((7 - i) * 4); cout << " " << std::bitset<4>(portion); }
}Also here is a version in C# .NET:
The operation i & -i is used for isolating the least significant non-zero bit of the corresponding integer.
In binary notation
numcan be represented asa1b, wherearepresents binary digits before the last bit andbrepresents zeroes after the last bit.-numis equal to(a1b)¯ + 1 = a¯0b¯ + 1.bconsists of all zeroes, sob¯consists of all ones.-num = (a1b)¯ + 1=>a¯0b¯ + 1=>a¯0(0…0)¯ + 1=>¯0(1…1) + 1=>a¯1(0…0)=>a¯1b
Now,
num & -num=>a1b & a¯1b=>(0..0)1(0..0)
For e.g. if i = 5
| iteration | i | last bit position | i & -i|
|-------- |--------|-------- |-----|
| 1 | 5 = 101 | 0 | 1 (2^0)|
| 2 | 6 = 110 | 1 | 2 (2^1)|
| 3 | 8 = 1000 | 3 | 8 (2^3)|
| 4 | 16 = 10000 | 4 | 16 (2^4)|
| 5 | 32 = 100000 | 5 | 32 (2^5)| This operation in mainly used in Binary Indexed Trees to move up and down the tree
PS: For some reason stackoverflow is treating table as code :(
