Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

arunmani.in

Post reply on HN
Print view View original

51–60 of 67 posts

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

#51

Post by gus_massa »

eslaught wrote: post #13
jb1991 wrote: post #6

Earlier 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?

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. https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Modular_arithmetic

I agree, but I just want to add that floating point numbers use sign and magnitude representation, so the GP may be confused by that.

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

#52

Post by StevenXC »

dataflow wrote: post #2

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. Cruci…

Algebraically, where | denotes concatenation, and z is a string of 0s:

x = y | 1 | z

-x = ~x + 1

-x = (~y | 0 | ~z) + 1

-x = ~y | 1 | z

x & -x = (y & ~y) | (1 & 1) | (z & z)

x & -x = 0 | 1 | z

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

#53

Post by School-Cotton »

School-Cotton wrote: post #38
jb1991 wrote: post #6

Earlier 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?

Assuming 4-byte integers, 0000 is 0 0001 is 1 0010 is 2 0011 is 3 0100 is 4 0101 is 5 0110 is 6 0111 is 7 1111 is -1 1110 is -2 1101 is -3 1100 is -4 1011 is -5 1010 is -6 1001 is -7 1000 is -8 The highest bit is always 1 when the sign is negative.

Too late to edit, but I meant 4-bit, not 4-byte.

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

#54

Post by jimbobthrowawy »

mike_hock wrote: post #42
xjay wrote: post #12

See 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 portabili…

I think a bunch of compilers nowadays are smart enough to see these kinds of hacks and compile them to an equivalent on the target that runs best. Favourite example of this is writing a duff's device to unroll a loop, and then gcc completely ignores it and replaces it with a vectorised loop.

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

#55

Post by ChuckMcM »

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!

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

#56

Post by wruza »

rokicki wrote: post #50

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?

Iow, we flip some bits in `a`, then do subj, then mask it back to `a`. It’s unclear what it computes in general, but if `b` disturbs the 2-powerness of `a` then I guess we learn that fact by seeing zero. Not sure where to use it.

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

#57

Post by dgfitz »

_proofs wrote: post #43
monktastic1 wrote: post #40

Earlier quoted context omitted.

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.

Seconded, this comment was hugely valuable to me.

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

#58

Post by MaxBarraclough »

dataflow wrote: post #7
jb1991 wrote: post #6

Earlier 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?

Signedness doesn't affect anything here, as long as the representation is in two's complement. The negation of x (i.e. -x) in two's complement is ~x + 1. The interpretation of the bits as signed or unsigned doesn't change any of the following steps.

I think strictly speaking signedness does affect things, assuming we're talking C/C++. If x has type int and were to take the value of INT_MIN, then evaluating -x would result in a signed arithmetic overflow, which is undefined behaviour. (Related: the C standard now insists on use of 2's complement, where it used to permit other schemes.)

If x had type unsigned int, this wouldn't introduce undefined behaviour.

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

#59

Post by rokicki »

wruza wrote: post #56
rokicki wrote: post #50

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?

Iow, we flip some bits in `a`, then do subj, then mask it back to `a`. It’s unclear what it computes in general, but if `b` disturbs the 2-powerness of `a` then I guess we learn that fact by seeing zero. Not sure where to use it.

There's a nice elegant description of what it does, mathematically, and a significant use in Computer Science.

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

#60

Post by School-Cotton »

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

For example:

    #include 
    #include 
    
    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);
    }
Post reply on HN