仅MSB置位的64位整数首置位字节索引查找的优化方案咨询

当然可以针对这个场景做大幅优化！因为你已经明确了置位只能出现在每个字节的最高有效位（也就是bit 7、15、23、31、39、47、55、63这8个固定位置），完全不用像通用De Bruijn算法那样扫描所有64位。下面给你两种高效的实现方案，都符合你不能用内置函数/汇编的要求：

方案一：分治法（无查表，极致高效） #

利用分治思想逐步缩小范围，只需要3次位运算判断就能定位到目标字节索引，代码简洁且执行效率极高：

#include <cstdint>

// 返回从LSB开始的第一个置位字节的索引（0-7），无置位时返回-1
int find_first_set_byte_msb(uint64_t x) {
    if (x == 0) {
        return -1; // 处理无置位的边界情况
    }

    int index = 0;

    // 先检查低4个字节（索引0-3）是否有置位
    if (!(x & 0x80808080ULL)) {
        index += 4;
        x >>= 32; // 移到高4字节继续检查
    }

    // 检查当前范围的低2个字节（索引0-1）是否有置位
    if (!(x & 0x8080ULL)) {
        index += 2;
        x >>= 16; // 移到高2字节继续检查
    }

    // 检查最后一个字节是否有置位
    if (!(x & 0x80ULL)) {
        index += 1;
    }

    return index;
}

代码解释： #

• 0x80808080ULL是低4字节每个字节的MSB为1的掩码，和输入值做与运算，结果为0就说明低4字节没有置位，直接跳到高4字节继续判断。
• 每次判断都将范围缩小一半，三次判断后就能精准定位到第一个置位的字节索引，完全避开了对无关位的扫描。

方案二：预查表法（代码简洁，可读性强） #

先将64位值转换为一个8位掩码（每个bit对应一个字节的MSB是否置位），再通过预定义的表格直接查询最低置位bit的索引：

#include <cstdint>

// 预定义表：索引对应8位掩码，值对应该掩码的最低置位bit的位置（即字节索引）
static const unsigned char lsb_index_table[256] = {
    0, 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,
    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
};

int find_first_set_byte_msb(uint64_t x) {
    if (x == 0) {
        return -1;
    }

    // 将64位值转换为8位掩码：每个bit对应一个字节的MSB是否置位
    uint8_t mask = static_cast<uint8_t>(
        ((x >> 7) & 1) |
        ((x >> 15) & 2) |
        ((x >> 23) & 4) |
        ((x >> 31) & 8) |
        ((x >> 39) & 16) |
        ((x >> 47) & 32) |
        ((x >> 55) & 64) |
        ((x >> 63) & 128)
    );

    return lsb_index_table[mask];
}

代码解释： #

• 第一步把64位输入值压缩成8位掩码，每个bit对应原数据中一个字节的MSB状态。
• 预定义的表格直接映射了所有256种掩码情况的最低置位bit位置，查表操作是O(1)的，代码可读性非常好。

这两种方案都完全符合你的要求：没有使用任何内置函数或内联汇编，而且因为利用了你的场景限制，比通用De Bruijn算法更高效——后者需要处理所有64位的可能置位情况，而我们只需要关注8个固定的位。

内容的提问来源于stack exchange，提问作者Lasse R