【算法】快速求出 n 最低位的 1
Leetcode 2438. 二的幂数组中查询范围内的乘积
先展示算法具体实现
while (n) {
int lowbit = n & (-n);
powers.push_back(lowbit);
n ^= lowbit;
}
这段代码的核心是通过 n & (-n) 计算出 n 的 最低位的 1（即最右边的 1）
-n是n的二进制补码表示。对于任意整数n，-n等于~n + 1，也就是对n取反然后加 1。n & (-n)的效果是提取n中最右边的 1 对应的那个值。例如，如果n是12（二进制是1100），那么-n是4（二进制是0100），n & (-n)就是4，即n中最低的 1 代表的值。
第四行：n ^= lowbit 则是通过异或运算（^）将 n 中的最低位的 1 清除掉，以继续统计后续的高位的 1 。
看题解的时候发现方法非常巧妙，由此记录。