C语言中k-=(k & (-k))语句的含义是什么？附求和函数疑问

嘿，这个操作其实是树状数组（Fenwick Tree）里的核心操作之一，咱们拆开来一步步看：

第一步：先搞懂 k & -k 做了什么 #

在C语言里，整数是以补码形式存储的。对于任意正整数k，-k的补码等于~k + 1（对k的二进制取反，再加1）。

当你对k和-k做按位与操作时，会得到一个非常特殊的结果：只保留k的二进制表示中最右边的那个1，其余位都变成0。

举几个直观的例子：

• 如果k = 6（二进制110），-k的补码是...11111010，按位与后得到010（也就是十进制的2）
• 如果k = 5（二进制101），-k的补码是...11111011，按位与后得到001（十进制的1）
• 如果k = 8（二进制1000），-k的补码是...11111000，按位与后得到1000（十进制的8）

第二步：k -= k & -k 的效果 #

明白了k & -k的作用后，这个减法操作的意义就很清晰了：把k的二进制中最右边的那个1给清除掉。

还是用刚才的例子：

• k=6，减去2后变成4（二进制从110变成100，最右边的1没了）
• k=5，减去1后变成4（二进制从101变成100）
• k=8，减去8后变成0（直接把唯一的1清除，循环终止）

结合你的函数来看 #

你给出的get_sum函数是典型的树状数组前缀求和实现：

int get_sum(int x) { 
    int p = 0, k; 
    for (k = x; k > 0; k -= k & -k) 
        p += bit[k]; 
    return p; 
}

这里的循环每次清除k最右边的1，其实是在遍历树状数组中需要累加的节点，最终p的值就是从1到x的前缀和（bit数组是树状数组的存储结构）。

比如当x=6时，循环会执行两次：

1. 第一次k=6，累加bit[6]，然后k变成4
2. 第二次k=4，累加bit[4]，然后k变成0，循环结束
   最终p = bit[6] + bit[4]，这正是树状数组中计算1-6前缀和的方式。

内容的提问来源于stack exchange，提问作者Aritra Dutta