整数nがあり、最上位ビットの位置を知りたい場合（つまり、最下位ビットが右側にある場合は、左端のビットの位置である1を知りたい）、見つけるための最も速く/最も効率的な方法は何ですか？
POSIXが最初のセットビットを見つけるためにstrings.hのメソッドをサポートしていることは知っていffs()ますが、対応するメソッドがないようですfls()。
私が見逃しているこれを行うための本当に明白な方法はありますか？
移植性のためにPOSIX関数を使用できない場合はどうでしょうか。
編集：32ビットアーキテクチャと64ビットアーキテクチャの両方で機能するソリューションについてはどうでしょうか（コードリストの多くは、32ビットintでのみ機能するようです）。
GCCには次のものがあります：
-- 組み込み関数: int __builtin_clz (unsigned int x)
最大で始まる、X の先頭の 0 ビットの数を返します。
有効ビット位置。X が 0 の場合、結果は未定義です。
-- 組み込み関数: int __builtin_clzl (unsigned long)
__builtin_clz に似ていますが、引数の型が unsigned である点が異なります
長いです'。
-- 組み込み関数: int __builtin_clzll (unsigned long long)
__builtin_clz に似ていますが、引数の型が unsigned である点が異なります
ロングロング」。
私は、それらが現在のプラットフォームにとって合理的に効率的なものに変換されることを期待しています.
入力がゼロになる可能性がある場合に役立つトリックは、他の入力を変更__builtin_clz(x | 1)せずに無条件に下位ビットを設定して、他の入力の出力を変更せずに の出力を31作成することです。x=0
__clzそれを行う必要を避けるために、他のオプションは、ARM GCC (ヘッダーは不要)、または命令_lzcnt_u32をサポートする CPU 上の x86などのプラットフォーム固有の組み込み関数です。lzcnt(ゼロ以外の入力に対して 31-lzcnt を与えるフォルトではなく、古い CPU のようにlzcntデコードすることに注意してください。)bsr
残念ながら、input=0 の結果を (オペランド幅に応じて) 32 または 64 として定義する非 x86 プラットフォームのさまざまな CLZ 命令を移植可能に利用する方法はありません。x86lzcntもそれを行いますが、bsr使用しない限りコンパイラが反転しなければならないビットインデックスを生成します31-__builtin_clz(x)。
（「未定義の結果」はCの未定義の動作ではなく、定義されていない値です。実際には、命令が実行されたときに宛先レジスタにあったものです。AMDはこれを文書化していますが、Intelは文書化していませんが、IntelのCPUはその動作を実装しています.しかし、代入先の C 変数に以前あったものとは異なります.通常、gcc が C を asm に変換するとき、それはどのように機能するかではありません. LZCNT の「出力依存性」を壊すことが重要なのはなぜですか?も参照してください) 。
2^N は N 番目のビットのみが設定された整数 (1 << N) であるため、設定された最上位ビットの位置 (N) を見つけることは、その整数の整数対数底 2 です。
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
unsigned int v;
unsigned r = 0;
while (v >>= 1) {
r++;
}
この「明白な」アルゴリズムは誰にとっても透過的ではないかもしれませんが、コードが左端のビットがシフトオフされるまで繰り返し 1 ビットずつ右にシフトし (C はゼロ以外の値を真として扱うことに注意してください)、数値を返すことに気付いた場合シフトの、それは完全に理にかなっています。また、複数のビットが設定されている場合でも機能することを意味します。結果は常に最上位ビットに対するものです。
そのページを下にスクロールすると、より高速で複雑なバリエーションがあります。ただし、先行ゼロが多数ある数値を扱っていることがわかっている場合は、単純なアプローチで許容できる速度が得られる可能性があります。これは、C ではビット シフトがかなり高速であり、単純なアルゴリズムでは配列にインデックスを付ける必要がないためです。
注: 64 ビット値を使用する場合は、非常に巧妙なアルゴリズムの使用に細心の注意を払ってください。それらの多くは、32 ビット値に対してのみ正しく機能します。
x86を使用していて、インラインアセンブラを少し使用していると仮定すると、IntelはBSR命令（「ビットスキャンリバース」）を提供します。一部のx86では高速です（他のx86ではマイクロコード化されています）。マニュアルから：
ソースオペランドで最上位のセットビット（1ビット）を検索します。最上位の1ビットが見つかった場合、そのビットインデックスはデスティネーションオペランドに格納されます。ソースオペランドは、レジスタまたはメモリ位置にすることができます。デスティネーションオペランドはレジスタです。ビットインデックスは、ソースオペランドのビット0からの符号なしオフセットです。コンテンツソースオペランドが0の場合、デスティネーションオペランドのコンテンツは未定義です。
（PowerPCを使用している場合は、同様のcntlz（「先行ゼロのカウント」）命令があります。）
gccのサンプルコード：
#include <iostream>
int main (int,char**)
{
int n=1;
for (;;++n) {
int msb;
asm("bsrl %1,%0" : "=r"(msb) : "r"(n));
std::cout << n << " : " << msb << std::endl;
}
return 0;
}
このインラインアセンブラチュートリアルも参照してください。このチュートリアルでは、コードをループするよりもかなり高速であることが示されています（セクション9.4）。
これは、一種の整数ログを見つけるようなものです。ビットをいじるトリックがありますが、私はこれのために独自のツールを作成しました。もちろん、目標はスピードです。
私の認識では、CPUにはすでに自動ビット検出器があり、整数から浮動小数点への変換に使用されています。だからそれを使ってください。
double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023; // assumes x86 endianness
このバージョンは、値をdoubleにキャストしてから、ビットがどこにあったかを示す指数を読み取ります。派手なシフトと減算は、IEEE値から適切な部分を抽出することです。
フロートを使用する方が少し高速ですが、フロートは精度が低いため、最初の24ビット位置しか提供できません。
これを安全に行うには、C ++またはCで未定義の動作を行わずに、memcpy型のパンニングにポインターキャストの代わりにを使用します。コンパイラは、それを効率的にインライン化する方法を知っています。
// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64");
// and also static_assert something about FLT_ENDIAN?
double ff=(double)(v|1);
uint32_t tmp;
memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t));
return (tmp>>20)-1023;
または、C99以降では、を使用しunion {double d; uint32_t u[2];};ます。ただし、C ++では、ユニオン型のパンニングは、ISO C ++ではなく、拡張機能として一部のコンパイラでのみサポートされていることに注意してください。
これは通常、先行ゼロカウント命令のプラットフォーム固有の組み込み関数よりも遅くなりますが、ポータブルISOCにはそのような機能はありません。一部のCPUには、先行ゼロのカウント命令もありませんが、整数をに効率的に変換できるCPUもありますdouble。ただし、FPビットパターンを整数に型のパンニングするのは遅い場合があります（たとえば、PowerPCでは、ストア/リロードが必要であり、通常、ロードヒットストアのストールが発生します）。
このアルゴリズムは、SIMDを備えたCPUが少ないため、SIMDの実装に役立つ可能性がありますlzcnt。x86はAVX512CDでのみそのような命令を受け取りました
これは非常に高速です。
int msb(unsigned int v) {
static const int pos[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};
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v = (v >> 1) + 1;
return pos[(v * 0x077CB531UL) >> 27];
}
カズ・キルヘクはこちら
この 63 ビットを超える数値 (gcc x86_64 の long long 型) に対する 2 つのアプローチをベンチマークし、符号ビットを避けました。
（たまたま、何かのためにこの「最上位ビットを見つける」必要があります。）
データ駆動型のバイナリ検索を実装しました（上記の回答の1つに厳密に基づいています）。また、完全にアンロールされた決定木を手動で実装しました。これは、即値オペランドを持つ単なるコードです。ループもテーブルもありません。
デシジョン ツリー (highest_bit_unrolled) は、バイナリ検索に明示的なテストがある n = 0 の場合を除いて、69% 高速であることがベンチマークされました。
0 ケースに対する二分探索の特別なテストは、特別なテストを持たない決定木よりも 48% だけ高速です。
コンパイラ、マシン: (GCC 4.5.2、-O3、x86-64、2867 Mhz Intel Core i5)。
int highest_bit_unrolled(long long n)
{
if (n & 0x7FFFFFFF00000000) {
if (n & 0x7FFF000000000000) {
if (n & 0x7F00000000000000) {
if (n & 0x7000000000000000) {
if (n & 0x4000000000000000)
return 63;
else
return (n & 0x2000000000000000) ? 62 : 61;
} else {
if (n & 0x0C00000000000000)
return (n & 0x0800000000000000) ? 60 : 59;
else
return (n & 0x0200000000000000) ? 58 : 57;
}
} else {
if (n & 0x00F0000000000000) {
if (n & 0x00C0000000000000)
return (n & 0x0080000000000000) ? 56 : 55;
else
return (n & 0x0020000000000000) ? 54 : 53;
} else {
if (n & 0x000C000000000000)
return (n & 0x0008000000000000) ? 52 : 51;
else
return (n & 0x0002000000000000) ? 50 : 49;
}
}
} else {
if (n & 0x0000FF0000000000) {
if (n & 0x0000F00000000000) {
if (n & 0x0000C00000000000)
return (n & 0x0000800000000000) ? 48 : 47;
else
return (n & 0x0000200000000000) ? 46 : 45;
} else {
if (n & 0x00000C0000000000)
return (n & 0x0000080000000000) ? 44 : 43;
else
return (n & 0x0000020000000000) ? 42 : 41;
}
} else {
if (n & 0x000000F000000000) {
if (n & 0x000000C000000000)
return (n & 0x0000008000000000) ? 40 : 39;
else
return (n & 0x0000002000000000) ? 38 : 37;
} else {
if (n & 0x0000000C00000000)
return (n & 0x0000000800000000) ? 36 : 35;
else
return (n & 0x0000000200000000) ? 34 : 33;
}
}
}
} else {
if (n & 0x00000000FFFF0000) {
if (n & 0x00000000FF000000) {
if (n & 0x00000000F0000000) {
if (n & 0x00000000C0000000)
return (n & 0x0000000080000000) ? 32 : 31;
else
return (n & 0x0000000020000000) ? 30 : 29;
} else {
if (n & 0x000000000C000000)
return (n & 0x0000000008000000) ? 28 : 27;
else
return (n & 0x0000000002000000) ? 26 : 25;
}
} else {
if (n & 0x0000000000F00000) {
if (n & 0x0000000000C00000)
return (n & 0x0000000000800000) ? 24 : 23;
else
return (n & 0x0000000000200000) ? 22 : 21;
} else {
if (n & 0x00000000000C0000)
return (n & 0x0000000000080000) ? 20 : 19;
else
return (n & 0x0000000000020000) ? 18 : 17;
}
}
} else {
if (n & 0x000000000000FF00) {
if (n & 0x000000000000F000) {
if (n & 0x000000000000C000)
return (n & 0x0000000000008000) ? 16 : 15;
else
return (n & 0x0000000000002000) ? 14 : 13;
} else {
if (n & 0x0000000000000C00)
return (n & 0x0000000000000800) ? 12 : 11;
else
return (n & 0x0000000000000200) ? 10 : 9;
}
} else {
if (n & 0x00000000000000F0) {
if (n & 0x00000000000000C0)
return (n & 0x0000000000000080) ? 8 : 7;
else
return (n & 0x0000000000000020) ? 6 : 5;
} else {
if (n & 0x000000000000000C)
return (n & 0x0000000000000008) ? 4 : 3;
else
return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
}
}
}
}
}
int highest_bit(long long n)
{
const long long mask[] = {
0x000000007FFFFFFF,
0x000000000000FFFF,
0x00000000000000FF,
0x000000000000000F,
0x0000000000000003,
0x0000000000000001
};
int hi = 64;
int lo = 0;
int i = 0;
if (n == 0)
return 0;
for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
int mi = lo + (hi - lo) / 2;
if ((n >> mi) != 0)
lo = mi;
else if ((n & (mask[i] << lo)) != 0)
hi = mi;
}
return lo + 1;
}
簡単で汚いテストプログラム:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int highest_bit_unrolled(long long n);
int highest_bit(long long n);
main(int argc, char **argv)
{
long long n = strtoull(argv[1], NULL, 0);
int b1, b2;
long i;
clock_t start = clock(), mid, end;
for (i = 0; i < 1000000000; i++)
b1 = highest_bit_unrolled(n);
mid = clock();
for (i = 0; i < 1000000000; i++)
b2 = highest_bit(n);
end = clock();
printf("highest bit of 0x%llx/%lld = %d, %d\n", n, n, b1, b2);
printf("time1 = %d\n", (int) (mid - start));
printf("time2 = %d\n", (int) (end - mid));
return 0;
}
-O2 のみを使用すると、その差はさらに大きくなります。デシジョン ツリーは、ほぼ 4 倍高速です。
また、単純なビット シフト コードに対してベンチマークを行いました。
int highest_bit_shift(long long n)
{
int i = 0;
for (; n; n >>= 1, i++)
; /* empty */
return i;
}
予想通り、これは少数の場合にのみ高速です。n == 1 の場合に最上位ビットが 1 であると判断する際に、80% 以上高速にベンチマークを実行しました。ただし、63 ビット空間でランダムに選択された数字の半分には、63 番目のビットが設定されています。
入力 0x3FFFFFFFFFFFFFF では、デシジョン ツリー バージョンは 1 よりもかなり高速であり、ビット シフタよりも 1120% (12.2 倍) 高速であることが示されています。
また、GCC ビルトインに対してデシジョン ツリーのベンチマークを行い、同じ数に対して繰り返すのではなく、入力の混合も試します。いくつかの固着分岐予測が行われている可能性があり、おそらくいくつかの非現実的なキャッシュシナリオがあり、繰り返しで人為的に高速になります。
おそらく最高のパフォーマンスが絶対に必要な場合にのみこの方法を使用しますが（たとえば、ビットボードを含むある種のボードゲームAIを作成する場合）、最も効率的な解決策はインラインASMを使用することです。説明付きのコードについては、このブログ投稿の最適化のセクションを参照してください。
[...]、
bsrlアセンブリ命令は最上位ビットの位置を計算します。asmしたがって、次のステートメントを使用できます。asm ("bsrl %1, %0" : "=r" (position) : "r" (number));
unsigned int
msb32(register unsigned int x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return(x & ~(x >> 1));
}
1レジスタ、13命令。信じられないかもしれませんが、これは通常、線形時間で動作する上記の BSR 命令よりも高速です。これは対数時間です。
どうですか
int highest_bit(unsigned int a) {
int count;
std::frexp(a, &count);
return count - 1;
}
?
このページで現在提供されているアルゴリズムのいくつかの（単純な）ベンチマークを次に示します...
アルゴリズムは、unsigned int のすべての入力に対してテストされていません。やみくもに何かを使用する前に、まずそれを確認してください;）
私のマシンでは clz (__builtin_clz) と asm が最適に動作します。asmはclzよりもさらに高速に見えます...しかし、それは単純なベンチマークが原因である可能性があります...
//////// go.c ///////////////////////////////
// compile with: gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/***************** math ********************/
#define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */ \
((unsigned) log2(a)) /* thus: do not use if a <= 0 */
#define NUM_OF_HIGHESTBITmath(a) ((a) \
? (1U << POS_OF_HIGHESTBITmath(a)) \
: 0)
/***************** clz ********************/
unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */
#define NUM_OF_HIGHESTBITclz(a) ((a) \
? (1U << POS_OF_HIGHESTBITclz(a)) \
: 0)
/***************** i2f ********************/
double FF;
#define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023)
#define NUM_OF_HIGHESTBITi2f(a) ((a) \
? (1U << POS_OF_HIGHESTBITi2f(a)) \
: 0)
/***************** asm ********************/
unsigned OUT;
#define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT)
#define NUM_OF_HIGHESTBITasm(a) ((a) \
? (1U << POS_OF_HIGHESTBITasm(a)) \
: 0)
/***************** bitshift1 ********************/
#define NUM_OF_HIGHESTBITbitshift1(a) (({ \
OUT = a; \
OUT |= (OUT >> 1); \
OUT |= (OUT >> 2); \
OUT |= (OUT >> 4); \
OUT |= (OUT >> 8); \
OUT |= (OUT >> 16); \
}), (OUT & ~(OUT >> 1))) \
/***************** bitshift2 ********************/
int POS[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};
#define POS_OF_HIGHESTBITbitshift2(a) (({ \
OUT = a; \
OUT |= OUT >> 1; \
OUT |= OUT >> 2; \
OUT |= OUT >> 4; \
OUT |= OUT >> 8; \
OUT |= OUT >> 16; \
OUT = (OUT >> 1) + 1; \
}), POS[(OUT * 0x077CB531UL) >> 27])
#define NUM_OF_HIGHESTBITbitshift2(a) ((a) \
? (1U << POS_OF_HIGHESTBITbitshift2(a)) \
: 0)
#define LOOPS 100000000U
int main()
{
time_t start, end;
unsigned ui;
unsigned n;
/********* Checking the first few unsigned values (you'll need to check all if you want to use an algorithm here) **************/
printf("math\n");
for (ui = 0U; ui < 18; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITmath(ui));
printf("\n\n");
printf("clz\n");
for (ui = 0U; ui < 18U; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITclz(ui));
printf("\n\n");
printf("i2f\n");
for (ui = 0U; ui < 18U; ++ui)
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITi2f(ui));
printf("\n\n");
printf("asm\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITasm(ui));
}
printf("\n\n");
printf("bitshift1\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift1(ui));
}
printf("\n\n");
printf("bitshift2\n");
for (ui = 0U; ui < 18U; ++ui) {
printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift2(ui));
}
printf("\n\nPlease wait...\n\n");
/************************* Simple clock() benchmark ******************/
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITmath(ui);
end = clock();
printf("math:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITclz(ui);
end = clock();
printf("clz:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITi2f(ui);
end = clock();
printf("i2f:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITasm(ui);
end = clock();
printf("asm:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITbitshift1(ui);
end = clock();
printf("bitshift1:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (ui = 0; ui < LOOPS; ++ui)
n = NUM_OF_HIGHESTBITbitshift2(ui);
end = clock();
printf("bitshift2\t%e\n", (double)(end-start)/CLOCKS_PER_SEC);
printf("\nThe lower, the better. Take note that a negative exponent is good! ;)\n");
return EXIT_SUCCESS;
}
これを行うためのルーチンが必要で、Web を検索する (そしてこのページを見つける) 前に、バイナリ検索に基づいた独自のソリューションを思いつきました。誰かが以前にこれをやったと確信していますが！それは一定の時間で実行され、投稿された「明白な」ソリューションよりも高速になる可能性がありますが、私は大きな主張をしているわけではなく、関心のために投稿しているだけです。
int highest_bit(unsigned int a) {
static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 };
const unsigned int *mask = maskv;
int l, h;
if (a == 0) return -1;
l = 0;
h = 32;
do {
int m = l + (h - l) / 2;
if ((a >> m) != 0) l = m;
else if ((a & (*mask << l)) != 0) h = m;
mask++;
} while (l < h - 1);
return l;
}
逐次近似を使用した C のバージョン:
unsigned int getMsb(unsigned int n)
{
unsigned int msb = sizeof(n) * 4;
unsigned int step = msb;
while (step > 1)
{
step /=2;
if (n>>msb)
msb += step;
else
msb -= step;
}
if (n>>msb)
msb++;
return (msb - 1);
}
利点: ループ回数は常に同じであるため、指定された回数に関係なく、実行時間は一定です。(「unsigned int」使用時は4ループ)
Joshのベンチマークを拡張すると...次のようにclzを改善できます
/***************** clz2 ********************/
#define NUM_OF_HIGHESTBITclz2(a) ((a) \
? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
: 0)
asm について: bsr と bsrl があることに注意してください (これは「長い」バージョンです)。通常のものは少し速いかもしれません。
上記の回答が指摘しているように、最上位ビットを決定する方法はいくつかあります。ただし、指摘されたように、メソッドは 32 ビットまたは 64 ビット レジスタに固有である可能性があります。stanford.eduのbithacks ページでは、32 ビットと 64 ビットの両方のコンピューティングで機能するソリューションを提供しています。少しの作業で、それらを組み合わせて、MSB を取得するための堅実なクロスアーキテクチャ アプローチを提供できます。私がたどり着いた解決策は、64 ビットと 32 ビットのコンピューターでコンパイル/動作することでした。
#if defined(__LP64__) || defined(_LP64)
# define BUILD_64 1
#endif
#include <stdio.h>
#include <stdint.h> /* for uint32_t */
/* CHAR_BIT (or include limits.h) */
#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif /* CHAR_BIT */
/*
* Find the log base 2 of an integer with the MSB N set in O(N)
* operations. (on 64bit & 32bit architectures)
*/
int
getmsb (uint32_t word)
{
int r = 0;
if (word < 1)
return 0;
#ifdef BUILD_64
union { uint32_t u[2]; double d; } t; // temp
t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
while (word >>= 1)
{
r++;
}
#endif /* BUILD_64 */
return r;
}
ビット演算子を考えてください。
私はその質問を初めて誤解した。左端のビットが設定されたint（他はゼロ）を生成する必要があります。cmpがその値に設定されていると仮定します。
position = sizeof(int)*8
while(!(n & cmp)){
n <<=1;
position--;
}
あなたがやろうとしているのは、整数の整数log2を計算することであることに注意してください。
#include <stdio.h>
#include <stdlib.h>
unsigned int
Log2(unsigned long x)
{
unsigned long n = x;
int bits = sizeof(x)*8;
int step = 1; int k=0;
for( step = 1; step < bits; ) {
n |= (n >> step);
step *= 2; ++k;
}
//printf("%ld %ld\n",x, (x - (n >> 1)) );
return(x - (n >> 1));
}
一度に複数のビットを検索できることに注意してください。
unsigned int
Log2_a(unsigned long x)
{
unsigned long n = x;
int bits = sizeof(x)*8;
int step = 1;
int step2 = 0;
//observe that you can move 8 bits at a time, and there is a pattern...
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//}
//}
//}
for( step2=0; x>1L<<step2+8; ) {
step2+=8;
}
//printf("step2 %d\n",step2);
for( step = 0; x>1L<<(step+step2); ) {
step+=1;
//printf("step %d\n",step+step2);
}
printf("log2(%ld) %d\n",x,step+step2);
return(step+step2);
}
このアプローチでは、二分探索を使用します
unsigned int
Log2_b(unsigned long x)
{
unsigned long n = x;
unsigned int bits = sizeof(x)*8;
unsigned int hbit = bits-1;
unsigned int lbit = 0;
unsigned long guess = bits/2;
int found = 0;
while ( hbit-lbit>1 ) {
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
//when value between guess..lbit
if( (x<=(1L<<guess)) ) {
//printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
hbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
}
//when value between hbit..guess
//else
if( (x>(1L<<guess)) ) {
//printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
lbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
}
}
if( (x>(1L<<guess)) ) ++guess;
printf("log2(x%ld)=r%d\n",x,guess);
return(guess);
}
おそらくもっと読みやすい別の二分探索法、
unsigned int
Log2_c(unsigned long x)
{
unsigned long v = x;
unsigned int bits = sizeof(x)*8;
unsigned int step = bits;
unsigned int res = 0;
for( step = bits/2; step>0; )
{
//printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
while ( v>>step ) {
v>>=step;
res+=step;
//printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
}
step /= 2;
}
if( (x>(1L<<res)) ) ++res;
printf("log2(x%ld)=r%ld\n",x,res);
return(res);
}
そして、これらをテストしたいので、
int main()
{
unsigned long int x = 3;
for( x=2; x<1000000000; x*=2 ) {
//printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
}
return(0);
}
「まだ別の」アプローチであるため、これを入れることは、すでに与えられている他のものとは異なるようです。
-1の場合x==0、そうでない場合floor( log2(x)) (最大結果 31)を返します。
32 ビット問題から 4 ビット問題に減らしてから、テーブルを使用します。おそらくエレガントではありませんが、実用的です。
__builtin_clzこれは、移植性の問題のために使用したくないときに使用するものです。
よりコンパクトにするために、代わりにループを使用して削減し、毎回 r に 4 を追加して、最大 7 回の反復を行うことができます。または、(64 ビットの場合) などのハイブリッド: 8 に減らすループ、4 に減らすテスト。
int log2floor( unsigned x ){
static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
int r = 0;
unsigned xk = x >> 16;
if( xk != 0 ){
r = 16;
x = xk;
}
// x is 0 .. 0xFFFF
xk = x >> 8;
if( xk != 0){
r += 8;
x = xk;
}
// x is 0 .. 0xFF
xk = x >> 4;
if( xk != 0){
r += 4;
x = xk;
}
// now x is 0..15; x=0 only if originally zero.
return r + wtab[x];
}
別の投稿者は、バイト幅のルックアップを使用してルックアップ テーブルを提供しました。もう少しパフォーマンスを上げたい場合 (256 個のルックアップ エントリではなく 32K のメモリを犠牲にして) 、C# 7 for .NETで15 ビットのルックアップ テーブルを使用するソリューションを次に示します。
興味深い部分は、テーブルの初期化です。これはプロセスの存続期間に必要な比較的小さなブロックであるため、 を使用してアンマネージ メモリを割り当てますMarshal.AllocHGlobal。ご覧のとおり、最大のパフォーマンスを得るために、例全体がネイティブとして記述されています。
readonly static byte[] msb_tab_15;
// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
var p = new byte[0x8000];
for (byte n = 0; n < 16; n++)
for (int c = (1 << n) >> 1, i = 0; i < c; i++)
p[c + i] = n;
msb_tab_15 = p;
}
テーブルは、上記のコードを介して一度だけ初期化する必要があります。これは読み取り専用であるため、同時アクセスのために単一のグローバル コピーを共有できます。この表を使用すると、さまざまな整数幅 (8、16、32、および 64 ビット) について、ここで探している整数log 2をすばやく検索できます。
0「最上位セット ビット」の概念が定義されていない唯一の整数であるのテーブル エントリには、値 が与えられていることに注意してください-1。この区別は、以下のコードで値が 0 の上位ワードを適切に処理するために必要です。これ以上苦労することなく、さまざまな整数プリミティブのそれぞれのコードを次に示します。
ulong (64 ビット) バージョン
/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 0x40) - 1; // handles cases v==0 and MSB==63
int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
return j + msb_tab_15[v >> (j + 1)];
}
uint (32 ビット) バージョン
/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
if ((int)v <= 0)
return (int)((v >> 26) & 0x20) - 1; // handles cases v==0 and MSB==31
int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
return j + msb_tab_15[v >> (j + 1)];
}
上記のさまざまなオーバーロード
public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];
これは完全で実用的なソリューションであり、.NET 4.7.2 での最高のパフォーマンスを表すさまざまな代替手段を、特殊なパフォーマンス テスト ハーネスと比較しました。これらのいくつかを以下に示します。テスト パラメータは、すべての 65 ビット位置の均一な密度、つまり0 ... 31/63プラス値0(結果は -1) でした。ターゲット インデックス位置より下のビットはランダムに埋められました。テストはx64のみ、リリース モードで、JIT 最適化が有効になっています。
これで正式な回答は終わりです。以下は、上記のコードのパフォーマンスと正確性を検証するために実行したテストに関連する代替テスト候補のソース コードへの簡単なメモとリンクです。
上記で提供され、Tab16A としてコード化されたバージョンは、多くの実行で一貫して勝者でした。これらのさまざまな候補は、アクティブな作業/スクラッチ形式で、ここ、ここ、およびここにあります。
1候補.HighestOne_Tab16A 622,496 2候補。HighestOne_Tab16C 628,234 3候補。HighestOne_Tab8A 649,146 4候補。HighestOne_Tab8B 656,847 5候補。HighestOne_Tab16B 657,147 6候補。HighestOne_Tab16D 659,650 7 _highest_one_bit_UNMANAGED.HighestOne_U 702,900 8 de_Bruijn.IndexOfMSB 709,672 9 _old_2.HighestOne_Old2 715,810 10 _test_A.HighestOne8 757,188 11 _old_1.HighestOne_Old1 757,925 12 _test_A.HighestOne5 (安全でない) 760,387 13 _test_B.HighestOne8 (安全でない) 763,904 14 _test_A.HighestOne3 (安全でない) 766,433 15 _test_A.HighestOne1 (安全でない) 767,321 16 _test_A.HighestOne4 (危険) 771,702 17 _test_B.HighestOne2 (危険) 772,136 18 _test_B.HighestOne1 (危険) 772,527 19 _test_B.HighestOne3 (危険) 774,140 20 _test_A.HighestOne7 (危険) 774,581 21 _test_B.HighestOne7 (危険) 775,463 22 _test_A.HighestOne2 (危険) 776,865 23 候補。HighestOne_NoTab 777,698 24 _test_B.HighestOne6 (危険) 779,481 25 _test_A.HighestOne6 (危険) 781,553 26 _test_B.HighestOne4 (危険) 785,504 27 _test_B.HighestOne5 (危険) 789,797 28 _test_A.HighestOne0 (安全でない) 809,566 29 _test_B.HighestOne0 (安全でない) 814,990 30 _highest_one_bit.HighestOne 824,345 30 _bitarray_ext.RtlFindMostSignificantBit 894,069 31 人の候補。HighestOne_Naive 898,865
注目に値するのは、 ntdll.dll!RtlFindMostSignificantBitP/Invoke 経由のパフォーマンスがひどいことです。
[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);
実際の関数全体を次に示します。
RtlFindMostSignificantBit:
bsr rdx, rcx
mov eax,0FFFFFFFFh
movzx ecx, dl
cmovne eax,ecx
ret
これらの 5 つの行に起因するパフォーマンスの低下は想像できないので、マネージド/ネイティブ移行のペナルティが原因であるに違いありません。また、テストで 128 バイト (および 256 バイト) (8 ビット) のルックアップ テーブルshortよりも 32KB (および 64KB) (16 ビット) の直接ルックアップ テーブルが実際に好まれたことにも驚きました。byte以下は 16 ビット ルックアップよりも競争力があると思いましたが、後者は一貫してこれを上回りました。
public static int HighestOne_Tab8A(ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 64) - 1;
int j;
j = /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
return j + msb_tab_8[v >> j];
}
最後に指摘しておきたいのは、私の deBruijn メソッドがうまくいかなかったことにかなりショックを受けたということです。これは、私が以前に広く使用していた方法です。
const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
N_bsr64 = 0x03F79D71B4CB0A89;
readonly public static sbyte[]
bsf64 =
{
63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5,
},
bsr64 =
{
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,
};
public static int IndexOfLSB(ulong v) =>
v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;
public static int IndexOfMSB(ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 64) - 1;
v |= v >> 1; v |= v >> 2; v |= v >> 4; // does anybody know a better
v |= v >> 8; v |= v >> 16; v |= v >> 32; // way than these 12 ops?
return bsr64[(v * N_bsr64) >> 58];
}
この SO question でdeBruijn メソッドがいかに優れていて優れているかについて多くの議論があり、私は同意する傾向がありました。私の推測では、deBruijn とダイレクト ルックアップ テーブル メソッド (最速であることがわかりました) はどちらもテーブル ルックアップを実行する必要があり、どちらも最小限の分岐しかありませんが、deBruijn だけが 64 ビットの乗算演算を行います。IndexOfMSB私はここで関数をテストしただけで、deBruijn はテストしませんでしたが、deBruijnIndexOfLSBは操作が非常に少ないため (上記を参照)、はるかにうまくいく可能性が高く、LSB には引き続き使用する可能性があります。
コード：
// x>=1;
unsigned func(unsigned x) {
double d = x ;
int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
printf( "The left-most non zero bit of %d is bit %d\n", x, p);
}
または、Y=1 に設定して、FPU 命令 FYL2X (Y*Log2 X) の整数部分を取得します。