This was a real joy to read. Especially kudos for the (I guess already oldschool?) plain text figures. I was reading this with lynx (as I stll frequently use it) and totally enjoyed the flawless accessibility of this article. Whatever the motivation, thanks for putting out content like this, it is totally appreciated!
Why is x & -x equal to the largest power of 2 that divides x?
41–50 of 67 posts
Re: Why is x & -x equal to the largest power of 2 that divides x?
#42See also: Bit Twiddling Hacks https://graphics.stanford.edu/~seander/bithacks.html
> Compute the sign of an integer
> On the other hand, if you prefer the result be either -1, 0, or +1, then use:
> sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));
> // Or, for more speed but less portability:
> sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1)); // -1, 0, or +1
> // Or, for portability, brevity, and (perhaps) speed:
> sign = (v > 0) - (v Or if you prefer portability, speed, and readability at the same time:
int sign(int i) {
if(i > 0)
return 1;
else if(i mov ecx, edi
sar ecx, 31
test edi, edi
mov eax, 1
cmovle eax, ecx
ret
(still useful as a reference for implementing an optimizer, to be read as pseudo code)
Re: Why is x & -x equal to the largest power of 2 that divides x?
#43Short 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 zer…
this is actually a fantastic comment and as someone who thinks more visually, was greatly appreciated. thank you.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#44Short 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…
> 2. Crucial observation: -x == ~x + 1
To be annoyingly pedantic, this is not simply an observation, this is essentially the definition of 2's complement arithmetic.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#45Carry. -x is ~x (not x) PLUS ONE
It's that carry that ripples through, making bits flip until it gets to that 'largest power of 2'
Re: Why is x & -x equal to the largest power of 2 that divides x?
#46Short 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…
> 2. Crucial observation: -x == ~x + 1 To be annoyingly pedantic, this is not simply an observation, this is essentially the definition of 2's complement arithmetic.
Some people do see it that way, and I think it's fine if you do, but I think I disagree. To me, the definition of N-bit two's complement is that -x (i.e. 0 - x) is represented by 2^N - x. The fact that that is equal to ~x + 1 is not obvious, or (as I see it) part of the definition.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#47This was a real joy to read. Especially kudos for the (I guess already oldschool?) plain text figures. I was reading this with lynx (as I stll frequently use it) and totally enjoyed the flawless accessibility of this article. Whatever the motivation, thanks for putting out content like this, it is totally appreciated!
Aww thanks! Actually we both should thank Hugo for converting the MarkDown into a very simple HTML structure. I also try to follow semantic web whenever possible (article, header, footer etc. instead of divsoup).
Very glad to know the site works well with Lynx!
Re: Why is x & -x equal to the largest power of 2 that divides x?
#48Or 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! :)
I find this a pretty confusing explanation because the actual mechanism is buried in the middle and you can't understand the first diagram without it.
The goal is to produce the number `0...010...0` with the same number of trailing zeroes as x.
If you flip all the bits in x, then `...10...0` turns into `...01...1`. Adding one cascades the tail into `...10...0`.
You can do this entirely in unsigned math and you don't need to drag two's complement into it. The fact that it corresponds to `x & -x` is a curiosity, and then you have to explain why it works for e.g. negative numbers, where it counts trailing ones instead but still produces a positive.
There are plenty of other tricks like this, e.g. `x & (x - 1) == 0` tells you if a (non-zero) x is a power of two, but it doesn't work for negatives.
Re: Why is x & -x equal to the largest power of 2 that divides x?
#49Short 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…
[deleted]
Re: Why is x & -x equal to the largest power of 2 that divides x?
#50To take this to the next level: what does [(a^b) & (-(a^b)) & a] compute? (Assume unsigned arithmetic.)
And then after that: what use can this be put to?