我有一个 byte
用于位标志。我知道 byte
中的one and only one 位是在任何给定时间设置的。
例如:unsigned char b = 0x20;//(00100000) 第 6 位设置
我目前使用以下循环来确定设置了哪个位:
int getSetBitLocation(unsigned char b) {
int i=0;
while( !((b >> i++) & 0x01) ) { ; }
return i;
}
如何最有效地确定设置位的位置?我可以在没有迭代的情况下做到这一点吗?
最佳答案
Can I do this without iteration?
确实有可能。
How do I most efficiently determine the position of the set bit?
你可以试试这个算法。它将 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
,四个用于 uint32
...)。它可能比你的循环更快。它绝对不会更短。
基于 Anton Kovalenko 的想法(哈希查找)和 6502 的评论(除法很慢),我还建议这个实现(8 位 => 3 位哈希使用 de-Bruijn 序列)
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];
}
关于c - 确定设置了字节中的哪一位,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14429661/