一行代码实现比较？

先看成果

#include <stdio.h>
int main(){
    long long a;
    int b;
    scanf("%lld%d",&a,&b);
    putchar("<=>"[1+(a>b)-(a<b)]);
    return 0;
}

上面这段代码相当简洁，它读取两个整数，然后输出一个字符表示它们的关系：<、= 或 >。你可以逐个模拟验证它的准确性：

当 a > b：(a>b)=1, (a<b)=0 → 下标为 1+1-0=2 → 输出 '>'
当 a < b：(a>b)=0, (a<b)=1 → 下标为 1+0-1=0 → 输出 '<'
当 a = b：(a>b)=0, (a<b)=0 → 下标为 1+0-0=1 → 输出 '='

那么，我是如何想到这种写法的呢？这要从一个性能优化问题说起。

性能优化之旅

问题起源

我在写 P3695 CYaRon!语时，遇到了一个函数的性能瓶颈。原始函数是一个条件判断函数，根据比较类型返回布尔值：

char assign_cond_old(enum TokType cond_typ, int left, int right) {
  switch (cond_typ) {
  case TOK_CMP_LT: return left < right;
  case TOK_CMP_GT: return left > right;
  case TOK_CMP_LE: return left <= right;
  case TOK_CMP_GE: return left >= right;
  case TOK_CMP_EQ: return left == right;
  case TOK_CMP_NEQ: return left != right;
  default: return 0;
  }
}

这段代码可读性极好，任何初学者都能看懂。但使用 gcc -O2 编译后，反汇编出来的结果让我吃惊——短短几行 C 代码，竟然生成了 62 字节的机器码！

ASM

assign_cond_old:
   0x0000000000003a30 <+0>:     add    $0xffffffec,%edi
   0x0000000000003a33 <+3>:     cmp    $0x5,%edi
   0x0000000000003a36 <+6>:     ja     0x3a6c <assign_cond_old+60>
   0x0000000000003a38 <+8>:     lea    -0x2b93(%rip),%rax        # 0xeac
   0x0000000000003a3f <+15>:    movslq (%rax,%rdi,4),%rcx
   0x0000000000003a43 <+19>:    add    %rax,%rcx
   0x0000000000003a46 <+22>:    jmp    *%rcx
   0x0000000000003a48 <+24>:    cmp    %edx,%esi
   0x0000000000003a4a <+26>:    setl   %al
   0x0000000000003a4d <+29>:    ret
   0x0000000000003a4e <+30>:    cmp    %edx,%esi
   0x0000000000003a50 <+32>:    setle  %al
   0x0000000000003a53 <+35>:    ret
   0x0000000000003a54 <+36>:    cmp    %edx,%esi
   0x0000000000003a56 <+38>:    setne  %al
   0x0000000000003a59 <+41>:    ret
   0x0000000000003a5a <+42>:    cmp    %edx,%esi
   0x0000000000003a5c <+44>:    setge  %al
   0x0000000000003a5f <+47>:    ret
   0x0000000000003a60 <+48>:    cmp    %edx,%esi
   0x0000000000003a62 <+50>:    setg   %al
   0x0000000000003a65 <+53>:    ret
   0x0000000000003a66 <+54>:    cmp    %edx,%esi
   0x0000000000003a68 <+56>:    sete   %al
   0x0000000000003a6b <+59>:    ret
   0x0000000000003a6c <+60>:    xor    %eax,%eax
   0x0000000000003a6e <+62>:    ret

优化思路

仔细观察这 6 种比较操作，我发现了它们之间的内在关系：

基础关系：实际上只需要两个基本比较结果就能推导出所有情况：
- lt = (left < right)
- gt = (left > right)
- eq = !lt && !gt （等于就是既不小于也不大于）
分类整理：
- TOK_CMP_LT: lt
- TOK_CMP_GT: gt
- TOK_CMP_NEQ: lt || gt
- TOK_CMP_GE: !lt
- TOK_CMP_LE: !gt
- TOK_CMP_EQ: !(lt || gt)
关键发现：后三种是前三种的逻辑非！

优化实现

基于这个发现，我写出了优化版本：

char assign_cond(enum TokType cond_typ, int left, int right) {
  cond_typ -= TOK_CMP_LT;
  if (cond_typ < 0 || cond_typ >= 6)
    return 0;

  int lt = (left < right);
  int gt = (left > right);

  const char results[] = {
      lt,            // TOK_CMP_LT
      gt,            // TOK_CMP_GT
      lt || gt,      // TOK_CMP_NEQ
      // 下面三个是上面三个的取反，通过异或实现
  };
  
  return results[cond_typ % 3] ^ (cond_typ >= 3);
  // 基于以下的代码优化：
  // return cond_typ >= 3 ? !results[cond_typ - 3] : results[cond_typ];
}

优化成果

编译后，新版本的汇编代码仅 44 字节，比原版减少了 29%：

ASM

assign_cond:
   0x0000000000003a70 <+0>:     lea    -0x14(%rdi),%eax
   0x0000000000003a73 <+3>:     cmp    $0x5,%eax
   0x0000000000003a76 <+6>:     jbe    0x3a7b <assign_cond+11>
   0x0000000000003a78 <+8>:     xor    %eax,%eax
   0x0000000000003a7a <+10>:    ret
   0x0000000000003a7b <+11>:    cmp    %edx,%esi
   0x0000000000003a7d <+13>:    setl   -0x3(%rsp)
   0x0000000000003a82 <+18>:    setg   -0x2(%rsp)
   0x0000000000003a87 <+23>:    setne  -0x1(%rsp)
   0x0000000000003a8c <+28>:    add    $0xffffffe9,%edi
   0x0000000000003a8f <+31>:    cmp    $0x3,%eax
   0x0000000000003a92 <+34>:    cmovb  %eax,%edi
   0x0000000000003a95 <+37>:    setae  %al
   0x0000000000003a98 <+40>:    xor    -0x3(%rsp,%rdi,1),%al
   0x0000000000003a9c <+44>:    ret

这给我们什么启示呢？

减少分支：分支预测失败的成本很高，能用数学运算代替分支判断时尽量使用
发现模式：很多看似不同的操作可能是同一模式的不同表现
利用对称性：逻辑非（!）可以通过异或（^）高效实现
索引技巧：用数组和索引代替 switch-case 有时能显著提升性能

这次优化经历，让我鼓起勇气尝试了更多例子，从而写出了文章开头那行优雅的代码。

性能对比总结

版本	代码风格	汇编大小	核心思想
原版	直观易读	62 字节	直接翻译每种情况
优化版	紧凑高效	44 字节	利用对称性，减少重复比较

优化不是魔法，而是对问题本质的更深理解。

思考题：你能用类似的思想，写出一个更简洁的比较函数吗？

一行代码实现比较？

讨论操作

先看成果

性能优化之旅

问题起源

优化思路

优化实现

优化成果

这给我们什么启示呢？

性能对比总结

回复

相关推荐

一行代码实现比较？