c++11 - 按位 AND 计算除以“n”的 2 的最大幂 - C++

Question

在阅读二进制索引树时，我遇到了以下表达式，该表达式神奇地计算出除以给定数字“n”的 2 的最大幂

n&-n

我想要一个正式的论点，为什么这个表达式正在做它所做的事情。此外，使用按位运算符有很多这样的技巧，可以节省我们很多时间并派上用场。请列出你知道的尽可能多的人。
例如， 1 << n 给出 2 的 n 次幂。

标签： c++11bitwise-operators

Answer 1

回答我自己的问题，我无法找到一个非常复杂的解决方案，但这让我很满意
让除以n2 ^k的二的最高幂。
这意味着k在最后一个 1 之后有零（如果没有，它给出 n=0 并且 n&-n 也为零，这是正确的）。

-n = ~n+1，因此 n 中的所有数字都被反转，除了最后一个和后面的k零。

采用按位与将导致最后一个后跟 k 个零，即 2 ^k。
我发现的一些使用按位运算符的技巧是：

x | (1 << k) 将第 k 位设置为 1

x & ~(1 << k) 将第 k 位设置为零

x ^ (1 << k) 反转第 k 位

x & (x−1) 将 x 的最后一位设置为零

x &−x 将所有 1 位设置为零，除了最后一位。

当 x & (x−1) = 0 时，正数 x 正好是 2 的幂。

公式 x | (x−1) 反转最后一位之后的所有位

这些可以用类似的证明来证明。当我遇到更多时，我会添加更多。