Does the site actually mention the book it was in?
Why is x & -x equal to the largest power of 2 that divides x?
11–20 of 67 posts
Re: Why is x & -x equal to the largest power of 2 that divides x?
#12See also: Bit Twiddling Hacks
Re: Why is x & -x equal to the largest power of 2 that divides x?
#13Short 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?
You're thinking about a sign and magnitude representation, which is not how integers are represented in a modern computer.
The modern version is two's complement. It still has a sign bit, but negating a number involves more than just changing the sign bit since the representation is modular.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#14Short 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…
Thanks! I've used the trick and derived why it works a few times, but always forget.
I battled to understand the post. Your explanation got me there very quickly.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#15Short 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.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#16Short 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?
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 matter (which it does in division, conversions between different word sizes, conversions to/from text, and sometimes multiplication), there are two different instructions for signed and unsigned, and it's up to the programmer or compiler to pick the right one.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#17Short 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…
Thanks! I've used the trick and derived why it works a few times, but always forget. I battled to understand the post. Your explanation got me there very quickly.
Sure thing, happy to hear!
Re: Why is x & -x equal to the largest power of 2 that divides x?
#18Short 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?
2s compliment helps with the problem of otherwise having a +0/-0 and lets you subtract numbers just with adders.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#19Earlier quoted context omitted.
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?
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 the same way they represent themselves: a three-bit -1 is just the sum of the positive values +1, +2, and +4. To extend that to six bits, you add the positive values +8, +16, and +32.
The meaning of the high bit in our six-bit scheme shouldn't be viewed as "when this bit is set, subtract 32 from the value instead of adding it". It is "whether this bit is set or not, all higher bits in the number, the ones that don't exist in the hardware, are equal to it"; under this interpretation, the 8-, 16-, and 32- bits were already set in the three-bit value, and that's why they continue to be set when we do a sign extension.
Every place value is still positive, but as long as there is no highest set bit, the number itself will be negative, and equal to the value you'd calculate from its representation as a geometric series.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#20Short 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…
Thanks for the nice summary. I found myself difficult to explain it so I took the help of visual explanation using the bits structure. :)