以下来自我跟 DeepSeek 的对话：

我的提问

我要为 C 语言的 qsort 编写一个比较函数，比较两个 uint64_t ，考虑以下两种实现：

int qcmp_uint64(const void* pa, const void* pb) {
  uint64_t a = *(uint64_t*)pa;
  uint64_t b = *(uint64_t*)pb;
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}

int qcmp_uint64_2(const void* pa, const void* pb) {
  uint64_t a = *(uint64_t*)pa;
  uint64_t b = *(uint64_t*)pb;
  return a - b;
}

从直觉上看，似乎第二种实现效率更高，但由于整数相减可能溢出，我对第二种方案的正确性产生了怀疑

第二种方案是否正确？如何高效实现这一比较函数？

DeepSeek 回答

对于第二种实现 qcmp_uint64_2，直接返回 a - b 的确存在隐患。原因如下：

1. 无符号整数减法不会溢出，但结果始终为非负数。

   • 当 a < b 时，a - b 会得到一个极大的无符号值（模运算结果），例如 1 - 2 = UINT64_MAX 。

2. 转换为 int 可能导致符号错误：

   • 若 a - b 的值超过 INT_MAX ，转换为 int 时会触发实现定义行为（通常为截断高位，导致结果为负数）。此时 qsort 会误判 a < b ，造成排序错误。

例如：

• 若 a = 1, b = 2 ，则 a - b = UINT64_MAX 。
• 转换为 int 时，假设 int 为 32 位，结果为 -1 （正确）。
• 但若 a = 0x80000000, b = 0 ，在 32 位 int 下，转换后为负数（错误）。

高效且安全的实现 利用 比较操作的布尔值隐式转换为 0/1 ，可写出无分支的高效代码：

int qcmp_uint64(const void* pa, const void* pb) {
  uint64_t a = *(const uint64_t*)pa;
  uint64_t b = *(const uint64_t*)pb;
  return (a > b) - (a < b);  // 若 a > b 则 1-0=1 ； a < b 则 0-1=-1 ；相等则为 0
}

优点：

• 完全避免溢出风险：不依赖数值运算，仅用比较结果。
• 无分支：现代编译器（如 GCC/Clang ）会将其优化为无跳转指令，性能与 a - b 相近。
• 代码简洁：符合严格比较逻辑。

性能验证

在 x86-64 架构下，上述代码的典型汇编输出为：

mov    rax, [rdi]
cmp    [rsi], rax
setb   al
seta   cl
movzx  eax, al
movzx  ecx, cl
sub    eax, ecx
ret

完全无分支，效率与减法方案相当，且绝对安全。

结论：不要使用 a - b 方案，优先选择无分支的布尔比较实现。

点评

这个 (a > b) - (a < b) 的写法太巧妙了！

感觉这类惯用法（ idiom ）很难通过看书或网络学习，正是 AI 的强项

只搜到一个相关的： https://stackoverflow.com/questions/3886446/problem-trying-to-use-the-c-qsort-function