如何从左到右计算一个字节中连续设置的位的数量，直到第一个 0？

Question

我的英语不好，我不能问得更好，但请看下面：

如果二进制中的字节是 1 0 0 0 0 0 0 0 那么结果是 1
如果二进制中的字节是 1 1 0 0 0 0 0 0 那么结果是 2
如果二进制中的字节是 1 1 1 0 0 0 0 0 那么结果是 3
如果二进制中的字节是 1 1 1 1 0 0 0 0 那么结果是 4
如果二进制中的字节是 1 1 1 1 1 0 0 0 那么结果是 5
如果二进制中的字节是 1 1 1 1 1 1 0 0 那么结果是 6
如果二进制中的字节是 1 1 1 1 1 1 1 0 那么结果是 7
如果二进制中的字节是 1 1 1 1 1 1 1 1 那么结果是 8

但是如果例如二进制中的字节是 1 1 1 0 * * * * 那么结果是 3。

我将确定从左边连续设置了多少位通过一次操作向右移动。

结果不一定是 1-8 的数字，只是为了区分。 我认为一两次手术是可能的，但我不知道如何做。

如果你不知道短至 2 个操作的解决方案，请也写下来，我不会再尝试了。

Answer 1

我能想到的最简单的非分支解决方案：

y=~x
y|=y>>4
y|=y>>2
y|=y>>1

反转 x，并将最左边的 1 位（对应于非反转值中最左边的 0 位）向右扩展。将给出不同的值（虽然不是 1-8，但进行映射非常容易）。

110* ****

变成

001* ****
001* **1*
001* 1*1*
0011 1111

编辑：

正如在另一个答案中指出的那样，使用预先计算的查找表可能是最快的。由于只有 8 位，就内存消耗而言甚至可能是可行的。

编辑：

嘿，哎呀，我的错..你可以跳过反转，而用 and 代替。

x&=x>>4
x&=x>>2
x&=x>>1

如

110* ****

您所见

110* **0*
110* 0*0*
1100 0000

，所有以 110 开头的值都会产生相同的输出 (1100 0000)。

编辑：

实际上，“and”版本基于未定义的行为（移动负数），如果使用有符号的8位（即char，而不是C中的unsigned char），通常会做正确的事情），但正如我所说，该行为是未定义的，并且可能并不总是有效。

Answer 2

我会支持一个查找表...否则您也可以执行以下操作：

unsigned long inverse_bitscan_reverse(unsigned long value)
{
    unsigned long bsr = 0;
    _BitScanReverse(&bsr, ~value); // x86 bsr instruction
    return bsr;
}

编辑：并不是说您必须小心“值”没有归零位的特殊情况。请参阅 _BitScanReverse 的文档。