找到char变量中唯一’1’位的索引的最有效方法（在C中）
这是一个面试问题：
给你一个名为ch的char变量，当你知道它代表一个二进制forms的数字时，它的八位中只有一个将等于’1’。 IE， ch的唯一可能值是： 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80 。
给定变量ch ，我需要编写最有效的代码来获得该’1’位的索引。 例如：如果ch == 0x1 – >结果为0.如果ch == 0x4 – >结果为2。
显而易见的方法是使用switch-case，但我需要更高效的东西。
为了有效实施，您可以在这里进行任何操作吗？
一个unsigned char变量据说只有8位宽。 为了编码位的位置，我们只需要3位。 这意味着我们可以构建一个24位的“表”，其中包含按自然顺序排列的所有8个可能的3位答案
111 110 101 100 011 010 001 000 = 0xFAC688
如果已知变量ch只包含一个1位，则它是2的幂。将某个值除以ch将右移原始值乘以1位的索引。 因此，如果我们将上面的“表”除以你的ch 三次 ，答案将转移到结果的最低3位
unsigned position = (0xFAC688 / ch / ch / ch) & 0x7;
故事结局。 可以更有效地重写上述内容，同时保留一般原则。
注意，这基本上与基于De Bruijn序列的方法中使用的原理相同。 但是，De Bruijn序列的目的是在原始“unpacked”表（如上面的表）不适合整数的情况下打包索引表。 作为一种“令人不快”的副作用，De Bruijn序列重新排序索引表，打破了原始的自然序列索引。 这需要额外的重新映射工作以从De Bruijn序列中提取适当的结果。
只有24位我们在这里没有这个问题，这意味着没有必要涉及De Bruijn及其相应的技巧。
另一方面，打包表需要较短的移位，这将简化（并因此优化）除数的计算以实现期望的移位长度。 在De Bruijn序列的情况下，根本没有必要计算除数 – 你的ch已经是它了。 因此，De Bruijn序列可能很容易变得更有效率。
好吧，如果ch设置了一个比特，那么ch-1中1比特的计数就是该比特的索引。 理想情况下，你想要找到没有循环或分支的，因为分支是昂贵的，所以我写这样的东西：
int index = ((unsigned char)ch)-1; index = ((index & 0xAA)>>1)+(index & 0x55); //sums of pairs of bits index = ((index & 0xCC)>>2)+(index & 0x33); //sums of 4s of bits index = ((index & 0xF0)>>4)+(index & 0x0F); //sum of 8 bits
以乘法和查找为代价，使用较少的操作也有一个非常聪明的答案：
int index = indexMap[((((int)(unsigned char)ch)*DEBRUIJN)>>16)&7];
DEBRUIJN中的位必须是De Bruijn序列（ https://en.wikipedia.org/wiki/De_Bruijn_sequence ），确保查找索引对于ch每个值都不同。 indexMap将这些查找索引映射到您想要的结果。
另请注意，在@ rici的注释之后， indexMap非常小，您可以将其打包到单个int中。
编写最有效的代码来获取’1’位的索引。
最有效的代码是以某种方式将ch的值映射到其位索引，即：
0x01 -> 0 0x02 -> 1 0x04 -> 2 0x08 -> 3 ...
朴素的映射表
最简单和天真的解决方案需要在映射表中查找ch所有可能值。 对于8位数字（char），我们需要一个包含2 8 = 256个元素的表：
char naive_table[256]; naive_table[0x01] = 0; naive_table[0x02] = 1; naive_table[0x04] = 2; naive_table[0x08] = 3; naive_table[0x10] = 4; naive_table[0x20] = 5; naive_table[0x40] = 6; naive_table[0x80] = 7;
此表中的查找也很简单：
index = naive_table[ch];
散列函数+映射表
之前的解决方案简单而快速，但naive_table大部分元素都被浪费了。 考虑到ch是2的幂，对于任何n位数，只有n可能的索引。
因此，我们可以使用仅包含8个元素的表和散列函数来代替使用具有2 8个元素的映射表，该散列函数将ch的值映射到映射表的唯一索引。
这种散列函数的完美候选者将是使用de Bruijn序列的函数。 有一篇论文“使用de Bruijn序列对计算机词中的1进行索引” ，其中指出：
length-nde Bruijn的序列，其中n是2的精确幂，是n 0和1的循环序列，使得长度为lg n每个0-1序列恰好作为连续子串出现一次。例如，长度为8 de Bruijn的序列是00011101.每个3位数字恰好作为一个连续的子字符串出现一次：从最左边的3位开始并一次向右移动一个3位窗口，我们有000， 001,011,111,110,101,010（环绕），100（也环绕）。
哈希函数的计算公式为：h（x）=（x * deBruijn）>>（n – lg n）
所以，让我们尝试这个哈希函数在我们的紧凑查找表中获取一个唯一索引：
h(ch) = ((ch * 00011101b) >> (8 - 3)) & 0x7 h(ch) = ((ch * 29) >> 5) & 0x7
让我们计算ch所有值的散列，并确保散列函数按预期工作，即所有散列都是唯一的：
ch h(ch) 0x01 ((1 * 29) >> 5) & 0x7 = 0 0x02 ((2 * 29) >> 5) & 0x7 = 1 0x04 ((4 * 29) >> 5) & 0x7 = 3 0x08 ((8 * 29) >> 5) & 0x7 = 7 0x10 ((16 * 29) >> 5) & 0x7 = 6 0x20 ((32 * 29) >> 5) & 0x7 = 5 0x40 ((64 * 29) >> 5) & 0x7 = 2 0x80 ((64 * 29) >> 5) & 0x7 = 4
因此散列函数工作正常并为ch的两个值的每个幂产生唯一的散列。
现在让我们使用上表中的哈希值创建一个紧凑的映射表：
char compact_table[8]; compact_table[0] = 0; compact_table[1] = 1; compact_table[3] = 2; compact_table[7] = 3; compact_table[6] = 4; compact_table[5] = 5; compact_table[2] = 6; compact_table[4] = 7;
现在，对于查找，我们使用哈希值作为索引：
h = ((ch * 29) >> 5) & 0x7; index = compact_table[h];
散列函数+位串
以前的版本几乎是完美的：映射表中不再有浪费的元素。 但由于所有索引都在0-7之内（即只有3位值），因此仍有改进的余地。 让我们使用位串而不是映射表，这样就不会浪费每个元素的最高位。
首先，让我们使用ch所有值和先前版本的哈希值创建这样的位字符串：
ch h(sh) index 0x01 0 0 (000b) 0x02 1 1 (001b) 0x04 3 2 (010b) 0x08 7 3 (011b) 0x10 6 4 (100b) 0x20 5 5 (101b) 0x40 2 6 (110b) 0x80 4 7 (111b)
现在让我们按哈希值来命令这个表：
ch h(sh) index 0x01 0 0 (000b) 0x02 1 1 (001b) 0x40 2 6 (110b) 0x04 3 2 (010b) 0x80 4 7 (111b) 0x20 5 5 (101b) 0x10 6 4 (100b) 0x08 7 3 (011b)
所以位串将是这些3位索引的反向串联：
011 100 101 111 010 110 001 000 = 0x72f588
现在让我们像以前一样在这个位字符串中查找。 请注意，我们的索引是3位的，因此我们需要将哈希值乘以3：
h = ((ch * 29) >> 5) & 0x7; // just like before bit_string = 0x72f588; index = (bit_string >> (h * 3)) & 0x7;
或者简而言之：
index = (0x72f588 >> ((((ch * 29) >> 5) & 0x7) * 3)) & 0x7;
代码中没有分区/模数/条件，因此它应该在任何CPU上快速执行。
概念代码的certificate：
unsigned char ch; for (ch = 1; ch; ch <<= 1) { int index = (0x72f588 >> ((((ch * 29) >> 5) & 7) * 3)) & 7; printf("ch = 0x%02x index = %d\n", ch, index); } return 0;
char类型可以是signed或unsigned（实现定义的行为）。 为了安全地操作值0x80我们应该使用unsigned char数据显式操作。
我假设没有可用的特殊函数或多或少直接给我们位位置，例如ffs() （查找第一组）， clz() （计数前导零）或popcount() （填充计数），以及我们只使用标准ISO C来确定钻头位置。
一种方法是将ch中的每个位位置扩展到单独的半字节（四位组），然后执行寄存器表查找，其中每个表元素包含32位int一个半字节。
可以通过将输入平方两次来实现扩展，这将位[i]移动到位[4 * i]。 然后，下面的代码使用特殊技巧来允许使用乘法和右移提取表元素，其中乘法将所需的表条目移动到中间结果的位[31:28]。 请注意，该表以可读方式指定，并等于常量0x01234567 ，每个合理的编译器将进行替换。
编译器资源管理器（Godbolt） 显示 uchar_bitpos()大部分执行时间成本是三个相关的整数乘法加上一些其他指令。
此代码假定8位char和32位int 。 为了更好的可移植性， unsigned char变量可以转换为uint8_t变量， unsigned int变量可以转换为uint32_t变量。
#include #include int uchar_bitpos (unsigned char ch) { unsigned int ch_pow2, ch_pow4; const unsigned int table = ((0 << 28) | (1 << 24) | (2 << 20) | (3 << 16) | (4 << 12) | (5 << 8) | (6 << 4) | (7 << 0)); ch_pow2 = ch * ch; ch_pow4 = ch_pow2 * ch_pow2; return (ch_pow4 * table) >> 28; } int main (void) { unsigned char a = 0x80; do { printf ("a = %2x bitpos=%d\n", a, uchar_bitpos (a)); a = a / 2; } while (a); return EXIT_SUCCESS; }
上述程序的输出应如下所示：
a = 80 bitpos=7 a = 40 bitpos=6 a = 20 bitpos=5 a = 10 bitpos=4 a = 8 bitpos=3 a = 4 bitpos=2 a = 2 bitpos=1 a = 1 bitpos=0
快速且便携的解决方案是：
int charindex(unsigned char c){ union { /* Assume both float and int are 32 bits, assume IEEE 754 floating point. */ int i; float f; } x; xf = (float)c; return (xi >> 23) - 127; }
请注意，许多处理器都具有硬件支持，用于计算整数的前导或尾随零的数量。 使用gcc可以轻松访问这些特定指令：gcc具有内置函数__builtin_ctz() ，它可能比具有适当硬件支持的平台上的charindex更有效。
有效的代码行数可以是通过位的线性搜索。
short bit=0; const char one=1; while(!((ch >> bit) & one)) ++bit;
当然，错误检查可能是一个好主意，所以你也可以添加一个检查，以确保你仍然在有效位。
short bit=0; const char one=1; while(++bit < 8 && !((ch >> bit) & one)) {}
它绝对不具有计算效率，并且无法检测何时设置了多个位，因此开关盒仍然可能是正确性的方法。
这个人在组件中的跳跃少于开关盒，所以可能在计算钻头方面更有效率。
short bit= ch&0x2?1: (ch&0x4?2: (ch&0x8?3: (ch&0x10?4: (ch&0x20?5: (ch&0x40?6: (ch&0x80?7:8))))));
您也可以跳过检查最后一位，并假设如果没有其他任何内容匹配，则设置第7位可以保存一个比较。
short bit= ch&0x2?1: (ch&0x4?2: (ch&0x8?3: (ch&0x10?4: (ch&0x20?5: (ch&0x40?6:7)))));
您可以在此处使用二进制搜索技术将比较次数从7减少到3。
assert((n & n-1) == 0); if(n & 0x0F) { if(n & 0x03){ if(n & 0x01){ idx = 0; } else{ idx = 1; } }else{ if(n & 0x04){ idx = 2; } else{ idx = 4; } } }else{ if(n & 0x30){ if(n & 0x10){ idx = 3; } else{ idx = 4; } }else{ if(n & 0x40){ idx = 5; } else{ idx = 6; } } }
一些体系结构包含popcount高效（单指令）实现，可通过内在函数或__builtin_popcount()在C编译器中使用。
如果是这种情况，将很难击败popcount(x - 1) ，它将首先将单个设置位（1 << n）转换为来自（1 <<（n-1））的一组位。当x == 1时，1或0，然后计算1的数量，这是原始n的索引。
然而，有些评论指出“比特扫描转发”，至少在x86体系结构中不如popcount。 永远都知道你的HW ……
一些不高效的方法（取决于您对效率的定义）。
循环和移位方法。
int ch = 32 int i; for ( i=1;ch >>i ; i++) printf("%i %i \n",i, ch>>i); printf("Final index:%i\n",i-1);
调用math.h log2
int l=log2((double)ch); printf("math log2:%i\n",l);
更高效：对于单个查找，可能很难击败AnT的版本。 但是对于重复查找，查找表可能会表现得更好。
int ltable[256]= { -1 }; void initTable() { ltable[0x01]=0; ltable[0x02]=1; ltable[0x04]=2; ltable[0x08]=3; ltable[0x10]=4; ltable[0x20]=5; ltable[0x40]=6; ltable[0x80]=7; } int lookup(size_t ch) { return ltable[ch]; }
表init ASM
init(): push rbp mov rbp, rsp mov DWORD PTR ltable[rip+4], 0 mov DWORD PTR ltable[rip+8], 1 mov DWORD PTR ltable[rip+16], 2 mov DWORD PTR ltable[rip+32], 3 mov DWORD PTR ltable[rip+64], 4 mov DWORD PTR ltable[rip+128], 5 mov DWORD PTR ltable[rip+256], 6 mov DWORD PTR ltable[rip+512], 7 nop pop rbp ret
表查找ASM
lookup(unsigned long): push rbp mov rbp, rsp mov QWORD PTR [rbp-8], rdi mov rax, QWORD PTR [rbp-8] mov eax, DWORD PTR ltable[0+rax*4] pop rbp ret
输出
1 16 2 8 3 4 4 2 5 1 Final index:5 math log2:5 Lookup[32]=>5
如果只有一位设置为1 ，则表示它的幂为2 。 您可以通过log ch来直接获取索引。 当然，你必须使用2基日志。
最简单的解决方案可能不是最快的，但只有针对其他解决方案的分析才能让您确定，并且仅针对给定的体系结构和编译器。
这是一个非常简单的解决方案：
#include int leadingbit(unsigned char c) { return log2(c); }
这是一个带有查找表的解决方案：
int leadingbit(unsigned char c) { #define N(x) ((076543210 / (x) / (x) / (x)) & 7) #define N8(x) N(x), N(x+1), N(x+2), N(x+3), N(x+4), N(x+5), N(x+6), N(x+7) #define N32(x) N8(x), N8(x+8), N8(x+16), N8(x+24) static unsigned char table[256] = { N32(0), N32(32), N32(64), N32(96), N32(128), N32(160), N32(192), N32(224), }; #undef N #undef N8 #undef N32 return table[c]; }
这是一个受Matt Timmermans启发而没有记忆参考的人：
int leadingbit(unsigned char c) { int n = c - 1; n = ((n & 0xAA) >> 1) + (n & 0x55); //sums of pairs of bits n = ((n & 0xCC) >> 2) + (n & 0x33); //sums of 4s of bits return ((n >> 4) + n) & 7; }
这是一个使用非便携式builtin_clz()函数（计数前导零）：
#include int leadingbit(unsigned char c) { return CHAR_BIT * sizeof(unsigned) - 1 - builtin_clz((unsigned)c); }
请注意，以上所有都假设c是2的幂，其他值的行为可能未定义。 您可以使用简单表达式检查c是2的幂：
if (c && !(c & (c - 1))) { /* c is a power of 2 */ }