c++ - 将设置位移动到 64 位整数的末尾

Question

我正在开发一个函数，该函数将一个 64 位整数作为参数并返回一个 64 位整数，所有位都设置在末尾。

01011001 -> 00001111   // examples
00010100 -> 00000011

我首先想到了下面的算法:

nb_ones = countSetBit(x)
int64 res = 1
for i from 1 to nb_ones+1:
    res |= (1 << i)

这里 countSetBit 是一个 defined here

还有更直接的吗？我在 C++ 中工作

Answer 1

countSetBit 可能已经针对您的平台进行了优化。

要在最后设置给定的个数，只需转到下一个 2 的幂并减去 1。

nb_ones = countSetBit(x)
int64 res = nb_ones == 64 ? -1 : ((1 << nb_ones) - 1);

编辑 来自 MSalters 评论的不错的非分支解决方案:

int64_t res = ((1^(nb_ones>>6))<<nb_ones)-1;

(当且仅当 nb_ones==64 时 nb_ones 的第 6 位是 1)

<< 64 的未定义行为的背景可能是相应的 native 操作可能仅使用最大合理移位值所需的参数位，并且在 C++ 端处理此操作会增加开销。