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

31–40 of 67 posts

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

#31

Post by bonzini »

chx wrote: post #28
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.

> -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…

The point of two's complement is that it's the same as modulo-2^n arithmetic. In two's complement -x is defined such that x + -x = 0 (mod 2^n); and because x + ~x = 2^n - 1 (mod 2^n), then -x = ~x + 1.

Therefore x & -x works only in two's complement, and it's fair to assume it as the parent comment did.

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

#33

Post by wruza »

Because to negate you invert (so & = 0) and add one, which overflows former zeroes until it meets a former one, which flips, so & gives 1 there. Former zeroes are how even a number is.

  01100 (12, 2 bit even)
  10011 (inv 12, & = 0)
  10100 (inv 12 +1 aka -12)
  00100 &, 2 bit even

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

#34

Post by baryphonic »

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…

When I read the title, my immediate thought was "because 2s complement!"

Your explanation is more thorough.

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

#35

Post by kbolino »

thaumasiotes wrote: post #19
cvz wrote: post #16

Earlier quoted context omitted.

In the "two's complement" representation, there is a sign bit, but the meaning isn't "invert this number", it's "subtract a large, fixed power of 2 from this number". The reason this has become the most common representation for signed numbers in computer hardware is that it makes the difference between signed and unsigned numbers basically irrelevant as far as the hardware is concerned. When the difference does matt…

> n the "two's complement" representation, there is a sign bit, but the meaning isn't "invert this number", it's "subtract a large, fixed power of 2 from this number". This is only true if the size of your modulus is fixed. In fact, there is a "sign extension" command allowing you to produce, for example, signed 128-bit values from signed 64-bit values, and this basically requires interpreting two's complement values…

This is true mathematically but simple to implement in practice. If the number is signed, shifts to the right and widening casts fill the new bits with a copy of the sign bit. If it's unsigned, shifts to the right and widening casts fill the new bits with zeroes. Shifts to the left and narrowing casts work the same for signed and unsigned.

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

#37

Post by layer8 »

omnicognate wrote: post #24

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. usi…

From https://en.wikipedia.org/wiki/Method_of_complements:

“Some people, notably Donald Knuth, recommend using the placement of the apostrophe to distinguish between the radix complement and the diminished radix complement. In this usage, the four's complement refers to the radix complement of a number in base four while fours' complement is the diminished radix complement of a number in base 5. However, the distinction is not important when the radix is apparent (nearly always), and the subtle difference in apostrophe placement is not common practice. Most writers use one's and nine's complement, and many style manuals leave out the apostrophe, recommending ones and nines complement.”

I.e., the distinction isn’t as well established as some claim, and in the context of binary presentations it doesn’t really matter.

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

#38

Post by School-Cotton »

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?

Assuming 4-byte integers,

0000 is 0

0001 is 1

0010 is 2

0011 is 3

0100 is 4

0101 is 5

0110 is 6

0111 is 7

1111 is -1

1110 is -2

1101 is -3

1100 is -4

1011 is -5

1010 is -6

1001 is -7

1000 is -8

The highest bit is always 1 when the sign is negative.

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

#40

Post by monktastic1 »

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…

Another, more "visual" description:

Without loss of generality, let the number be xx...xx100...000, where x stands for any bit and there are n trailing zeros.

1. The largest power of 2 that divides it is 2^n.

2. The twos-complement representation is xx...xx011...111, where the x's are inverted from before, plus one.

3. After adding one, we get xx...xx100...000. Notice that the carryover stopped exactly where the zero was (which is where our first 1 from the right originally was).

4. All the "x" bits are now inverted from their original values, so their & is zero. All the original trailing zero bits are still zero, so their & is zero. The middle 1 has stayed 1, so its & is 1.

5. Thus, the overall & is 00...00100...000 = 2^n, as required.

Post reply on HN