交换两个整数中最右边的N位二进制位

Question

这个问题是在一次C++面试中提出的。当时我没有提供一个好的答案，所以我希望从这里的人们获得反馈和建议。现在我有更多的时间来想出一个解决方案，我认为自己写了一个不错的解决方案。我认为只要a和b引用不同的整数，这个方法就可以很好地工作。如果a和b引用相同的整数，那么该整数将被覆盖为0。

void SwapRightMostNBits(int& a, int& b, unsigned int n){

    if (n>31) { n=31; }
    int mask=static_cast<int>(pow(2,n)-1);

    a ^= (b & mask);
    b ^= (a & mask);
    a ^= (b & mask);
}

- claytonjwong

---

整数的幂运算 --> 面试失败，下一个。 - Marc Glisse

请使用 1 << n 替代 pow(2,n)，对无符号整数值执行位操作。 - Artemy Vysotsky

这不是面试失败。谁在乎呢。有人可能会认为你应该说出你的意思。在这里转移并不重要。 - Millie Smith

@Ron：我倾向于从这样一个问题开始。如果你能进入面试环节，这应该很容易。即使你有点初级，它也应该有助于缓解紧张情绪。我并不是真的在乎答案；这更多是为了帮助我判断接下来要问什么。 - MSalters

此外，在面试中，我个人绝不会使用可爱的异或（XOR）技巧。这种做法让人感觉是死记硬背，而非解决问题，而且我很少使用它，因此担心会出错。我会使用一个temp变量进行常规交换，并提到异或技巧作为另一种选择。 - user4442671

Answer 1

我认为这里的意图是要实现一个技巧，

void SwapRightMostNBits(unsigned int& a, unsigned int& b, unsigned int n){

    unsigned int mask=(1U<<n) -1;
    unsigned int diff = (a^b) & mask;

    a ^= diff;
    b ^= diff;
}

请注意，这个方法使用了三个异或运算（像你的解决方案一样），但只进行了一次掩码操作。此外，这种方法对CPU寄存器更加友好，没有错误依赖链。最后，它可以处理 &a==&b 的情况。

- MSalters

---

你说的“false dependency chains”是指 Load-Hit-Store，对吗？ - user4442671

谢谢MSalters，这看起来是一个更好的解决方案！ - claytonjwong

@Frank：不，那是当一个单一的值在内存中来回移动时发生的情况。现代CPU尝试并行执行N条指令，只有当第N个指令不依赖于前N-1个指令时才可能实现。这就是为什么CPU动态地确定依赖关系，并且这些关系可以被链接起来。"经典的XOR交换"存在问题，因为最终的A值取决于A和B，因为它们被XOR在一起，B也是如此，这意味着第一个XOR必须在下一个操作开始之前完成。 - MSalters

@MSalters 这正是我的担忧。移除 OP 的左手边将会产生比释放 OOO 执行（取决于 CPU 流水线，可能会增加约 10 倍）更大的影响。 - user4442671

@Frank：嗯，它们是相互关联的。OOOE 还允许您在等待加载指令时启动新指令。在我的示例中，a^b 可以立即开始。可能需要一段时间才能完成 a^b，但完成后掩码就可用了。 - MSalters