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

21–30 of 67 posts

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

#21

Post by arun-mani-j »

o11c wrote: post #4

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…

I tried to explain only one's complement and two's complement because they were only relevant to the explanation.

TIL we have 5 such representations! :)

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

#23

Post by Droobfest »

pbsd wrote: post #15
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…

An alternative, more arithmetic, argument: - x is 2^b*k for some odd k - -x is 2^n - 2^b*k = 2^b*(2^(n-b)-k) - k is odd by definition, and (2^(n-b)-k) + k = 0 (mod 2^(n-b)). This means that the LSB must be 1 in both operands, which results in a carry out, and in the following ith bits we have that the sum is 0 mod 2^i if and only if the ith bits of (2^(n-b)-k) and k are distinct. Thus x & -x = 2^b.

This immediately reads like gobbledygook to me, while the parent is easy to follow.

I’m not trying to dunk on you, but I can’t help to note that the denseness of math is too much for an idiot like me.

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

#24

Post by omnicognate »

Grammar nazi correction, but one I think is both interesting and a useful way to remember how these work: ones' complement has the apostrophe at the end (but two's complement is correct).

Ones' complement is the "complement of ones (plural)" in that if you take an n-bit number and the representation of its additive inverse in that scheme and add them as ordinary binary numbers you get a result that is n ones. Eg. using 4 bits, 6 is 0110, -6 is 1001, adding them with ordinary binary addition gives 1111.

Two's complement is the "complement of two (to the n)" in that if you do the same thing you get 2^n. Eg. 6 is 0110, -6 is 1010, adding them with ordinary binary addition gives 10000, or 2^4.

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

#25

Post by lifthrasiir »

o11c wrote: post #4

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…

And then we have a zig-zag bijection for too many serialization formats.

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

#26

Post by IshKebab »

lifthrasiir wrote: post #25
o11c wrote: post #4

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…

And then we have a zig-zag bijection for too many serialization formats.

Why too many? It's a neat trick.

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

#28

Post by chx »

pbsd wrote: post #15
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…

An alternative, more arithmetic, argument: - x is 2^b*k for some odd k - -x is 2^n - 2^b*k = 2^b*(2^(n-b)-k) - k is odd by definition, and (2^(n-b)-k) + k = 0 (mod 2^(n-b)). This means that the LSB must be 1 in both operands, which results in a carry out, and in the following ith bits we have that the sum is 0 mod 2^i if and only if the ith bits of (2^(n-b)-k) and k are distinct. Thus x & -x = 2^b.

> -x is 2^n - 2^b * k

Erm no. -x is - 2^b * k and it's the "Two's complement" notation which is 2^n - 2 * b * k

This is because the way we generate the "Two's complement" number. Given A in binary representation, let's call A1 the number you get by flipping every bit in A also called one's complement. Observe how every bit in A+A1 is 1 because if the bit was 0 in A then the bit is 1 in A1 and vica versa. So then that's 2^N-1. Two's complement is created by adding 1 to A1 so then A + A1 is 2^N or A1 = 2^N-A. But you do need to prove this before you can use it.

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

#29

Post by schoen »

Droobfest wrote: post #23
pbsd wrote: post #15

Earlier quoted context omitted.

An alternative, more arithmetic, argument: - x is 2^b*k for some odd k - -x is 2^n - 2^b*k = 2^b*(2^(n-b)-k) - k is odd by definition, and (2^(n-b)-k) + k = 0 (mod 2^(n-b)). This means that the LSB must be 1 in both operands, which results in a carry out, and in the following ith bits we have that the sum is 0 mod 2^i if and only if the ith bits of (2^(n-b)-k) and k are distinct. Thus x & -x = 2^b.

This immediately reads like gobbledygook to me, while the parent is easy to follow. I’m not trying to dunk on you, but I can’t help to note that the denseness of math is too much for an idiot like me.

It might be nicer with exponents rendered as superscripts, because it could make it more apparent how the exponents are being used.
Post reply on HN