设置了 MSB 的第一个字节的索引

Question

我有八个 8 位值存储在一个 64 位整数中。每个字节的最高位可以为 1 或 0，其余位均为 0。示例：

MSB 10000000 00000000 10000000 ... 10000000 00000000 00000000 LSB

我现在需要找到设置了位的第一个字节的索引。首先意味着我们从最不重要的方向搜索。在上面的示例中，结果将是 2.

我们可以使用 de Bruijn 扫描第一个设置位并除以 8 以获得其字节索引。

这是我的问题：de Bruijn 是通用的，它适用于任何输入。但在我的用例中，我们仅限于仅设置了 MSB 的字节。是否可以针对这种情况进行优化？

实现是在 C++ 中。我不能使用任何内在函数或内联汇编（_BitScanForward64()、__builtin_clzll 等）。

Answer 1

(编辑) 隔离最低设置位 x &= (-x) 然后查看 How to find the position of the only-set-bit in a 64-bit value using bit manipulation efficiently? 正在检查这个确切的问题（尽管标题）。

下面的答案稍微笼统一些。

通过消除 table 查找，可以在 de Bruijn 位扫描上节省几个延迟周期。

uint64_t ByteIndexOfLowestSetBit(uint64_t val) {
    assert(val != 0);
    const uint64_t m = UINT64_C(0x0101010101010101);
    return ((((val - 1) ^ val) & (m - 1)) * m) >> 56;
}

使用尾随位操作获得覆盖最低设置位及以下的掩码。将掩码覆盖的每个字节设置为 1。通过 prefix-summing 横向计算我们有多少 1 字节。我们现在已经将一个从 1 开始的字节索引放入 u64 字的最高有效字节中。将计数移到底部并减去 1 以获得从 0 开始的索引。但是，我们不希望关键路径上的 -1...所以从 m 中减去 1，这样我们就永远不会计算总数中的最低有效字节。

找到最高集合 MS1B 的问题更复杂，因为我们没有任何 bit-manipulation 技巧来隔离想要的位。在这种情况下， Extract Bits with a Single Multiplication，将它们作为 table 的索引。如果不允许输入值为零，那么最低有效字节的值要么无关紧要，要么是 non-zero。这允许使用具有 7 位索引而不是 8 位索引的查找 table。

根据需要进行调整。

uint64_t ReversedIndexOf_Highest_Byte_With_LSB_Set (uint64_t val) {
    static const unsigned char ctz7_tab[128] = {
        7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
        5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
        6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
        5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
    };
    assert(val != 0);
    assert((val & 0xFEFEFEFEFEFEFEFEULL) == 0);
    val = (val * UINT64_C(0x0080402010080402)) >> 57;
    return ctz7_tab[val];
}

Answer 2

这里有一个简单的方法。

int LeastSignificantSetBitByteIndex(long value)
{
    if((value & 0x80) != 0) return 0;
    if((value & 0x8000) != 0) return 1;
    if((value & 0x800000) != 0) return 2;
    if((value & 0x80000000L) != 0) return 3;
    if((value & 0x8000000000L) != 0) return 4;
    if((value & 0x800000000000L) != 0) return 5;
    if((value & 0x80000000000000L) != 0) return 6;
    if((value & 0x8000000000000000L) != 0) return 7;
    return -1;
}
    
int MostSignificantSetBitByteIndex(long value)
{
    if((value & 0x8000000000000000L) != 0) return 0;
    if((value & 0x80000000000000L) != 0) return 1;
    if((value & 0x800000000000L) != 0) return 2;
    if((value & 0x8000000000L) != 0) return 3;
    if((value & 0x80000000L) != 0) return 4;
    if((value & 0x800000) != 0) return 5;
    if((value & 0x8000) != 0) return 6;
    if((value & 0x80) != 0) return 7;
    return -1;
}

设置了 MSB 的第一个字节的索引

Index of first byte having its MSB set

c++

bit-manipulation