(number) & (-number)的含义
(number) & (-number)是什么意思？
我想在for循环中使用i & (-i)，如下所示：
for (i = 0; i <= n; i += i & (-i))回答 4
Stack Overflow用户
发布于 2012-10-10 20:10:40
假设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的最低组设置位，并设置高于该组位的下一个清除位，例如101100 -> 110000。对于没有高于最低设置位(包括i = 0)的清除位的i，它将i设置为0。因此，如果不是因为i从0开始，每个循环都会使i增加至少是前一个循环的两倍，有时甚至更多，直到最终超过n，中断或进入0并永远循环。
编写这样的没有注释的代码通常是不可原谅的，但根据问题的领域，这可能是要循环的值的“明显”序列。]
Stack Overflow用户
发布于 2012-10-10 20:51:35
我想我只需要花一点时间来说明它是如何工作的。这段代码给出了最低的设置位的值：
int i = 0xFFFFFFFF; //Last byte is 1111(base 2), -1(base 10)
int j = -i; //-(-1) == 1
int k = i&j; // 1111(2) = -1(10)
// & 0001(2) = 1(10)
// ------------------
// 0001(2) = 1(10). So the lowest set bit here is the 1's bit
int i = 0x80; //Last 2 bytes are 1000 0000(base 2), 128(base 10)
int j = -i; //-(128) == -128
int k = i&j; // ...0000 0000 1000 0000(2) = 128(10)
// & ...1111 1111 1000 0000(2) = -128(10)
// ---------------------------
// 1000 0000(2) = 128(10). So the lowest set bit here is the 128's bit
int i = 0xFFFFFFC0; //Last 2 bytes are 1100 0000(base 2), -64(base 10)
int j = -i; //-(-64) == 64
int k = i&j; // 1100 0000(2) = -64(10)
// & 0100 0000(2) = 64(10)
// ------------------
// 0100 0000(2) = 64(10). So the lowest set bit here is the 64's bit它对于无符号值也是一样的，结果总是最低的设置位的值。
给定您的循环：
for(i=0;i<=n;i=i&(-i)) 没有设置位数(i=0)，因此此操作的增量步骤将返回0。因此，除非修改n=0或i，否则此循环将永远持续下去。
Stack Overflow用户
发布于 2016-03-17 04:16:16
假设负值使用的是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
https://stackoverflow.com/questions/12818978
复制相似问题
腾讯云开发者
