Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why is x & -x equal to the largest power of 2 that divides x?

arunmani.in

Post reply on HN
Print view View original

1–10 of 67 posts

Re: Why is x & -x equal to the largest power of 2 that divides x?

#2

Post by dataflow »

Short explanation:

1. The largest power of 2 that divides x is just 2^(number of trailing zeros in x)

2. Crucial observation: -x == ~x + 1

3. ~x flips all the bits of x bits, so none of the bits of ~x match those of x. (i.e. (x & ~x) == 0)

4. When you do +1, all the trailing 1's flip AGAIN, becoming zero like they were in x. The next highest 0 (say it was the n'th) also flips, becoming 1... like it was in x.

5. Crucial observation: The n'th 0 did NOT match the corresponding bit in x prior to the increment, therefore it MUST match after the increment. All higher bits stay as-is.

6. This leaves only the n'th bits matching in x and ~x + 1, isolating the highest power-of-2 divisor of x when you AND them.

Re: Why is x & -x equal to the largest power of 2 that divides x?

#4

Post by o11c »

Or briefly, copied from my StackOverflow answer[1]:

  v    000...00010100
  ~v   111...11101011 (not used directly, all bits opposite)
  -v   111...11101100 (-v == ~v + 1; this causes all low 1 bits to overflow and carry)
  v&-v 000...00000100 (has a single 1 bit, from the carry)
The linked article is wrong in only mentioning 2 signed integer representations. Old versions of C allowed 3 representations for integers, floats use one of those (sign-magnitude, also used widedly by bignum libraries) and one other (offset binary), and base negative-2 is also possible in theory (not sure if practical for anything), for a total of 5.

[1]: https://stackoverflow.com/a/63552117/1405588

Re: Why is x & -x equal to the largest power of 2 that divides x?

#6

Post by jb1991 »

dataflow wrote: post #2

Short explanation: 1. The largest power of 2 that divides x is just 2^(number of trailing zeros in x) 2. Crucial observation: -x == ~x + 1 3. ~x flips all the bits of x bits, so none of the bits of ~x match those of x. (i.e. (x & ~x) == 0) 4. When you do +1, all the trailing 1's flip AGAIN, becoming zero like they were in x. The next highest 0 (say it was the n'th) also flips, becoming 1... like it was in x. 5. Cruci…

I thought there was just a sign bit. If not, how does a system know if a number should be interpreted as positive or negative?

Re: Why is x & -x equal to the largest power of 2 that divides x?

#7

Post by dataflow »

jb1991 wrote: post #6
dataflow wrote: post #2

Short explanation: 1. The largest power of 2 that divides x is just 2^(number of trailing zeros in x) 2. Crucial observation: -x == ~x + 1 3. ~x flips all the bits of x bits, so none of the bits of ~x match those of x. (i.e. (x & ~x) == 0) 4. When you do +1, all the trailing 1's flip AGAIN, becoming zero like they were in x. The next highest 0 (say it was the n'th) also flips, becoming 1... like it was in x. 5. Cruci…

I thought there was just a sign bit. If not, how does a system know if a number should be interpreted as positive or negative?

Signedness doesn't affect anything here, as long as the representation is in two's complement. The negation of x (i.e. -x) in two's complement is ~x + 1. The interpretation of the bits as signed or unsigned doesn't change any of the following steps.

Re: Why is x & -x equal to the largest power of 2 that divides x?

#8

Post by elevatedastalt »

jb1991 wrote: post #6
dataflow wrote: post #2

Short explanation: 1. The largest power of 2 that divides x is just 2^(number of trailing zeros in x) 2. Crucial observation: -x == ~x + 1 3. ~x flips all the bits of x bits, so none of the bits of ~x match those of x. (i.e. (x & ~x) == 0) 4. When you do +1, all the trailing 1's flip AGAIN, becoming zero like they were in x. The next highest 0 (say it was the n'th) also flips, becoming 1... like it was in x. 5. Cruci…

I thought there was just a sign bit. If not, how does a system know if a number should be interpreted as positive or negative?

There's still a sign bit. The sign bit tells you whether to interpret the rest of the number as positive or treat as negative and undo the 2s complement operation.
Post reply on HN