确定字节中的哪个位被设置
我有一个用于bitflags的byte 。 我知道在任何给定时间都设置了byte中的一个且只有一个位。
例如： unsigned char b = 0x20; //(00100000) 6th most bit set unsigned char b = 0x20; //(00100000) 6th most bit set
我目前使用以下循环来确定设置了哪个位：
int getSetBitLocation(unsigned char b) { int i=0; while( !((b >> i++) & 0x01) ) { ; } return i; }
如何最有效地确定设定位的位置？ 我可以不经迭代地完成这项工作吗？
我可以不经迭代地完成这项工作吗？
这确实是可能的。
如何最有效地确定设定位的位置？
你可以试试这个算法。 它将char分成两半以搜索最高位，每次都转移到低位：
int getTopSetBit(unsigned char b) { int res = 0; if(b>15){ b = b >> 4; res = res + 4; } if(b>3){ b = b >> 2; res = res + 2; } //thanks @JasonD return res + (b>>1); }
它使用两个比较（三个用于uint16 s，四个用于uint32 s …）。 它可能比你的循环更快。 绝对不会短。
根据Anton Kovalenko的想法（散列查找）和6502的评论（除法很慢），我也建议这个实现（使用de-Bruijn序列的8位=> 3位散列）
int[] lookup = {7, 0, 5, 1, 6, 4, 3, 2}; int getBitPosition(unsigned char b) { // return lookup[(b | (b>>1) | (b>>2) | (b>>4)) & 0x7]; return lookup[((b * 0x1D) >> 4) & 0x7]; }
或（较大的LUT，但只使用三个术语而不是四个）
int[] lookup = {0xFF, 0, 1, 4, 2, 0xFF, 5, 0xFF, 7, 3, 0xFF, 0xFF, 6, 0xFF, 0xFF, 0xFF}; int getBitPosition(unsigned char b) { return lookup[(b | (b>>3) | (b>>4)) & 0xF]; }
查找表很简单，如果值集稀疏，则可以减小其大小。 让我们试试11个元素而不是128个：
unsigned char expt2mod11_bits[11]={0xFF,0,1,0xFF,2,4,0xFF,7,3,6,5}; unsigned char pos = expt2mod11_bits[b%11]; assert(pos < 8); assert(1<
当然，它不一定更有效，特别是对于8位，但同样的技巧可以用于更大的尺寸，其中完整的查找表将非常大。 让我们来看看：
unsigned int w; .... unsigned char expt2mod19_bits[19]={0xFF,0,1,13,2,0xFF,14,6,3,8,0xFF,12,15,5,7,11,4,10,9}; unsigned char pos = expt2mod19_bits[w%19]; assert(pos < 16); assert(1<
对于使用64位来表示位置的国际象棋程序来说，这是一个相当普遍的问题（即，一个64位数字用于存储所有白色棋子的位置，另一个用于存储所有黑色棋子的位置，依此类推）。
有了这种表示，有时需要找到第一个或最后一个设置位的索引0 … 63，并且有几种可能的方法：
- 像你一样做一个循环
- 使用二分法搜索（即如果
x & 0x00000000ffffffffULL为零，则无需检查低32位） - 如果处理器上有特殊指令（例如x86上的
bsf和bsr） - 使用查找表（当然不是针对整个64位值，而是针对8位或16位）
然而，速度更快取决于您的硬件和实际使用情况。 对于仅8位和现代处理器，我认为可能有256个条目的查找表是最佳选择……
但你真的确定这是你的算法的瓶颈吗？
unsigned getSetBitLocation(unsigned char b) { unsigned pos=0; pos = (b & 0xf0) ? 4 : 0; b |= b >>4; pos += (b & 0xc) ? 2 : 0; b |= b >>2; pos += (b & 0x2) ? 1 : 0; return pos; }
跳跃是很难的。 也许与Bruin序列？
最简单的方法是创建一个查找表。 最简单的一个是稀疏的（有256个元素）但它在技术上会避免迭代。
这里的评论在技术上避免了迭代，但是我们开玩笑的是，它仍在进行相同数量的检查： 如何在c / c ++中编写日志库（2）
封闭forms将是log2（） ，la， log2() + 1但是我不确定它的效率如何 – 可能CPU有一个指令来获取基数为2的对数？
基于log2计算在O（lg（N））操作中查找N位整数的日志库2 ：
int getSetBitLocation(unsigned char c) { // c is in {1, 2, 4, 8, 16, 32, 64, 128}, returned values are {0, 1, ..., 7} return (((c & 0xAA) != 0) | (((c & 0xCC) != 0) << 1) | (((c & 0xF0) != 0) << 2)); }
如果你定义
const char bytes[]={1,2,4,8,16,32,64,128}
并使用
struct byte{ char data; int pos; } void assign(struct byte b,int i){ b.data=bytes[i]; b.pos=i }
您不需要确定设置位的位置
当CHAR_BIT == 8时，查找表快速而简单，但在某些系统上，CHAR_BIT == 16或32，查找表变得非常笨重。 如果您正在考虑查找表，我建议将其包装; 相反，使它成为“查找表函数”，以便在需要优化时可以交换逻辑。
使用除法和征服，通过对已排序的数组执行二进制搜索，涉及基于log2 CHAR_BIT比较。 该代码更复杂，涉及初始化unsigned char数组以用作start的查找表。 一旦初始化了这样的数组，就可以使用bsearch来搜索它，例如：
#include #include void uchar_bit_init(unsigned char *table) { for (size_t x = 0; x < CHAR_BIT; x++) { table[x] = 1U << x; } } int uchar_compare(void const *x, void const *y) { char const *X = x, *Y = y; return (*X > *Y) - (*X < *Y); } size_t uchar_bit_lookup(unsigned char *table, unsigned char value) { unsigned char *position = bsearch(lookup, c, sizeof lookup, 1, char_compare); return position ? position - table + 1 : 0; } int main(void) { unsigned char lookup[CHAR_BIT]; uchar_bit_init(lookup); for (;;) { int c = getchar(); if (c == EOF) { break; } printf("Bit for %c found at %zu\n", c, uchar_bit_lookup(lookup, c)); } }
PS这听起来像微优化。 完成解决方案（将这些function所需的操作抽象出来），然后根据您的分析担心优化。 如果您要专注于微优化，请确保您的分析针对您的解决方案将运行的系统，因为微优化的效率差异很大，因为硬件差异甚至略有...通常更好的想法是购买更快的PC;）