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

Question

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

Cupulate

It may cause undefined behavior or simply result in an unspecified and/or implementation defined value depending on the value of n and the representation of negative numbers (i. e. 1's complement vs. 2's complement). I'm sure it's something you don't want to use/encounter. – Soandso

I haven't ever seen a real 1's complement machine. – Szeged

@Cthulhu, I have but it was a very long time ago. C++ hadn't been invented yet. – Aryn

@H2CO3 codechef.com/viewsolution/1856173 It is used in the following code but, i am unable to get why it is used :( – Cupulate

@Cthulhu, I think there are still embedded systems that use one's complement. And even if they're all dead, it doesn't mean you won't see more in the future :) – Yttria

@ShubhamTyagi Because that site is crap, that's why. – Soandso

Answer 1

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

Amino

Well that doesn't entirely work as it would return true for zero, which isn't generally considered a power of two. And the trick is more useful than that - see the other answers. – Acuminate

(n&(n-1))==0 would have been more simple. – Ratan

Answer 2

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)

Aryn

Yes, and that's handy if e.g. one wants to quickly iterate over all bits set in n; for (;j=n&(-n);n^=j) – Heifetz

It's probably vernacular to say "bottom bit", but to put this in a way that was clearer (at least in my own mind): the resulting number has at most one bit set, and it is the least significant bit that was set in the original number – Roughen

@Roughen thanks for that. I've been thinking in terms of "bottom bit" for so long that I couldn't tell you where I picked it up; I can't claim it's universally understood. – Aryn

Answer 3

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.

Childlike

but beware that it is dependent on implementation defined behavior, so is technicaly not portable. – Consolute

@Consolute Portability is a relative term. It's not portable as far as the C++ standard is concerned, true. But it is probably portable across more systems than even have a conformant, or nearly conformant C++ compiler – Childlike

@Consolute I was told recently here on SO that C++20 mandates two's-complement integers, so the behavior will be more consistent in the future. – Aryn

Answer 4

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

Stairs

Answer 5

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

Incantation

Answer 6

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`

Homonym

Answer 7

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.

Cleancut

Answer 8

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

Strength