尽快交换整数中的两位

Question

我一直在看其中一些关于有趣面试问题的书。一个人有一个问题，在给定两位索引的情况下，应该编写代码来翻转 64 位整数中的两位。玩了一会儿之后，我想出了下面的代码，它比教科书中给出的解决方案更快，因为它没有任何分支：

uint64_t swapbits(uint64_t n, size_t i, size_t j)
{
  // extract ith and jth bit
  uint64_t bi = ((uint64_t) 0x1 << i) & n;
  uint64_t bj = ((uint64_t) 0x1 << j) & n;

  // clear ith and jth bit in n
  n ^= bi | bj;

  n ^= (bi >> i) << j;
  n ^= (bj >> j) << i;

  return n;
}

我的问题基本上如下：有没有更快的方法？

编辑：这是另一个实现作为参考：

uint64_t swapbits(uint64_t x, size_t i, size_t j)
{
  if(((x >> i) & 1) != ((x >> j) & 1)) {
    x ^= (1L << i) | (1L << j);
  }
  return x;
}

通过编译器优化，后者在 Core i7 4770 上慢了大约 35%。正如我在评论中所说，我很想知道是否有任何有趣的技巧可以非常有效地做到这一点。我见过一些非常聪明的小技巧，只需几条指令就可以完成看起来相当复杂的事情。

Answer 1

这是一个仅使用 7 个操作的解决方案。请注意，即使 i == j.

这也有效

uint64_t swapbits(uint64_t n, size_t i, size_t j)
{
    uint64_t x = ((n >> i) ^ (n >> j)) & 1; // x = 1 bit "toggle" flag
    return n ^ ((x << i) | (x << j));       // apply toggle to bits i and j
}

说明：只有索引i和j的原始位不同（10或01）时x才等于1，因此需要切换。否则为零，位保持不变（00 或 11）。然后，我们将此切换位应用于原始位（即，将其与原始位进行异或）以获得所需的结果。

尽快交换整数中的两位

Swapping two bits in an integer as quickly as possible

bit-manipulation