<story><title>Why is x &amp; -x equal to the largest power of 2 that divides x?</title><url>https://arunmani.in/articles/highest-two-power-to-divide-a-number/</url></story><parent_chain></parent_chain><comment><author>dataflow</author><text>Short explanation:&lt;p&gt;1. The largest power of 2 that divides x is just 2^(number of trailing zeros in x)&lt;p&gt;2. Crucial observation: -x == ~x + 1&lt;p&gt;3. ~x flips all the bits of x bits, so none of the bits of ~x match those of x. (i.e. (x &amp;amp; ~x) == 0)&lt;p&gt;4. When you do +1, all the trailing 1&amp;#x27;s flip AGAIN, becoming zero like they were in x. The next highest 0 (say it was the n&amp;#x27;th) also flips, becoming 1... like it was in x.&lt;p&gt;5. Crucial observation: The n&amp;#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.&lt;p&gt;6. This leaves only the n&amp;#x27;th bits matching in x and ~x + 1, isolating the highest power-of-2 divisor of x when you AND them.</text></comment>
<story><title>Why is x &amp; -x equal to the largest power of 2 that divides x?</title><url>https://arunmani.in/articles/highest-two-power-to-divide-a-number/</url></story><parent_chain></parent_chain><comment><author>o11c</author><text>Or briefly, copied from my StackOverflow answer[1]:&lt;p&gt;&lt;pre&gt;&lt;code&gt;  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;amp;-v 000...00000100 (has a single 1 bit, from the carry)
&lt;/code&gt;&lt;/pre&gt;
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.&lt;p&gt;[1]: &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;stackoverflow.com&amp;#x2F;a&amp;#x2F;63552117&amp;#x2F;1405588&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;stackoverflow.com&amp;#x2F;a&amp;#x2F;63552117&amp;#x2F;1405588&lt;/a&gt;</text></comment>