查找位数组中最重要的位（最左边）
我有一个位数组实现，其中第0个索引是数组中第一个字节的MSB，第8个索引是第二个字节的MSB等等。
什么是快速find在这个位arrays中设置的第一位的方法？ 我查过的所有相关解决schemefind了第一个最不重要的位，但我需要第一个最重要的位。 所以，给定0x00A1，我想要8（因为它是从左边的第九位）。
GCC有__builtin_clz转换为x86 / x64上的BSR，ARM上的CLZ等等，并在硬件没有实现的情况下模拟指令。
Visual C + + 2005年和_BitScanReverse 。
作为一个performance瘾君子，我尝试了一大堆MSB套装的变化，以下是我遇到的最快的，
unsigned int msb32(unsigned int x) { static const unsigned int bval[] = {0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4}; unsigned int r = 0; if (x & 0xFFFF0000) { r += 16/1; x >>= 16/1; } if (x & 0x0000FF00) { r += 16/2; x >>= 16/2; } if (x & 0x000000F0) { r += 16/4; x >>= 16/4; } return r + bval[x]; }
有多种方法可以做到这一点，不同的实现的相对性能是有些机器相关的（我碰巧在某种程度上为了类似的目的而对其进行了基准testing）。 在一些机器上，甚至还有一个内置的指令（如果可用的话，使用一个，可移植性可以处理）。
看看这里的一些实现（在“整数日志基2”）。 如果您使用的是GCC，请查看函数__builtin_clz和__builtin_clzl （分别为非零无符号整数和无符号长整数）。 “clz”代表“计数前导零”，这是另一种描述同样问题的方法。
当然，如果你的位数组不适合一个合适的机器字，你需要迭代数组中的字来find第一个非零字，然后只对这个字执行这个计算。
TL：博士; _BitScanReverse或__builtin_clz是最快的非便携式MSBalgorithm，而de Bruijn乘法是最快的便携式algorithm。
这是一个便携式的32位MSBalgorithm，比其他所有便携式32位MSBalgorithm在这个线程中快得多：
u32 msbDeBruijn32( u32 v ) { static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return MultiplyDeBruijnBitPosition[( u32 )( v * 0x07C4ACDDU ) >> 27]; }
在这个线程中的所有其他答案要么比他们的作者提出的要差得多，要么不正确地计算结果，要么两者兼而有之。 让我们来衡量一切，让我们来validation他们做他们自称的事情。
这里有一个简单的C ++ 11工具来testing所有这些实现。 它编译干净的Visual Studio，但应该在所有现代编译器上工作。 它允许您在性能模式（bVerifyResults = false）和检查模式（bVerifyResults = true）下运行基准testing。
以下是validation模式下的结果：
Verification failed for msbNative64: input was 0; output was 818af060; expected 0 Verification failed for msbFfs: input was 22df; output was 0; expected d Verification failed for msbPerformanceJunkie32: input was 0; output was ffffffff; expected 0 Verification failed for msbNative32: input was 0; output was 9ab07060; expected 0
input为零时，“性能迷惑”和Microsoft本机实现做不同的事情。 msbPerformanceJunkie32产生-1和Microsoft产生一个随机数。 此外，msbPerformanceJunkie32实现产生的结果是所有其他答案中的一个。
以下是运行在我的i7-4600笔记本电脑上的性能模式的结果：
msbLoop64 took 4.59326 seconds msbNative64 took 0.296473 seconds msbLoop32 took 3.55306 seconds msbFfs took 0.562097 seconds msbPerformanceJunkie32 took 1.10708 seconds msbDeBruijn32 took 0.263309 seconds msbNative32 took 0.259938 seconds
de Bruijn版本因其无分支而完美击败了其他实现，因此它可以很好地对付产生均匀分布输出集合的input。 所有其他版本对于任意input都比较慢，因为现代CPU的分支预测失误会受到惩罚。 smbFfs函数产生不正确的结果，所以可以忽略。
一些实现在32位input上工作，一些在64位input上工作。 无论input大小如何，模板都可以帮助我们比较苹果和苹果。
这是代码。 如果你喜欢，自己下载并运行基准testing。
#include <iostream> #include <chrono> #include <random> #include <cassert> #include <string> #include <limits> #ifdef _MSC_VER #define MICROSOFT_COMPILER 1 #include <intrin.h> #endif // _MSC_VER const int iterations = 100000000; bool bVerifyResults = false; std::random_device rd; std::default_random_engine re( rd() ); typedef unsigned int u32; typedef unsigned long long u64; class Timer { public: Timer() : beg_( clock_::now() ) {} void reset() { beg_ = clock_::now(); } double elapsed() const { return std::chrono::duration_cast<second_> ( clock_::now() - beg_ ).count(); } private: typedef std::chrono::high_resolution_clock clock_; typedef std::chrono::duration<double, std::ratio<1> > second_; std::chrono::time_point<clock_> beg_; }; unsigned int msbPerformanceJunkie32( u32 x ) { static const unsigned int bval[] = { 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4 }; unsigned int r = 0; if ( x & 0xFFFF0000 ) { r += 16 / 1; x >>= 16 / 1; } if ( x & 0x0000FF00 ) { r += 16 / 2; x >>= 16 / 2; } if ( x & 0x000000F0 ) { r += 16 / 4; x >>= 16 / 4; } return r + bval[x]; } #define FFS(t) \ { \ register int n = 0; \ if (!(0xffff & t)) \ n += 16; \ if (!((0xff << n) & t)) \ n += 8; \ if (!((0xf << n) & t)) \ n += 4; \ if (!((0x3 << n) & t)) \ n += 2; \ if (!((0x1 << n) & t)) \ n += 1; \ return n; \ } unsigned int msbFfs32( u32 x ) { FFS( x ); } unsigned int msbLoop32( u32 x ) { int r = 0; if ( x < 1 ) return 0; while ( x >>= 1 ) r++; return r; } unsigned int msbLoop64(u64 x) { int r = 0; if (x < 1) return 0; while (x >>= 1) r++; return r; } u32 msbDeBruijn32( u32 v ) { static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v |= v >> 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return MultiplyDeBruijnBitPosition[( u32 )( v * 0x07C4ACDDU ) >> 27]; } #ifdef MICROSOFT_COMPILER u32 msbNative32( u32 val ) { unsigned long result; _BitScanReverse( &result, val ); return result; } u32 msbNative64( u64 val ) { unsigned long result; _BitScanReverse64(&result, val); return result; } #endif // MICROSOFT_COMPILER template <typename InputType> void test( unsigned int msbFunc( InputType ), const std::string &name, const std::vector< InputType > &inputs, std::vector< unsigned int > &results, bool bIsReference = false ) { Timer t; if (bIsReference) { int i = 0; for (int i = 0; i < iterations; i++) results[ i ] = msbFunc( inputs[i] ); } unsigned int result; bool bNotified = false; for (int i = 0; i < iterations; i++) { result = msbFunc(inputs[i]); if (bVerifyResults && ( result != results[i]) && !bNotified) { std::cout << "Verification failed for " << name << ": " << "input was " << std::hex << inputs[i] << "; output was " << result << "; expected " << results[i] << std::endl; bNotified = true; } } double elapsed = t.elapsed(); std::cout << name << " took " << elapsed << " seconds" << std::endl; } void main() { std::uniform_int_distribution <u64> dist64(0, std::numeric_limits< u64 >::max()); std::uniform_int_distribution <u32> shift64(0, 63); std::vector< u64 > inputs64; for (int i = 0; i < iterations; i++) { inputs64.push_back(dist64(re) >> shift64(re)); } std::vector< u32 > results64; results64.resize(iterations); test< u64 >( msbLoop64, "msbLoop64", inputs64, results64, true); #ifdef MICROSOFT_COMPILER test< u64 >( msbNative64, "msbNative64", inputs64, results64, false ); #endif // MICROSOFT_COMPILER std::cout << std::endl; std::uniform_int_distribution <u32> dist32(0, std::numeric_limits< u32 >::max()); std::uniform_int_distribution <u32> shift32(0, 31); std::vector< u32 > inputs32; for (int i = 0; i < iterations; i++) inputs32.push_back(dist32(re) >> shift32(re)); std::vector< u32 > results32; results32.resize(iterations); test< u32 >( msbLoop32, "msbLoop32", inputs32, results32, true); test< u32 >( msbFfs32, "msbFfs", inputs32, results32, false); test< u32 >( msbPerformanceJunkie32, "msbPerformanceJunkie32", inputs32, results32, false); test< u32 >( msbDeBruijn32, "msbDeBruijn32", inputs32, results32, false); #ifdef MICROSOFT_COMPILER test< u32 >( msbNative32, "msbNative32", inputs32, results32, false); #endif // MICROSOFT_COMPILER }
查找BSR（位反向扫描）x86 asm指令是最快的方法。 从英特尔的文档： Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand). Searches the source operand (second operand) for the most significant set bit (1 bit). If a most significant 1 bit is found, its bit index is stored in the destination operand (first operand).
我知道在纯C中做两个最好的方法：
首先线性search字节/字数组，find非零的第一个字节/字，然后对find的字节/字进行展开的二进制search。
if (b>=0x10) if (b>=0x40) if (b>=0x80) return 0; else return 1; else if (b>=0x20) return 2; else return 3; else if (b>=0x4) if (b>=0x8) return 4; else return 5; else if (b>=0x2) return 6; else return 7;
3（顺便说一句，这是log2（8））条件跳转来得到答案。 在现代x86机器上，最后一个将被优化为条件mov。
或者，使用查找表将字节映射到设置的第一位的索引。
您可能要查找的相关主题是整数log2函数。 如果我记得，ffmpeg有一个很好的实现。
编辑：您可以实际上使上述二进制search到一个无分支的二进制search，但我不知道在这种情况下是否会更有效率…
这是一个解释__builtin_clz（）的代码片段
////// go.c //////// #include <stdio.h> 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) int main() { unsigned ui; for (ui = 0U; ui < 18U; ++ui) printf("%i \t %i\n", ui, NUM_OF_HIGHESTBITclz(ui)); return 0; }
如果你使用的是x86，你可以使用SSE2操作几乎任何逐字节或逐字的解决scheme，再加上find-first-bit指令，这些指令在gcc世界中发音为“ffs “为最低位，”fls“为最高位。 请原谅我有麻烦（！@＃$％^）在答案中格式化“C”代码; 检查： http : //mischasan.wordpress.com/2011/11/03/sse2-bit-trick-ffsfls-for-xmm-registers/
不是最快的，但它的作品…
//// C program #include <math.h> #define POS_OF_HIGHESTBIT(a) /* 0th position is the Least-Signif-Bit */ \ ((unsigned) log2(a)) /* thus: do not use if a <= 0 */ #define NUM_OF_HIGHESTBIT(a) ((!(a)) \ ? 0 /* no msb set*/ \ : (1 << POS_OF_HIGHESTBIT(a) )) // could be changed and optimized, if it is known that the following NEVER holds: a <= 0 int main() { unsigned a = 5; // 0b101 unsigned b = NUM_OF_HIGHESTBIT(a); // 4 since 4 = 0b100 return 0; }
我已经使用了许多函数来获取最重要的位，但是通常会出现32位和64位数之间移动或在x86_64和x86之间移动的问题。 函数__builtin_clz ， __builtin_clzl和__builtin_clzll适用于32/64位编号和x86_64和x86机器。 但是，需要三个function。 我find了一个简单的MSB，它依靠右移来处理所有正数的情况。 至less为了我的使用，在别人失败的地方已经成功了：
int getmsb (unsigned long long x) { int r = 0; if (x < 1) return 0; while (x >>= 1) r++; return r; }
通过将input指定为unsigned long long它可以将所有数字类从unsigned char为unsigned long long并给定标准定义，它在x86_64和x86版本之间兼容。 0情况定义为返回0 ，但可以根据需要进行更改。 一个简单的testing和输出是：
int main (int argc, char *argv[]) { unsigned char c0 = 0; unsigned char c = 216; unsigned short s = 1021; unsigned int ui = 32768; unsigned long ul = 3297381253; unsigned long long ull = 323543844043; int i = 32767; printf (" %16u MSB : %d\n", c0, getmsb (c0)); printf (" %16u MSB : %d\n", c, getmsb (c)); printf (" %16u MSB : %d\n", s, getmsb (s)); printf (" %16u MSB : %d\n", i, getmsb (i)); printf (" %16u MSB : %d\n", ui, getmsb (ui)); printf (" %16lu MSB : %d\n", ul, getmsb (ul)); printf (" %16llu MSB : %d\n", ull, getmsb (ull)); return 0; }
输出：
0 MSB : 0 216 MSB : 7 1021 MSB : 9 32767 MSB : 14 32768 MSB : 15 3297381253 MSB : 31 323543844043 MSB : 38
注意：出于速度方面的考虑，使用单个函数来完成以__builtin_clzll为中心的相同的事情仍然会快6倍。
我会加一个！
typedef unsigned long long u64; typedef unsigned int u32; typedef unsigned char u8; u8 findMostSignificantBit (u64 u64Val) { u8 u8Shift; u8 u8Bit = 0; assert (u64Val != 0ULL); for (u8Shift = 32 ; u8Shift != 0 ; u8Shift >>= 1) { u64 u64Temp = u64Val >> u8Shift; if (u64Temp) { u8Bit |= u8Shift; // notice not using += u64Val = u64Temp; } } return u8Bit; }
当然，这是一个64位数字（无符号long long），而不是一个数组。 而且，很多人都指出了我不知道的内置的g ++函数。 多么有趣。
无论如何，这在6次迭代中find最重要的位，并且如果将0传递给函数，则会产生断言。 如果您有权访问芯片组的指令，则不是最好的function。
我也使用| =而不是+ =，因为这些总是幂2，并且（典型地）比加法快。 因为我只是加在一起的独特的权力，我从来没有翻身。
这是一个二进制search，这意味着它总是在6次迭代中find结果。
再次，这是更好的：
u8 findMostSignificantBit2 (u64 u64Val) { assert (u64Val != 0ULL); return (u8) (__builtin_ctzll(u64Val)); }
下面是一个任意大小的字节数组的一个简单的powershellalgorithm：
int msb( unsigned char x); // prototype for function that returns // most significant bit set unsigned char* p; for (p = arr + num_elements; p != arr;) { --p; if (*p != 0) break; } // p is with pointing to the last byte that has a bit set, or // it's pointing to the first byte in the array if (*p) { return ((p - arr) * 8) + msb( *p); } // what do you want to return if no bits are set? return -1;
我将把它作为一个练习，让读者提出一个适当的msb()函数，以及优化工作在int或long long尺寸的chinks数据。
嗯，你的标签指示32位，但它看起来像你使用的值是16位。 如果你的意思是32位，那么我认为0x00a1的答案应该是24而不是8。
假设你正在寻找左边的MSB位索引，并且你知道你将只处理uint32_t，下面是一个明显的，简单的algorithm：
#include <stdlib.h> #include <stdio.h> #include <stdint.h> int main() { uint32_t test_value = 0x00a1; int i; for (i=0; i<32; ++i) { if (test_value & (0x80000000 >> i)) { printf("i = %d\n", i); exit(0); } } return 0; }
#define FFS(t) \ ({ \ register int n = 0; \ \ if (!(0xffff & t)) \ n += 16; \ \ if (!((0xff << n) & t)) \ n += 8; \ \ if (!((0xf << n) & t)) \ n += 4; \ \ if (!((0x3 << n) & t)) \ n += 2; \ \ if (!((0x1 << n) & t)) \ n += 1; \ \ n; \ })
