为什么（n＆-n）== n那么n是2的幂？

为什么（n＆-n）== n那么n是2的幂？

该描述并不完全准确，因为

(0 & -0) == 0

0不是2的幂。更好的说法是

((n & -n) == n)

当n是2的幂或2的幂的负数或零时。

如果n是2的幂，则二进制中的n是单个1，后跟零。-n为2的补数是倒数+ 1，因此位排成一行

 n      0000100...000-n      1111100...000 n & -n 0000100...000

要了解其工作原理，请将二进制补码视为逆+ 1。

-n == ~n + 1

n          0000100...000inverse n  1111011...111          + 1two's comp 1111100...000

因为当您添加一个得到两个的补码时，您会一直进行到一个。

如果n不是2的幂，则结果将丢失一点，因为由于进位，两个补码的最高位不会置位。

†-或零或2的幂的负数…如顶部所述。