| 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 zero was (which is where our first 1 from the right originally was). 4. All the "x" bits are now inverted from their original values, so their & is zero. All the original trailing zero bits are still zero, so their & is zero. The middle 1 has stayed 1, so its & is 1. 5. Thus, the overall & is 00...00100...000 = 2^n, as required. |