整数に設定されている最下位ビットの位置を決定する効率的な方法を探しています。たとえば、0x0FF0 の場合は 4 になります。
簡単な実装は次のとおりです。
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
return pos;
}
そこからいくつかのサイクルを絞り出す方法はありますか?
(注: この質問は、そのようなことを楽しんでいる人のためのものであり、xyzoptimization は悪だと言う人のためのものではありません。)
[編集] アイデアをくれたみんなに感謝! 他にもいくつかのことを学びました。涼しい！
Bit Twiddling Hacksは、パフォーマンス/最適化の議論が添付された、ビットをいじるハックの優れたコレクションを提供します。（そのサイトからの）あなたの問題に対する私のお気に入りの解決策は«乗算と検索»です：
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
役立つ参考資料：
組み込みのffsを使用しないのはなぜですか? (Linux から man ページを取得しましたが、それよりも広く利用できます。)
ffs(3) - Linux のマニュアルページ
名前
ffs - 単語に設定された最初のビットを見つける
あらすじ
#include <strings.h> int ffs(int i); #define _GNU_SOURCE #include <string.h> int ffsl(long int i); int ffsll(long long int i);説明
ffs() 関数は、単語 i に設定された最初の (最下位) ビットの位置を返します。最下位ビットは位置 1 で、最上位ビットは 32 または 64 などです。関数 ffsll() および ffsl() は同じことを行いますが、おそらく異なるサイズの引数を取ります。
戻り値
これらの関数は、最初に設定されたビットの位置を返します。i にビットが設定されていない場合は 0 を返します。
準拠
4.3BSD、POSIX.1-2001。
ノート
BSD システムには、 にプロトタイプがあり
<string.h>ます。
それを行うx86アセンブリ命令（bsf）があります。:)
さらに最適化?!
このレベルでの最適化は、本質的にアーキテクチャに依存します。今日のプロセッサは(分岐予測、キャッシュ ミス、パイプライン処理に関して)複雑すぎるため、どのアーキテクチャでどのコードがより速く実行されるかを予測することは非常に困難です。オペレーションを 32 から 9 に減らすなど、一部のアーキテクチャではパフォーマンスが低下することさえあります。1 つのアーキテクチャで最適化されたコードは、他のアーキテクチャではより悪いコードになる可能性があります。これを特定のCPU用に最適化するか、そのままにして、コンパイラーがより良いと思うものを選択できるようにするかのどちらかだと思います。
最近のほとんどのアーキテクチャには、セットされた最下位ビットまたはセットされた最上位ビットの位置を見つけたり、先頭のゼロの数を数えたりするための命令があります。
このクラスの命令が 1 つでもあれば、他の命令を安価にエミュレートできます。
少し時間を取って紙の上で作業し、アーキテクチャやワード長などに関係なくx & (x-1)、x の最下位のセット ビットをクリアし、最下位のセット ビット( x & ~(x-1) )だけを返すことを理解してください。 -zeroes / maximum-set-bit を指定すると、明示的な指示がない場合に設定された最下位ビットが検索されます。
関連するハードウェア サポートがまったくない場合は、ここで指定されているカウント リーディング ゼロの乗算とルックアップの実装、またはBit Twiddling Hacksページにあるものの 1 つを簡単に変換して、上記の ID とブランチレスであるという利点があります。
以下は、いくつかのソリューションを比較するベンチマークです。
私のマシンは Intel i530 (2.9 GHz) で、Windows 7 64 ビットを実行しています。MinGW の 32 ビット バージョンでコンパイルしました。
$ gcc --version
gcc.exe (GCC) 4.7.2
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop. Time = 2.91 (Original questioner)
De Bruijn multiply. Time = 1.16 (Tykhyy)
Lookup table. Time = 0.36 (Andrew Grant)
FFS instruction. Time = 0.90 (ephemient)
Branch free mask. Time = 3.48 (Dan / Jim Balter)
Double hack. Time = 3.41 (DocMax)
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop. Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table. Time = 0.35
FFS instruction. Time = 0.68
Branch free mask. Time = 3.49
Double hack. Time = 0.92
私のコード:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 65536
#define NUM_ITERS 5000 // Number of times to process array
int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
if (value == 0)
continue;
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
total += pos + 1;
}
}
return total;
}
int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
static const int MultiplyDeBruijnBitPosition[32] =
{
1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
};
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int c = nums[i];
total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
}
}
return total;
}
unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
unsigned mask = 1;
for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
if (num & mask) {
return cnt;
}
}
return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int value = nums[i];
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
unsigned char *bytes = (unsigned char *)&value;
if (bytes[0])
total += lowestBitTable[bytes[0]];
else if (bytes[1])
total += lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
total += lowestBitTable[bytes[2]] + 16;
else
total += lowestBitTable[bytes[3]] + 24;
}
}
return total;
}
int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
total += __builtin_ffs(nums[i]);
}
}
return total;
}
int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
}
}
return total;
}
int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
double d = value ^ (value - !!value);
total += (((int*)&d)[1]>>20)-1022;
}
}
return total;
}
int main() {
unsigned nums[ARRAY_SIZE];
for (int i = 0; i < ARRAY_SIZE; i++) {
nums[i] = rand() + (rand() << 15);
}
for (int i = 0; i < 256; i++) {
lowestBitTable[i] = get_lowest_set_bit(i);
}
clock_t start_time, end_time;
int result;
start_time = clock();
result = find_first_bits_naive_loop(nums);
end_time = clock();
printf("Naive loop. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_de_bruijn(nums);
end_time = clock();
printf("De Bruijn multiply. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_lookup_table(nums);
end_time = clock();
printf("Lookup table. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_ffs_instruction(nums);
end_time = clock();
printf("FFS instruction. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_branch_free_mask(nums);
end_time = clock();
printf("Branch free mask. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_double_hack(nums);
end_time = clock();
printf("Double hack. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}
これに対する最速の (非組み込み/非アセンブラー) ソリューションは、最下位バイトを見つけて、256 エントリのルックアップ テーブルでそのバイトを使用することです。これにより、4 つの条件付き命令の最悪の場合のパフォーマンスと 1 つの最良の場合のパフォーマンスが得られます。これは命令の量が最小であるだけでなく、最新のハードウェアで非常に重要な分岐の量も最小です。
テーブル (256 個の 8 ビット エントリ) には、0 ～ 255 の範囲の各数値の LSB のインデックスが含まれている必要があります。値の各バイトをチェックし、ゼロ以外の最小バイトを見つけてから、この値を使用して実際のインデックスを検索します。
これには 256 バイトのメモリが必要ですが、この関数の速度が非常に重要な場合は、256 バイトに値する価値があります。
例えば
byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};
unsigned GetLowestBitPos(unsigned value)
{
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
byte* bytes = (byte*)value;
if (bytes[0])
return lowestBitTable[bytes[0]];
else if (bytes[1])
return lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
return lowestBitTable[bytes[2]] + 16;
else
return lowestBitTable[bytes[3]] + 24;
}
分岐があるときはいつでも、CPU はどの分岐が行われるかを推測する必要があります。命令パイプには、推測されたパスにつながる命令がロードされます。CPU が間違った推測をした場合、命令パイプがフラッシュされ、他のブランチをロードする必要があります。
一番上の単純な while ループを考えてみましょう。推測は、ループ内にとどまることです。ループを抜けるとき、少なくとも一度は間違っています。これにより、命令パイプがフラッシュされます。この動作は、ループを抜けると推測するよりもわずかに優れています。その場合、反復ごとに命令パイプがフラッシュされます。
失われる CPU サイクルの量は、プロセッサの種類によって大きく異なります。ただし、20 ～ 150 の CPU サイクルが失われることが予想されます。
次の悪いグループは、値を小さな断片に分割し、さらにいくつかの分岐を追加することで、いくつかの反復を節約しようと考えている場所です。これらの分岐ごとに、命令パイプをフラッシュする機会が追加され、さらに 20 ～ 150 クロック サイクルのコストがかかります。
テーブル内の値を検索するとどうなるかを考えてみましょう。少なくとも関数が初めて呼び出されたときは、値が現在キャッシュにない可能性があります。これは、値がキャッシュからロードされている間、CPU が停止することを意味します。繰り返しますが、これはマシンごとに異なります。新しい Intel チップは、現在のスレッドがキャッシュのロードが完了するのを待っている間に、これをスレッドを交換する機会として実際に使用します。これは、命令パイプのフラッシュよりも簡単にコストがかかる可能性がありますが、この操作を何度も実行している場合は、1 回しか発生しない可能性があります。
明らかに最速の定数時間ソリューションは、決定論的数学を含むものです。純粋でエレガントなソリューション。
これがすでにカバーされている場合は、お詫び申し上げます。
XCODE AFAIKを除いて、私が使用するすべてのコンパイラには、フォワードビットスキャンとリバースビットスキャンの両方のコンパイラ組み込み関数があります。これらは、ほとんどのハードウェアで単一のアセンブリ命令にコンパイルされ、キャッシュ ミス、分岐ミス予測、および他のプログラマ生成のつまずきブロックはありません。
Microsoft コンパイラの場合、_BitScanForward と _BitScanReverse を使用します。
GCC では、__builtin_ffs、__builtin_clz、__builtin_ctz を使用します。
さらに、議論されている主題について十分な知識がない場合は、回答を投稿したり、新規参入者を誤解させる可能性があることを控えてください.
申し訳ありませんが、解決策を提供するのを完全に忘れていました..これは、タスクのアセンブリレベルの指示がないIPADで使用するコードです。
unsigned BitScanLow_BranchFree(unsigned value)
{
bool bwl = (value & 0x0000ffff) == 0;
unsigned I1 = (bwl * 15);
value = (value >> I1) & 0x0000ffff;
bool bbl = (value & 0x00ff00ff) == 0;
unsigned I2 = (bbl * 7);
value = (value >> I2) & 0x00ff00ff;
bool bnl = (value & 0x0f0f0f0f) == 0;
unsigned I3 = (bnl * 3);
value = (value >> I3) & 0x0f0f0f0f;
bool bsl = (value & 0x33333333) == 0;
unsigned I4 = (bsl * 1);
value = (value >> I4) & 0x33333333;
unsigned result = value + I1 + I2 + I3 + I4 - 1;
return result;
}
ここで理解しておくべきことは、コストがかかるのは比較ではなく、比較後に発生する分岐であるということです。この場合の比較は、.. == 0 を使用して 0 または 1 の値に強制され、その結果を使用して、分岐のどちらかの側で発生した計算を結合します。
編集：
上記のコードは完全に壊れています。このコードは機能し、まだブランチフリーです (最適化されている場合):
int BitScanLow_BranchFree(ui value)
{
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
return i16 + i8 + i4 + i2 + i1 + i0;
}
これは、0 を指定すると -1 を返します。0 を気にしない場合、または 0 に対して 31 を取得することに満足している場合は、i0 の計算を削除して、時間を大幅に節約します。
セットビットの検索を含むこの同様の投稿に触発されて、私は以下を提供します:
unsigned GetLowestBitPos(unsigned value)
{
double d = value ^ (value - !!value);
return (((int*)&d)[1]>>20)-1023;
}
長所：
短所：
更新： コメントで指摘されているように、ユニオンは（少なくともCの場合）よりクリーンな実装であり、次のようになります。
unsigned GetLowestBitPos(unsigned value)
{
union {
int i[2];
double d;
} temp = { .d = value ^ (value - !!value) };
return (temp.i[1] >> 20) - 1023;
}
これは、すべてのリトルエンディアン ストレージを備えた 32 ビット int を想定しています (x86 プロセッサを考えてください)。
これは、32 回未満の操作という最悪のケースで実行できます。
原則: 2 ビット以上のチェックは、1 ビットのチェックと同じくらい効率的です。
したがって、たとえば、最初にどのグループが含まれているかをチェックし、次にそのグループの最小から最大まで各ビットをチェックすることを妨げるものは何もありません。
したがって...
一度に 2 ビットをチェックすると、最悪の場合 (Nbits/2) + 1 チェック合計になります。
一度に 3 ビットをチェックすると、最悪の場合 (Nbits/3) + 合計 2 チェックになります。
...
4 人一組でチェックインするのが最適です。最悪の場合、32 回ではなく 11 回の操作が必要になります。
このグループ化のアイデアを使用する場合、最良のケースは、アルゴリズムの 1 回のチェックから 2 回のチェックになります。しかし、最悪の場合の節約のためには、最良の場合の追加の 1 つのチェックは価値があります。
注: ループを使用する代わりに、完全に書き出す方が効率的であるためです。
int getLowestBitPos(unsigned int value)
{
//Group 1: Bits 0-3
if(value&0xf)
{
if(value&0x1)
return 0;
else if(value&0x2)
return 1;
else if(value&0x4)
return 2;
else
return 3;
}
//Group 2: Bits 4-7
if(value&0xf0)
{
if(value&0x10)
return 4;
else if(value&0x20)
return 5;
else if(value&0x40)
return 6;
else
return 7;
}
//Group 3: Bits 8-11
if(value&0xf00)
{
if(value&0x100)
return 8;
else if(value&0x200)
return 9;
else if(value&0x400)
return 10;
else
return 11;
}
//Group 4: Bits 12-15
if(value&0xf000)
{
if(value&0x1000)
return 12;
else if(value&0x2000)
return 13;
else if(value&0x4000)
return 14;
else
return 15;
}
//Group 5: Bits 16-19
if(value&0xf0000)
{
if(value&0x10000)
return 16;
else if(value&0x20000)
return 17;
else if(value&0x40000)
return 18;
else
return 19;
}
//Group 6: Bits 20-23
if(value&0xf00000)
{
if(value&0x100000)
return 20;
else if(value&0x200000)
return 21;
else if(value&0x400000)
return 22;
else
return 23;
}
//Group 7: Bits 24-27
if(value&0xf000000)
{
if(value&0x1000000)
return 24;
else if(value&0x2000000)
return 25;
else if(value&0x4000000)
return 26;
else
return 27;
}
//Group 8: Bits 28-31
if(value&0xf0000000)
{
if(value&0x10000000)
return 28;
else if(value&0x20000000)
return 29;
else if(value&0x40000000)
return 30;
else
return 31;
}
return -1;
}
二分探索を使ってみませんか？これは、5回の操作後に常に完了します（intサイズが4バイトであると想定）。
if (0x0000FFFF & value) {
if (0x000000FF & value) {
if (0x0000000F & value) {
if (0x00000003 & value) {
if (0x00000001 & value) {
return 1;
} else {
return 2;
}
} else {
if (0x0000004 & value) {
return 3;
} else {
return 4;
}
}
} else { ...
} else { ...
} else { ...
@ anton-tykhyy によって提供された同じリンクから、ここで別の方法 (モジュラス除算とルックアップ) を特筆する価値があります。このメソッドは、DeBruijn の乗算およびルックアップ メソッドとパフォーマンスが非常に似ていますが、わずかではあるが重要な違いがあります。
モジュラス除算とルックアップ
unsigned int v; // find the number of trailing zeros in v
int r; // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37];
モジュラス除算およびルックアップ メソッドは v=0x00000000 および v=FFFFFFFF に対して異なる値を返しますが、DeBruijn 乗算およびルックアップ メソッドは両方の入力でゼロを返します。
テスト：-
unsigned int n1=0x00000000, n2=0xFFFFFFFF;
MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */
unsigned GetLowestBitPos(unsigned value)
{
if (value & 1) return 1;
if (value & 2) return 2;
if (value & 4) return 3;
if (value & 8) return 4;
if (value & 16) return 5;
if (value & 32) return 6;
if (value & 64) return 7;
if (value & 128) return 8;
if (value & 256) return 9;
if (value & 512) return 10;
if (value & 1024) return 11;
if (value & 2048) return 12;
if (value & 4096) return 13;
if (value & 8192) return 14;
if (value & 16384) return 15;
if (value & 32768) return 16;
if (value & 65536) return 17;
if (value & 131072) return 18;
if (value & 262144) return 19;
if (value & 524288) return 20;
if (value & 1048576) return 21;
if (value & 2097152) return 22;
if (value & 4194304) return 23;
if (value & 8388608) return 24;
if (value & 16777216) return 25;
if (value & 33554432) return 26;
if (value & 67108864) return 27;
if (value & 134217728) return 28;
if (value & 268435456) return 29;
if (value & 536870912) return 30;
return 31;
}
コードの最初の行で、すべての数値の 50% が返されます。
コードの最初の 2 行で、すべての数値の 75% が返されます。
すべての数値の 87% がコードの最初の 3 行で返されます。
コードの最初の 4 行で、すべての数値の 94% が返されます。
コードの最初の 5 行で、すべての数値の 97% が返されます。
等
このコードの最悪のシナリオがどれほど非効率的であるかについて不平を言っている人は、そのような状況が発生することがどれほどまれかを理解していないと思います。
Chess Programming BitScan ページと私自身の測定によると、減算と xor は、否定とマスクよりも高速です。
（ の末尾のゼロを数えようとしている場合0、私が持っているメソッドは戻ります63が、ネゲートとマスクは を返します0。）
64 ビットの減算と xor は次のとおりです。
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];
参考までに、negate および mask メソッドの 64 ビット バージョンを次に示します。
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];
おそらく最速ではありませんが、かなり良いようです。
少なくとも枝はない。;)
uint32 x = ...; // 0x00000001 0x0405a0c0 0x00602000
x |= x << 1; // 0x00000003 0x0c0fe1c0 0x00e06000
x |= x << 2; // 0x0000000f 0x3c3fe7c0 0x03e1e000
x |= x << 4; // 0x000000ff 0xffffffc0 0x3fffe000
x |= x << 8; // 0x0000ffff 0xffffffc0 0xffffe000
x |= x << 16; // 0xffffffff 0xffffffc0 0xffffe000
// now x is filled with '1' from the least significant '1' to bit 31
x = ~x; // 0x00000000 0x0000003f 0x00001fff
// now we have 1's below the original least significant 1
// let's count them
x = x & 0x55555555 + (x >> 1) & 0x55555555;
// 0x00000000 0x0000002a 0x00001aaa
x = x & 0x33333333 + (x >> 2) & 0x33333333;
// 0x00000000 0x00000024 0x00001444
x = x & 0x0f0f0f0f + (x >> 4) & 0x0f0f0f0f;
// 0x00000000 0x00000006 0x00000508
x = x & 0x00ff00ff + (x >> 8) & 0x00ff00ff;
// 0x00000000 0x00000006 0x0000000d
x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
// 0x00000000 0x00000006 0x0000000d
// least sign.bit pos. was: 0 6 13
下位ビットが設定されているかどうかを確認できます。もしそうなら、残りのビットの下位を見てください。例えば、：
32bit int - 最初の 16 のいずれかが設定されているかどうかを確認します。その場合、最初の 8 つのいずれかが設定されているかどうかを確認します。もしそうなら、 ....
そうでない場合は、上位 16 個のいずれかが設定されているかどうかを確認してください。
基本的には二分探索です。
C++11 が利用できる場合は、コンパイラがそのタスクを実行してくれることがあります:)
constexpr std::uint64_t lssb(const std::uint64_t value)
{
return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}
結果は 1 ベースのインデックスです。
単一の x86 命令でそれを行う方法については、ここで私の回答を参照してBSFくださいBSR。
最近、シンガポールの首相が彼が書いたプログラムを Facebook に投稿したのを見ました。
論理は単純に「値 & -値」です。0x0FF0 があるとします。次に、0FF0 & (F00F+1) は 0x0010 に等しく、最小の 1 が 4 番目のビットにあることを意味します。:)
リソースがある場合は、速度を向上させるためにメモリを犠牲にすることができます。
static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
return bitPositions[value];
}
注：このテーブルは少なくとも4 GBを消費します（リターンタイプをそのままにしておくと16 GB unsigned）。これは、ある限られたリソース（RAM）を別のリソース（実行速度）と交換する例です。
関数の移植性を維持し、どんな犠牲を払っても可能な限り高速に実行する必要がある場合は、これが最適な方法です。ほとんどの実際のアプリケーションでは、4GBのテーブルは非現実的です。