如何快速设置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位将始终为零。

这是我对该功能的实现

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