c++ - 给定一个无符号整数，很容易交换每个偶数位和奇数位。这可以概括为交换每个偶数和奇数 n 位吗？

Question

在 n = 1 的情况下，如果我们有一个无符号的 32 位整数 i，交换后的整数将是

((i & 0xaaaaaaaa) >> 1) | ((i & 0x55555555) << 1)

当 n = 2

((i & 0xcccccccc) >> 2) | ((i & 0x33333333) << 2)

当 n = 4

((i & 0xf0f0f0f0) >> 4) | ((i & 0x0f0f0f0f) << 4)

等等。

如果 n 是 2 的任意次幂呢？ ...并且，假设 i 是任意 128 位整数而不是 32 位整数，那么我们有 7 个案例而不是 5 个？

我怀疑有一种方法可以概括给定 n 的过程(即从 n 生成该掩码)，如果有它就好了，这样我就不必在每个案例出现时都对它进行硬编码向上(例如，实现某些加密哈希函数——例如 JH)。

想到的明显方法是遍历潜在的掩码，在 n 较大的情况下迭代次数较少，但我宁愿有一种方法可以在常数时间内完成，操作较少。

一些应该适用于 32 位整数的东西，例如:

uint32_t mask = 0; submask = (2n) - 1;

for (uint32_t index = 0; index < 32; index += 2n)
{
    mask |= submask;
    submask <<= 2n;
}

有没有更好的方法来生成该掩码(最好没有循环)？

编辑:我刚刚想到，而不是

((i & 0xaaaaaaaa) >> 1) | ((i & 0x55555555) << 1)

你可以做

((i & 0xaaaaaaaa) >> 1) | ((i << 1) & 0xaaaaaaaa)

这将允许根本不需要使用倒置掩码。万一有人要查看此内容以供引用，那可能会很方便。

Answer 1

我认为这种方法效率更高一些。您可以存储或生成第一个掩码值。如果我的 c++ 不太正确，请原谅我，我更像是一个 php/javascript 程序员。此代码将依次生成所有掩码，因此您可以将它们保存到一个数组中，或者只是在您想要的掩码处停止循环:

uint32_t mask = 0xffffffff; // can perhaps use int32 and -1?
for (uint32_t i = 4; i >= 0; i--)  {
   mask ^= mask >> (1 << i);
   cout << mask;
}