c++ - 在两个整数之间交换最右边的 N 位

Question

这个问题是在现场 C++ 编码面试中提出的。在那次采访中我没有提供一个好的答案。所以我希望在 stack overflow 得到人们的反馈和建议。现在我有更多的时间来想出一个解决方案，我相信我写了一个不错的解决方案。我认为这可以正常工作，因为 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);
}

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;
}

请注意，这使用了 3 个 XOR，就像您的解决方案一样，但只使用了一个掩码操作。另外，这对 CPU 寄存器更友好。没有错误的依赖链。最后，它在 &a==&b 时有效。