查找char变量中唯一“ 1”位的索引的最有效方法（在C中） [英] Most efficient way to find the index of the only '1' bit in a char variable (in C)

问题描述

这是一个面试问题：

当您知道它表示二进制数时，您会得到一个名为 ch 的char变量。形式，其八位中只有一位等于 1。即， ch 的唯一可能值是： 0x1、0x2、0x4、0x8、0x10、0x20、0x40、0x80 。

给定变量 ch ，我需要编写最有效的代码来获取该 1位的索引。例如：如果 ch == 0x1 ->结果为0。如果 ch == 0x4 ->结果为2

This is an interview question:
You are given a char variable named ch, when you know that it represents a number that in its binary form, only one of its eight bits will be equal to '1'. I.E. , the only possible values for ch are: 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80.
Given the variable ch, I need to write the most efficient code to get the index of that '1' bit. For example: if ch == 0x1 -> result is 0. if ch == 0x4 -> result is 2.

最明显的方法是使用switch-case，但是我需要更有效的方法。

您可以在此处进行任何操作吗？

The obvious way is to use switch-case, but I need something more efficient.
Is there any bit manipulation you can do here for efficient implementation?

推荐答案

一个 unsigned char 变量据说只有8位宽。为了编码位的位置，我们只需要3位。这意味着我们可以构建一个24位的表，其中包含所有8个可能的3位答案的自然顺序

An unsigned char variable is supposedly only 8 bit wide. In order to encode the position of the bit we need only 3 bits. That means that we can build a 24-bit "table" that contains all 8 of possible 3-bit answers in their natural order

111 110 101 100 011 010 001 000 =

0xFAC688

如果已知变量 ch 仅包含一个 1 位，则它的幂为2。除以 ch 会将原始值右移 1 位的索引。因此，如果将上面的表格除以您的 ch 三遍，答案将移至结果的最低3位

If your variable ch is known to contain only one 1 bit, then it is a power of 2. Dividing something by ch will right-shift the original value by the index of your 1 bit. So, if we divide the above "table" by your ch three times the answer will get shifted to the lowest 3 bits of the result

unsigned position = (0xFAC688 / ch / ch / ch) & 0x7;

故事的结尾。在保留一般原理的同时，可以更有效地重写以上内容。

End of story. The above could probably be rewritten more efficiently, while preserving the general principle.

请注意，这基本上是相同的原理这是基于De Bruijn序列的方法中使用的。但是，De Bruijn序列的目的是在原始的未打包表（如上面的我的表）不适合整数的情况下打包索引表。作为令人不快的副作用，De Bruijn序列对索引表进行了重新排序，从而破坏了索引的原始自然序列。这需要额外的重新映射工作，才能从De Bruijn序列中提取正确的结果。

Note, that this is basically the same principle that's used in the approaches based on De Bruijn sequences. However, the purpose of De Bruijn sequence is to pack the index table in situations when the original "unpacked" table (like my table above) does not fit into an integer. As an "unpleasant" side effect, De Bruijn sequence reorders the index table, breaking the original natural sequence of indices. This requires extra re-mapping efforts to extract the proper result from the De Bruijn sequence.

只有24位，我们在这里没有这个问题，这意味着

With only 24 bits we don't have this problem here, which means that there's no need to involve De Bruijn and its accompanying tricks.

另一方面，打包表需要更短的移位，这将简化（从而优化）计算结果。除数以实现所需班次的长度。如果是De Bruijn序列，则根本不需要计算除数-您的 ch 已经存在。因此，De Bruijn序列可能很容易最终变得更有效率。

On the other hand, a packed table requires a shorter shift, which will simplify (and thus optimize) the calculation of the divisor to achieve the desired shift's length. In case of De Bruijn sequence, there's no need to calculate the divisor at all - your ch is already it. So, De Bruijn sequence might easily end up being more efficient.

这篇关于查找char变量中唯一“ 1”位的索引的最有效方法（在C中）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！