の意味は何 (number) & (-number)ですか？検索しましたが意味がわかりませんでした
i & (-i)次のようなforループで使用したい：
for (i = 0; i <= n; i += i & (-i))
質問する
6948 次
4 に答える
30
i2の補数（または符号なし）を仮定すると、-iはに等しくなり~i+1ます。
i & (~i + 1)の最下位セットビットを抽出するためのトリックですi。
+1が実際に行うのは、最下位のクリアビットを設定し、それより低いすべてのビットをクリアすることであるため、これは機能します。したがって、両方iに設定され、~i+1からの最下位の設定ビットi（つまり、の最下位のクリアビット~i）である唯一のビットです。それより低いビットはで明確であり、それより高いビットはとの間で~i+1等しくありません。i~i
ループ本体が変更されない限り、ループでそれを使用することは奇妙に思えます。これは、べき等の操作iであるためi = i & (-i)です。これを2回実行すると、同じ結果が再び得られます。
[編集：他の場所のコメントで、コードが実際にはであると指摘していますi += i & (-i)。したがって、ゼロ以外の場合iは、のセットビットの最下位グループをクリアし、iその上の次のクリアビットを設定します（例：101100-> 110000 ）。i最下位のセットビット（を含むi = 0）よりも高いクリアビットがない場合は、 0に設定されます。したがって、で始まるiという事実がなければ、各ループは前のループの少なくとも2倍、場合によってはそれ以上増加し、最終的にはそれを超えて中断するか、永久にループします。i0in0
通常、コメントなしでこのようなコードを書くことは許されませんが、問題のドメインによっては、これはループする「明らかな」値のシーケンスである可能性があります。]
于 2012-10-10T12:10:39.867 に答える
4
これがどのように機能するかを示すために少し時間を取ってみようと思いました。このコードは、最小のセットビット値を提供します。
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が変更されない限り、このループは永久に続きます。
于 2012-10-10T12:51:34.770 に答える
4
負の値が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)、最小のビットが得られることがわかります。
コードがIDEOneでオンラインで実行されていることを確認できます：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
于 2016-03-16T20:16:16.030 に答える
1
この演算i & -iは、対応する整数の最下位の非ゼロビットを分離するために使用されます。
2進表記では、
numとして表すことができますa1b。ここでa、は最後のビットの前の2進数をb表し、最後のビットの後のゼロを表します。-numに等しい(a1b)¯ + 1 = a¯0b¯ + 1。bすべてゼロでb¯構成されているため、すべて1で構成されています。-num = (a1b)¯ + 1=>a¯0b¯ + 1=>a¯0(0…0)¯ + 1=>¯0(1…1) + 1=>a¯1(0…0)=>a¯1b
さて、
num & -num=>a1b & a¯1b=>(0..0)1(0..0)
たとえば、i=5の場合
| iteration | i | last bit position | i & -i|
|-------- |--------|-------- |-----|
| 1 | 5 = 101 | 0 | 1 (2^0)|
| 2 | 6 = 110 | 1 | 2 (2^1)|
| 3 | 8 = 1000 | 3 | 8 (2^3)|
| 4 | 16 = 10000 | 4 | 16 (2^4)|
| 5 | 32 = 100000 | 5 | 32 (2^5)|
この操作は、主にバイナリインデックスツリーでツリーを上下に移動するために使用されます
PS：何らかの理由で、stackoverflowはテーブルをコードとして扱っています:(
于 2021-05-07T19:20:08.860 に答える