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

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. Crucial observation: The n'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.

6. This leaves only the n'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]:

  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)

[1]: https://stackoverflow.com/a/63552117/1405588

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. using 4 bits, 6 is 0110, -6 is 1001, adding them with ordinary binary addition gives 1111.

Two's complement is the "complement of two (to the n)" 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 "reverse the order of bits with XOR" kinds of things are gateways into the properties of numbers and their bases. Base 2 happens to be "easy" 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.

I really didn't appreciate number theory until I started writing cryptography code and trying to understand some of the 'tricks' 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's easy to see when a number is divisible by 2 in binary,

just like in decimal: 70 is divisible by 10, 500 is divisible by 100,

so in binary 10 is divisible by 2 10100 is divisible by 4 101010111000 is divisible by 8 etc. (We also know 101010111001 can't be divisible by 8, cause it's only 1 more than a number divisible by 8)

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

when we take the compliment we get 1100111 which for the same reason must end in a 0 and a run of 1s,

now when we add one to this, all the ones will roll over and we end up with the same tail "1000" 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 & = 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

See also: Bit Twiddling Hacks

https://graphics.stanford.edu/~seander/bithacks.html

One reason why this is useful is it lets you iterate through the set bits of a number.

For example:

    #include <stdlib.h>
    #include <stdio.h>
    
    void decompose_bits(unsigned x) {
        while (x) {
            unsigned bit = x & -x;
            printf("0x%x (%u)\n", bit, bit);
            x -= bit;
        }
    }
    
    int main(int argc, char *argv[]) {
        unsigned x = atoi(argv[1]);
        decompose_bits(x);
    }

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) & (-(a^b)) & a] compute? (Assume unsigned arithmetic.)

And then after that: what use can this be put to?

Carry. -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'

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.