将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是在此处定义的。

有没有更加简单明了的方法？我正在使用C++编程。

- Loheek

---

还有另一种用于计算位的方法 https://tekpool.wordpress.com/2006/09/25/bit-count-parallel-counting-mit-hakmem/ - Andrey Belykh

使用表格映射countSetBit是一种非常直接的方法。 - apple apple

Answer 1

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

要在末尾设置指定数量的1，请转到下一个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中的第六位仅在nb_ones等于64时为1)

左移64位的未定义行为背后的原因可能是相应的本机操作只使用最大合理移位值所需的参数位，从C++方面处理这个问题会增加开销。

- Stefan Haustein

---

如果 x == (int64)-1 会怎么样呢？因为 1 << 64 会触发未定义行为。 - Nayuki

没错，就是这样（点个赞），但你需要检查边缘情况“-1”。 - Bathsheba

谢谢，问题已解决 O:) - Stefan Haustein

有一个非分支解决方案：int64_t res = ((1^(nb_ones>>6))<<nb_ones)-1; - nb_ones 中的第6位仅在 nb_ones==64 时为1。 - MSalters

Answer 2

您可以避免循环：

const auto nb_ones = countSetBit(x)
if (nb_ones == 64) {
    return -1; // 0xFFFFFFFFFFFFFFFF;
} else {
    return (1u << nb_ones) - 1;
}

- Jarod42

---

你认为0xFFFFFFFFFFFFFFFF比-1更清晰吗？还是我很奇怪？ - Bathsheba

Answer 3

计算所有位有些过度了，因为大多数CPU都可以有效地测试是否为零。

所以，我们使用它作为退出条件：

output = 0;
while (input != 0) {
  if (input & 1) output = (output<<1)+1;
  input >>= 1;
}

循环将输入向右移位，每当一个位从输入中移出时，就会向output添加一个额外的位。显然，这将添加与input中相同数量的位数到output中（可能为0，可能为64）。但是，output中的位是连续的，因为只有在添加位时才会进行移位。

如果你的CPU具有位计数操作，那当然会更快。如果您在x86或ARM汇编中实现此操作，您将使用input&1与>>=1移位操作的事实是相同的位。

- MSalters

---

你来晚了，但这仍然是最好的答案。点个赞！ - Bathsheba

Answer 4

尽管你已经得到了几个高效的答案，但是因为你实际上要求的是一个简单明了的答案，所以我给你提供一个概念上非常简单的答案，虽然不太快速：

uint64_t num(uint64_t x)
{
    // construct a base-2 string
    auto s = std::bitset<64>(x).to_string();
    // sort the 1s to the end
    std::sort(begin(s), end(s));
    // and convert it back to an integer
    return std::bitset<64>(s).to_ulong();
}

- Useless

---

这篇写得非常好，让我意识到我完全实现了错误的东西。顺便点个赞。 - Bathsheba

我仍然没有直觉理解为什么 OP 想要这些位，或者它可能有什么用处 - 这也是为什么我需要读几遍才能弄清楚的原因。 - Useless

Answer 5

我认为你可以只用一个循环来完成它：

std::uint64_t bits_to_end(std::uint64_t n)
{
    std::uint64_t x = 0;

    for(std::uint64_t bit = 0, pos = 0; bit < 64; ++bit)
        if(n & (1ULL << bit))
            x |= (1ULL << pos++);

    return x;
}

- Galik