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.

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. — , Mar 13 '13 at 20:03
@Cthulhu, I have but it was a very long time ago. C++ hadn't been invented yet. — Mark Ransom, Mar 13 '13 at 20:07
@H2CO3 http://www.codechef.com/viewsolution/1856173 It is used in the following code but, i am unable to get why it is used :( — Shubham Tyagi, Mar 13 '13 at 20:07
@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 :) — Frédéric Hamidi, Mar 13 '13 at 20:08

Mark Ransom · Answer 1 · 2013-03-13T20:48:26.367

34

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)

edited Mar 13 '13 at 20:48

answered Mar 13 '13 at 20:13

Mark Ransom

299,747
42
398
622

1

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)` – Aki Suihkonen Mar 13 '13 at 20:17
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 – pooley1994 Sep 06 '19 at 15:32
1

@pooley1994 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. – Mark Ransom Sep 06 '19 at 18:35

score 9 · Answer 2 · answered Mar 13 '13 at 20:07

9

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.

answered Mar 13 '13 at 20:07

Benjamin Lindley

101,917
9
204
274

but beware that it is dependent on implementation defined behavior, so is technicaly not portable. – tletnes Mar 13 '13 at 20:10
3

@tletnes 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 – Benjamin Lindley Mar 13 '13 at 20:12
@tletnes 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. – Mark Ransom Nov 25 '20 at 04:31

score 4 · Answer 3 · answered Jul 16 '18 at 11:28

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

score 3 · Accepted Answer · answered Mar 13 '13 at 20:10

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

answered Mar 13 '13 at 20:10

c.fogelklou

1,781
1
13
26

1

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. – JasonD Mar 13 '13 at 20:27
2

`(n&(n-1))==0` would have been more simple. – Jyothrilinga K Aug 21 '17 at 03:03

score 2 · Answer 5 · answered Mar 13 '13 at 20:11

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

answered Mar 13 '13 at 20:11

aestrivex

5,170
2
27
44

score 0 · Answer 6 · edited May 23 '17 at 10:29

0

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`

edited May 23 '17 at 10:29

Community

1
1

answered Jan 13 '16 at 13:37

leodido

912
7
21

score -1 · Answer 7 · answered Jan 31 '18 at 06:20

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.

score -3 · Answer 8 · answered Dec 27 '15 at 09:01

-3

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

answered Dec 27 '15 at 09:01

Diffy

2,339
3
25
47

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

8 Answers8

Linked