meaning of (number) & (-number)

Question

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))

Answer 1

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

Answer 2

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 0100

You can see from the example above that (number) & (-number) gives you the least bit.

You can see the code run online on IDE One: http://ideone.com/WzpxSD

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: https://dotnetfiddle.net/ai7Eq6

Answer 3

I 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 bit

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

Answer 4

The operation i & -i is used for isolating the least significant non-zero bit of the corresponding integer.

• In binary notation num can be represented as a1b, where a represents binary digits before the last bit and b represents zeroes after the last bit.

• -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ 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 :(