如何在 9 位整数中的所有"1"之后快速设置 64 位

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 位将始终为零。

这是我对这个函数的实现

/**
 * 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 位。

Answer 2

首先，你需要摆脱指针，访问内存是处理器最慢的操作。其次，您可以通过不断复制 1 的数量来减少操作次数。

即像这样：

 n |= n >> 1;  // will porduce 1100000000
 n |= n >> 2;  // will produce 1111000000
 n |= n >> 4;  // will produce 1111111100
 n |= n >> 2;  // will produce 1111111111