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

Short explanation:<p>1. The largest power of 2 that divides x is just 2^(number of trailing zeros in x)<p>2. Crucial observation: -x == ~x + 1<p>3. ~x flips all the bits of x bits, so none of the bits of ~x match those of x. (i.e. (x &amp; ~x) == 0)<p>4. When you do +1, all the trailing 1&#x27;s flip AGAIN, becoming zero like they were in x. The next highest 0 (say it was the n&#x27;th) also flips, becoming 1... like it was in x.<p>5. Crucial observation: The n&#x27;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.<p>6. This leaves only the n&#x27;th bits matching in x and ~x + 1, isolating the highest power-of-2 divisor of x when you AND them.

Or briefly, copied from my StackOverflow answer[1]:<p><pre><code> 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&amp;-v 000...00000100 (has a single 1 bit, from the carry) </code></pre> 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.<p>[1]: <a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;63552117&#x2F;1405588" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;63552117&#x2F;1405588</a>

Grammar nazi correction, but one I think is both interesting and a useful way to remember how these work: ones&#x27; complement has the apostrophe at the end (but two&#x27;s complement is correct).<p>Ones&#x27; complement is the &quot;complement of ones (plural)&quot; 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.<p>Two&#x27;s complement is the &quot;complement of two (to the n)&quot; 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.

Note that this gives 0 when x == O. For applications where you need the largest power of 2 that divides x because you are going to actually divide x by that you may want to check for 0 first.

It is a simple trick, but in practice you probably want to know the position of the last nonzero bit instead of the 2^n pattern. And most CPUs have instructions for that, which are more efficient and as a bonus also document better what is happening.

Nice article, which is putatively about the question posed, but really is about how fun number theory can be. This trick and the &quot;reverse the order of bits with XOR&quot; kinds of things are gateways into the properties of numbers and their bases. Base 2 happens to be &quot;easy&quot; because you can use simple boolean functions to move it around but once you get the hang of it you can do this with other bases as well.<p>I really didn&#x27;t appreciate number theory until I started writing cryptography code and trying to understand some of the &#x27;tricks&#x27; used to optimize the algorithms. Fun stuff!

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!

It&#x27;s easy to see when a number is divisible by 2 in binary,<p>just like in decimal: 70 is divisible by 10, 500 is divisible by 100,<p>so in binary 10 is divisible by 2 10100 is divisible by 4 101010111000 is divisible by 8 etc. (We also know 101010111001 can&#x27;t be divisible by 8, cause it&#x27;s only 1 more than a number divisible by 8)<p>Knowing this we can look at the question backwards take 24 and -24, because 24 is divisible by 8 it must end with a 1 and 3 0s ...0011000<p>when we take the compliment we get 1100111 which for the same reason must end in a 0 and a run of 1s,<p>now when we add one to this, all the ones will roll over and we end up with the same tail &quot;1000&quot; as in 24, and since this anything to the left of the tail is a compliment of the corresponding bit in x a bitwise and will just be the tail.

Because to negate you invert (so &amp; = 0) and add one, which overflows former zeroes until it meets a former one, which flips, so &amp; gives 1 there. Former zeroes are how even a number is.<p><pre><code> 01100 (12, 2 bit even) 10011 (inv 12, &amp; = 0) 10100 (inv 12 +1 aka -12) 00100 &amp;, 2 bit even</code></pre>

See also: Bit Twiddling Hacks<p><a href="https:&#x2F;&#x2F;graphics.stanford.edu&#x2F;~seander&#x2F;bithacks.html" rel="nofollow">https:&#x2F;&#x2F;graphics.stanford.edu&#x2F;~seander&#x2F;bithacks.html</a>

One reason why this is useful is it lets you iterate through the set bits of a number.<p>For example:<p><pre><code> #include &lt;stdlib.h&gt; #include &lt;stdio.h&gt; void decompose_bits(unsigned x) { while (x) { unsigned bit = x &amp; -x; printf(&quot;0x%x (%u)\n&quot;, bit, bit); x -= bit; } } int main(int argc, char *argv[]) { unsigned x = atoi(argv[1]); decompose_bits(x); }</code></pre>

This is a fun puzzle to try to figure out before reading the article.

To take this to the next level: what does [(a^b) &amp; (-(a^b)) &amp; a] compute? (Assume unsigned arithmetic.)<p>And then after that: what use can this be put to?

Carry. -x is ~x (not x) PLUS ONE<p>It&#x27;s that carry that ripples through, making bits flip until it gets to that &#x27;largest power of 2&#x27;

Does the site actually mention the book it was in?

Good explanation. Always good to read up on some bit tweaking once a while.

This meeting could have been a post it note.