有人能帮忙解释一下n&-n是什么意思吗？以及它的意义是什么。
8个回答
37
这是一种老技巧，它可以给出一个只有一个位的数字，即在n中设置的最后一位。至少在补码算术中，这种方法几乎是通用的。
其原理：一个数的负数是通过对该数进行反转，然后加1来产生的（这就是补码的定义）。当你加1时，从底部开始设置的每个位都会溢出到下一个更高的位；一旦到达零位，这个过程就停止了。这些溢出的位将全部为零，上面没有受影响的位将互为反码，因此留下的唯一位是停止级联的位——最初为1并被反转为0的那个位。
P.S. 如果你担心在线性补码中运行，这里有一个适用于两种方式的版本：
n & (~n + 1)
- Mark Ransom
3
1是的，如果例如想要快速迭代n中所有设置的位，那么这非常方便；
for (;j=n&(-n);n^=j) - Aki Suihkonen1可能说“bottom bit”是俗语，但为了更清晰地表达（至少在我自己的脑海中）：结果数字最多只有一位被设置，并且它是原始数字中设置的最低有效位。 - pooley1994
1@pooley1994 谢谢你。我一直在用“底部位”这个术语思考问题，但我无法告诉你我是从哪里学来的；我不能声称它是普遍理解的。 - Mark Ransom
9
在大多数人关心的系统上，它将为您提供n可被整除的最高2的幂。
- Benjamin Lindley
3
但要注意，它依赖于实现定义的行为，因此在技术上不可移植。 - tletnes
3可携性是一个相对的术语。从C++标准的角度来看，它并不具备可携性，这是事实。但它可能在比拥有符合或接近符合C++编译器的系统更多的系统中具有可携性。 - Benjamin Lindley
@tletnes 我最近在SO上被告知，C++20规定了二进制补码整数，因此行为将来会更加一致。 - Mark Ransom
5
N&(-N)会给你在N的二进制形式中第一个位'1'的位置。
例如：
N = 144 (0b10010000) => N&(-N) = 0b10000
N = 7 (0b00000111) => N&(-N) = 0b1
这个技巧的一个应用是将整数转换为2的幂次方之和。例如:
To convert 22 = 16 + 4 + 2 = 2^4 + 2^2 + 2^1
22&(-22) = 2, 22 - 2 = 20
20&(-20) = 4, 20 - 4 = 16
16&(-16) = 16, 16 - 16 = 0
- Thanh Cong Vu
3
我相信这是一种检测 n 是否为 2 的幂的技巧。当且仅当 n 是 2 的幂 (1, 2, 4, 8) 时，(n == (n & -n)) 成立。
- c.fogelklou
2
1那并不完全行得通，因为它会将零视为2的幂，而通常情况下零并不被认为是2的幂。这个技巧比这更有用 - 可以看看其他答案。 - JasonD
2
(n&(n-1))==0 更简单。 - Jyothrilinga K0
我会在Mark Randsom精彩的阐述中添加一个自我解释的例子。
010010000 | +144 ~
----------|-------
101101111 | -145 +
1 |
----------|-------
101110000 | -144
101110000 | -144 &
010010000 | +144
----------|-------
000010000 | 16`
- leodido
-1
因为对于 x 从0到32，x & -x = {0, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32}。它被用于一些应用程序中的for循环跳转。这些应用程序可以用来存储累积记录。
for(;x < N;x += x&-x) {
// do something here
++tr[x];
}
循环遍历非常快，因为它寻找下一个跳跃的二次幂。
- beahacker
-3
正如@aestrivex所提到的，这是一种写1的方式。我也遇到过这种情况。
for (int y = x; y > 0; y -= y & -y)
这只是意味着 y=y-1，因为
7&(-7) 是 x00000111 & x11111001 = x00000001 = 1
- Diffy
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
n的值和负数的表示方式（即1的补码与2的补码），它可能会导致未定义的行为或仅产生未指定和/或实现定义的值。我相信这是您不想使用/遇到的东西。 - user529758