c - 在 char 变量中查找唯一 '1' 位的索引的最有效方法(在 C 中)

Question

这是一道面试题:
给定一个名为 ch 的 char 变量，当您知道它代表二进制形式的数字时，它的八位中只有一位等于“1”。 IE。 ，ch 的唯一可能值是:0x1、0x2、0x4、0x8、0x10、0x20、0x40、0x80。
给定变量 ch，我需要编写最有效的代码来获取“1”位的索引。例如:如果 ch == 0x1 -> 结果为 0。如果 ch == 0x4 -> 结果为 2。

显而易见的方法是使用 switch-case，但我需要更高效的方法。
您可以在此处进行任何位操作以实现高效实现吗？

Answer 1

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 序列的目的是在原始“未打包”表(如我上面的表)不适合整数的情况下打包索引表。作为一个“令人不快”的副作用，De Bruijn 序列重新排序了索引表，打破了索引的原始自然序列。这需要额外的重新映射工作才能从 De Bruijn 序列中提取正确的结果。

只有 24 位，我们在这里没有这个问题，这意味着不需要涉及 De Bruijn 及其伴随的技巧。

另一方面，打包表需要更短的移位，这将简化(并因此优化)除数的计算以获得所需的移位长度。对于 De Bruijn 序列，根本不需要计算除数——您的 ch 已经是除数了。因此，De Bruijn 序列可能很容易变得更有效率。