Meaning of bitwise and(&) of a positive and negative number?

StackOverflow https://stackoverflow.com/questions/15395317

  •  23-03-2022
  •  | 
  •  

Question

Can anyone help what n&-n means?? And what is the significance of it.

Was it helpful?

Solution 3

I believe it is a trick to figure out if n is a power of 2. (n == (n & -n)) IFF n is a power of 2 (1,2,4,8).

OTHER TIPS

It's an old trick that gives a number with a single bit in it, the bottom bit that was set in n. At least in two's complement arithmetic, which is just about universal these days.

The reason it works: the negative of a number is produced by inverting the number, then adding 1 (that's the definition of two's complement). When you add 1, every bit starting at the bottom that is set will overflow into the next higher bit; this stops once you reach a zero bit. Those overflowed bits will all be zero, and the bits above the last one affected will be the inverse of each other, so the only bit left is the one that stopped the cascade - the one that started as 1 and was inverted to 0.

P.S. If you're worried about running across one's complement arithmetic here's a version that works with both:

n & (~n + 1)

On pretty much every system that most people actually care about, it will give you the highest power of 2 that n is evenly divisible by.

N&(-N) will give you position of the first bit '1' in binary form of N. For example:

N = 144 (0b10010000) => N&(-N) = 0b10000
N = 7 (0b00000111) => N&(-N) = 0b1

One application of this trick is to convert an integer to sum of power-of-2. For example:

To convert 22 = 16 + 4 + 2 = 2^4 + 2^2 + 2^1
22&(-22) = 2, 22 - 2 = 20
20&(-20) = 4, 20 - 4 = 16
16&(-16) = 16, 16 - 16 = 0

It's just a bitwise-and of the number. Negative numbers are represented as two's complement.

So for instance, bitwise and of 7&(-7) is x00000111 & x11111001 = x00000001 = 1

I would add a self-explanatory example to the Mark Randsom's wonderful exposition.

010010000 | +144 ~
----------|-------
101101111 | -145 +
        1 |
----------|-------
101110000 | -144 

101110000 | -144 & 
010010000 | +144
----------|-------
000010000 |   16`

Because x & -x = {0, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32} for x from 0 to 32. It is used to jumpy in the for sequences for some applications. The applications can be to store accumulated records.

for(;x < N;x += x&-x) {
    // do something here
    ++tr[x];
}

The loop traverses very fast because it looks for the next power of two to jump.

As @aestrivex has mentioned, it is a way of writing 1.Even i encountered this 

for (int y = x; y > 0; y -= y & -y)

and it just means y=y-1 because
7&(-7) is x00000111 & x11111001 = x00000001 = 1

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top