c++ - 如何在 64 位整数中的所有 '1' 之后快速设置 9 位

Question

我正在编写一个 C++ 程序，需要一个函数在所有现有的“1”之后将所有 9 位设置为 1。

也就是说，我要编写一个函数 void set10BitsFull(int64_t& n) 用于整数 "int64_t n = 0b...1000000000... "，set10BitsFull(n) 将 n 转换为“0b...1111111111...”。

(更新)输入整数的位被稀疏地设置为 1，并且两个 1 之间至少有 10 位距离。对于示例输入 0x20000200，预期输出为 0x3FF003FF 。最后一个1之后至少有9位0，最左边的10位永远为0。

这是我实现的这个功能

/**
 * Inline function that set 10 bits to 1 after each set 1
 * i.e.,
 * ......1000000000...... -> ......1111111111.......
 *
 * @param n
 *      pointer of input number
 */
inline void set10BitFull(int_fast64_t *n) {
    // n = 1000000000
    *n |= (*n >> 1); // n = 1100000000
    *n |= (*n >> 2) | (*n >> 4) | (*n >> 6) | (*n >> 8); // n = 1111111111
}

在程序的主循环中，这两行代码会被频繁调用，在之前的测试中，计算成本非常高。因此，我想寻求一种计算开销更少(计算的 cpu 周期更少)的方法，可能的解决方案可能包括:

• 使用预先计算好的掩码
• 内联汇编
• x86/gcc 内置内在 ...

Answer 1

你可以这样做:

constexpr uint_fast64_t set10BitFull(uint_fast64_t n) {
    return (n << 1) - (n >> 9);
}

这应该适用于您描述的所有输入，其中每 1 位后至少有 9 个 0 位。