Meaning of bitwise and(&) of a positive and negati

Question

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

Answer 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`

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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)