无分支实现有符号整数x<y时交换的高效位操作方案问询

嘿，这个需求抓得很准啊！要实现无分支、无乘法的if (x < y) { std::swap(x, y); }，完全可以靠位操作搞定，核心是利用有符号整数的符号位特性，彻底避开分支和乘法指令。

核心思路 #

对于有符号整数来说，当x < y时，x - y的结果是负数，它的最高位（符号位）会被置为1。我们可以把这个符号位通过算术右移扩展成一个全1（对应负数-1）或全0的掩码——因为有符号数的算术右移会用符号位填充高位，比如32位int的负数右移31位后会变成0xFFFFFFFF（即-1），正数则变成0x00000000。

具体实现代码 #

#include <cstdint>

void swap_if_less(int32_t& x, int32_t& y) {
    int32_t diff = x - y;
    // 算术右移生成掩码：x<y时为-1（全1），否则为0（全0）
    int32_t mask = diff >> 31;
    // 掩码控制异或交换：mask为-1时执行交换，为0时无操作
    x ^= (x ^ y) & mask;
    y ^= (x ^ y) & mask;
}

为啥这能行？ #

• 当x >= y时，diff是非负数，mask为0，(x^y)&mask的结果是0，x和y异或0后保持不变，相当于啥也没做；
• 当x < y时，mask是全1（即-1），(x^y)&mask就等于x^y，这时候x异或x^y得到y，y再异或x^y（此时x已经变成y，所以x^y等价于x）得到x，完美完成交换。

额外说明 #

1. 无分支无乘法：整个过程没有条件判断，也没有乘法指令，全是位运算和减法，CPU执行起来非常高效，完全避免了分支预测失败的性能损耗；
2. 有符号整数限制：这个技巧只适用于有符号整数，因为无符号整数的右移是逻辑右移（填充0），无法生成全1的掩码；
3. 溢出问题：如果x - y发生有符号整数溢出，这在C++标准里是未定义行为，但在大多数主流编译器（GCC、Clang、MSVC）的补码实现中，溢出后的结果符号位依然能正确反映x < y的关系，实际使用中通常没问题。

要是想追求极致简洁，也可以把代码压缩成一行（但可读性会下降）：

x ^= (y ^= x ^= y) & ((x - y) >> 31);

不过还是更推荐前面的分步写法，清晰易懂。

内容的提问来源于stack exchange，提问作者del