C++中表达式i&-i的含义与工作原理是什么？

表达式核心含义 #

i & -i的作用是提取整数i二进制表示里最右侧的1所对应的十进制数值，简单说就是拿到i最低有效位的权值。

底层工作原理 #

C++里整数以补码形式存储，这是理解这个表达式的关键：

1. 正数i的补码和原码完全一致；
2. -i的补码是对i的原码按位取反后再加1。

举个实际例子：

• 假设i=5（二进制101），补码是000...000101；
• -i的补码：先对i按位取反得到111...111010，再加1变成111...111011；
• 两者按位与（&）运算：000...000101 & 111...111011 = 000...000001，对应十进制1，正好是i最右侧1的数值。

再看i=8（二进制1000）：

• -i的补码是111...1111000；
• 按位与结果为1000，也就是8，和i自身相等，因为它只有最右侧一个1。

示例代码与运行结果分析 #

示例代码 #

#include <iostream>
#include <vector>
using namespace std;
void print(int i){
    vector <int> a;
    while (i){
        a.push_back(i%2);
        i/=2;
    }
    for (int i=a.size()-1; i>=0; i--)
        cout<<a[i];
}
int main() {
    
    for (int i=1000; i>0; i-=(i&-i)){
        cout<<i<<' '<<int(i&i)<<' '<<int(i&-i)<<' ';
        print(i); cout<<' '; print(int(i&-i));
        cout<<'\n';
    }
    cout<<'\n';
    for (int i=5; i<=1000; i+=(i&-i)){
        cout<<i<<' '<<int(i&-i)<<' ';
        print(i); cout<<' '; print(int(i&-i));
        cout<<'\n';
    }
    return 0;
}

运行结果拆解 #

第一个递减循环（从1000开始）

每次循环减去i&-i，本质是逐步消除i二进制里最右侧的1：

• 1000（二进制1111101000）的i&-i是8（1000），减去后得到992（1111100000）；
• 992的i&-i是32（100000），减去后得到960（1111000000）；
• 以此类推，直到剩下512（1000000000），此时i&-i等于自身，减去后i变为0，循环终止。

第二个递增循环（从5开始）

每次循环加上i&-i，相当于把最右侧的1向左进位扩展：

• 5（101）的i&-i是1，相加后得到6（110）；
• 6的i&-i是2，相加后得到8（1000）；
• 后续每次累加的都是当前数最右侧1的数值，最终快速增长到512。

常见应用场景 #

这个表达式最常用在**树状数组（Fenwick Tree）**的实现中，用来快速定位节点的父/子节点，高效完成前缀和查询、单点更新等操作。

内容的提问来源于stack exchange，提问作者Yuu Chan