查找 64 位中零半字节的位置

Question

我得到一个 64 位数字，由 16 个半字节（4 位块）组成。我知道其中有一个半字节为零 (

0b0000

)，我需要找到它的索引 (0-15)。 我的限制是我不能使用迭代、循环或分支（if/else）。

我只能使用位操作，但我可以访问内置函数，例如

__builtin_ctzll

或

__builtin_ffsll

（我正在使用 GCC）。

我对位操作没有很好的掌握，所以到目前为止我只尝试了以下方法：

x |= x >> 1;
x |= x >> 2;

这似乎给出了目标半字节在哪里的某种想法，但我无法真正找到下一步，而且有很多情况下它不能按预期工作......

我也看过一个极其相似的问题：Fast Lookup of a null nibble in a 64 bit unsigned

提供的答案表明以下功能应该有效：

int zero_nibble_position (uint64_t a)
{
    const uint64_t nibble_lsb = 0x1111111111111111ULL;
    const uint64_t nibble_msb = 0x8888888888888888ULL; 
    uint64_t t = (a - nibble_lsb) & (~a & nibble_msb);
    return __builtin_clzll(t)/4;
}

对于某些输入，它确实有效，但有时却无效。 例如，

0b0001000000111010010101100111001010010001010011001101111011111011

(1169342103320059643) 应返回 1，但实际上返回 0。

一般来说，一旦

0b0000

半字节位于

0b0001

之后，索引就会错误

Answer 1

Alan Mycroft 的空字节检测算法（此处适用于半字节）的一个属性是，该技巧可靠地检测到“最低”零，但其左侧的位（更高有效位）并不可靠。 当您使用从最低有效位向上计数的位扫描时，就像链接的答案一样，那么这并不重要：要么没有零（因此没有麻烦的位），要么有一个零和一个位从最低有效位开始扫描将忽略结果中不可靠的部分。

使用从最高有效位向下扫描，如

__builtin_clzll

，

is

受到结果不可靠部分的影响。所以这些东西不能结合起来。

如果您可以使用最低有效零半字节的索引（您应该能够做到这一点，因为您指示只有一个半字节为零），您可以继续使用 Mycroft 零检测技术的变体，但结合使用与
• __builtin_ctzll

  一起使用（在 C23 中，您可以使用

  stdc_trailing_zeros

  中的

  stdbit.h

  作为便携式选项）。

如果您需要最高有效零半字节的索引，则需要不同的零半字节检测，而没有该属性，即零以上的更高有效位是不可靠的。你离建造一个已经不远了。例如：

• x |= x >> 1;
  x |= x >> 2;
  // the least significant bit of every nibble indicates
  // whether the corresponding nibble was non-zero
  x &= 0x1111111111111111ULL;
  // set the nibble to 0xF if it was originally non-zero,
  // keep it 0x0 if it was originally zero
  x = (x << 4) - x;