(数字)&( - 数字)的含义

Question

是什么意思 (number) & (-number)？我搜索了它但却无法找到意义

我想i & (-i)在for循环中使用:

for (i = 0; i <= n; i += i & (-i))

Answer 1

假设2的补码(或i无符号),-i则等于~i+1.

i & (~i + 1)是一个提取最低设置位的技巧i.

这是有效的,因为+1实际上做的是设置最低的清除位,并清除低于该位的所有位.这样在两个设置的唯一位i,并~i+1从最低的一组位i(即最低清除位~i).比这低的位清晰~i+1,高于它的位在i和之间是不相等的~i.

除非循环体修改i,否则在循环中使用它似乎很奇怪,因为它i = i & (-i)是一个幂等操作:执行两次会再次给出相同的结果.

[编辑:在其他地方的评论中,你指出代码实际上是i += i & (-i).那么对于非零的i做法是清除最低的设置位组i,并将下一个清除位设置为高于该值,例如101100 - > 110000.因为i没有清除位高于最低设置位(包括i = 0),它设置i为0.所以,如果不是因为这样一个事实i开始于0,每次循环会增加i由至少两倍以前的循环,有时甚至更多,直到最后超过n和休息或去0,永远循环.

在没有注释的情况下编写这样的代码通常是不可原谅的,但是根据问题的领域,这可能是一个"明显的"循环值序列.

Answer 2

假设负值使用二进制补码。然后-number可以计算为(~number)+1，翻转位并加 1。

例如，如果number = 92. 那么这就是二进制的样子：

number               0000 0000 0000 0000 0000 0000 0101 1100
~number              1111 1111 1111 1111 1111 1111 1010 0011
(~number) + 1        1111 1111 1111 1111 1111 1111 1010 0100
-number              1111 1111 1111 1111 1111 1111 1010 0100
(number) & (-number) 0000 0000 0000 0000 0000 0000 0000 0100

您可以从上面的示例中看到，它只(number) & (-number)提供了最少的部分。

您可以在IDE One上看到在线运行的代码：http: //ideone.com/WzpxSD

这是一些 C 代码：

#include <iostream>
#include <bitset>
#include <stdio.h>
using namespace std;

void printIntBits(int num);
void printExpression(char *text, int value);

int main() {
  int number = 92;

  printExpression("number", number);
  printExpression("~number", ~number);
  printExpression("(~number) + 1", (~number) + 1);
  printExpression("-number", -number);
  printExpression("(number) & (-number)", (number) & (-number));

  return 0;
}

void printExpression(char *text, int value) {
  printf("%-20s", text);
  printIntBits(value);
  printf("\n");
}

void printIntBits(int num) {
    for(int i = 0; i < 8; i++) {
        int mask = (0xF0000000 >> (i * 4));
        int portion = (num & mask) >> ((7 - i) * 4);
      cout << " " << std::bitset<4>(portion);
    }
}

这里还有一个 C# .NET 版本：https://dotnetfiddle.net/ai7Eq6