c 中 k-=(k & (-k)) 的含义是什么？

Question

一个用于计算我遇到此语句的总和的函数 ..plz 帮助

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

Answer 1

这个表达：

k -= (k & (-k))

这是一种采用设置为正数的最低有效位并清除该位的棘手方法。它取决于负数的二进制补码表示。

第一部分，k & (-k)隔离设置的最低有效位。例如：

1 & -1：

   00000001
 & 11111111
   --------
   00000001

2 & -2：

   00000010
 & 11111110
   --------
   00000010

24 & -24：

   00011000
 & 11101000
   --------
   00001000

当从原始值中减去该值时k，它会清除该位作为结果。

因此，随着循环的进行k，从最低的开始，每次减少 1 位的值。因此，如果例如x是 52，则k是 52，然后是 48 (52 - 4)，然后是 32 (48 - 16)，并且会在 0 (32 - 32) 处退出。

至于程序为什么要这样做，这完全取决于它的定义bit和存储的内容。