时间戳

首页 > 解决方案 > 设置了 MSB 的第一个字节的索引

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

问题描述

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

最高有效位 10000000 00000000 10000000 ... 10000000 00000000 00000000 最低有效位

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

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

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

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

标签： c++bit-manipulation

解决方案

（编辑）隔离最低设置位x &= (-x)，然后查看如何使用位操作有效地找到 64 位值中唯一设置位的位置？它正在检查这个确切的问题（尽管有标题）。

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

通过消除表查找，可以在 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. 1通过对它们进行水平前缀求和来计算我们有多少字节。我们现在已经在 u64 字的最高有效字节中放置了一个基于 1 的字节索引。将计数移到底部并减去1以获得从 0 开始的索引。但是，我们不希望-1在关键路径上......所以相反1，m我们从不计算总数中的最低有效字节。

找到最高集合 MS1B 的问题更加复杂，因为我们没有任何位操作技巧来隔离所需的位。在这种情况下， 使用单次乘法提取位，将它们用作表的索引。如果不允许输入值为零，则最低有效字节的值无关紧要或非零。这允许使用具有 7 位索引而不是 8 位的查找表。

根据需要进行调整。

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];
}

推荐阅读