用 40 亿条 if 语句，只为判断一个数字是奇是偶？

逍遥设计自动化 · 发表于 2024-1-8 08:31:00

点击上方“C语言与CPP编程”，选择“关注/置顶/星标公众号”
干货福利，第一时间送达！

ywrehzkgavv640106051732.png

转自：CSDN（ID：CSDNnews）
# `$ E) |# A* ?; m& ^: }8 u看到这个标题，相信大多数人的第一反应是：真的有人用 40 亿条 if 语句，只为判断一个数字是奇数还是偶数？
的确有，这个开发者名为 Andreas Karlsson，他还把整个过程都整理成文了。

15l22ligikm640106051832.png

或许由于这“40 亿条 if 语句”听起来实在震撼，Andreas Karlsson 分享的这篇文章在 Hacker News 上很快引起了极大的关注和讨论，而他在文中也直白表示：其实这个想法，最初源于一个充满恶评的短视频。

aw5bpvdwhyl640106051932.png

以下为译文：

cni3nad0fs1640106052032.png

大于 11 的数字，没有输出结果
我最近在火车上刷手机时，偶然发现了上面这个截图：“写了一个程序，来判断一个数字是偶数还是奇数。”点开评论区，果然是一连串的恶意评论，多数都在嘲笑这位新手程序员的稚嫩和无知，竟企图以这种方式解决计算机科学中的经典问题“取模运算”。
可看过截图中的代码和网友评论后，我莫名生出了一些不同的想法：现在，AI 正在分分钟取代程序员、抢走他们的饭碗，并彻底改变了我们对代码的思考方式，或许我们应该更加开放地接受这个行业新生代的思想？
其实仔细想来，上述代码是时间和空间的一种完美权衡：你在付出自己时间的同时，也换来了计算机的内存和时间——这难道不是一个神奇的算法吗？
于是，我开始探索这种只使用比较来判断一个数字是奇数还是偶数的想法，看看它在实际情况中的效果到底如何。由于我是一位高性能代码的忠实拥护者，因此我决定用 C 语言来实现这个想法。
然后，我就开始编码了：
/* Copyright 2023. All unauthorized distribution of this source code
will be persecuted to the fullest extent of the law*/
#include
#include
#include
int main(int argc, char* argv[])
{
uint8_t number = atoi(argv[1]); // No problems here
if (number == 0)
      printf("even
");
if (number == 1)
      printf("odd
");
if (number == 2)
      printf("even
");
if (number == 3)
      printf("odd
");
if (number == 4)
      printf("even
");
if (number == 5)
      printf("odd
");
if (number == 6)
      printf("even
");
if (number == 7)
      printf("odd
");
if (number == 8)
      printf("even
");
if (number == 9)
      printf("odd
");
if (number == 10)
      printf("even
");
}
接下来，我们要编译这段代码，使用 /Od 禁用优化，确保烦人的编译器不会干扰我们的算法。编译完成后，我们就可以对程序进行快速测试，看看结果如何：
PS > cl.exe /Od program.c
PS > .\program.exe 0
even
PS > .\program.exe 4
even
PS > .\program.exe 3
odd
PS > .\program.exe 7
odd
结果显示：0、4 是偶数，3、7 是奇数。这么看来，程序似乎运行得挺好，但在进一步测试后，我发现了一些问题：
PS > .\program.exe 50
PS > .\program.exe 11
PS > .\program.exe 99

大于 11 的数字没有输出，看来这个程序只对 11 以下的数字有效！回到原始代码中，可以发现问题出在最后一个 if 语句之后：我们需要更多的 if 语句！

aveoj23prhh640106052132.png

向 32 位（32-bit）数扩展
这件事进行到这里，就需要我在时间和内存之间做出权衡了。考虑到我的寿命有限，我决定用另一种编程语言对 if 语句进行元编程。为了弥补这种“作弊”行为，我决定用“地球上速度最慢”的语言 Python。
print("/* Copyright 2023. All unauthorized distribution of this source code")
print(" will be persecuted to the fullest extent of the law*/")

print("#include ")
print("#include ")
print("#include ")

print("int main(int argc, char* argv[])")
print("{")
print(" uint8_t number = atoi(argv[1]); // No problems here")

for i in range(2**8):
print(" if (number == "+str(i)+")")
if i % 2 == 0:
      print("       printf(\"even\n\");")
else:
      print("       printf(\"odd\n\");")
print("}")
好了！现在我们可以生成一个程序，解决所有 8 位（8-bit）整数的奇偶问题！
PS > python programmer.py > program.c
PS > cl.exe /Od program.c
PS > .\program.exe 99
odd
PS > .\program.exe 50
even
PS > .\program.exe 240
even
PS > .\program.exe 241
odd
看看，这个效果简直完美！现在，让我们把它放大到 16 位（16-bit）！
print(" uint16_t number = atoi(argv[1]); // No problems here")
…
for i in range(2**16):

这样就得到了一个约 13 万行、超长且漂亮的 c 文件。回顾了一下我多年工作所做的一些代码库，这其实不算什么。话不多说，开始编译！
PS > python programmer.py > program.c
PS > cl.exe /Od program.c
PS > .\program.exe 21000
even
PS > .\program.exe 3475
odd
PS > .\program.exe 3
odd
PS > .\program.exe 65001
odd
PS > .\program.exe 65532
even
太棒了，我们的算法似乎能够处理大量数据！可执行文件大约只有 2 MB，但这与我拥有高达 31.8 GB 内存的强大游戏设备相比，简直不值一提。
但众所周知，32 位（32-bit）才是计算机领域的终极目标，也是我们解决所有实际工程和科学问题所需的最终位宽。毕竟，在 IPv4 因所谓的 "地址耗尽 "而被认为过时 60 年后，它如今仍然很强大。所以，让我们来看看最终的规模：32 位的数字是 16 位的 65536 倍，这会有什么问题吗？
print(" uint32_t number = atoi(argv[1]); // No problems here")
…
for i in range(2**32):
于是，我让强大的 Python 开始它的工作。48 小时后，我喝了一杯咖啡，然后回来检查程序，就得到了一个美丽的 c 文件，大小接近 330 GB！我几乎可以肯定，这是历史上最大的 c 文件之一。当我输入下一条命令时，我的手指都在颤抖，我猜 MSVC 肯定从未遇到如此强大的源代码。
在我那台可怜而强大的电脑页面文件中遭受半小时的折磨后，输出如下：
PS > cl /Od program.c
Microsoft (R) C/C++ Optimizing Compiler Version 19.32.31329 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

program.c
program.c(134397076): warning C4049: compiler limit: terminating line number emission
program.c(134397076): note: Compiler limit for line number is 16777215
program.c(41133672): fatal error C1060: compiler is out of heap space
太令人失望了！不仅编译器让我失望，在研究 Windows 可移植可执行文件格式（.exe）的限制时，我发现它无法处理超过 4GB 的文件！由于需要将 40 多亿次比较语句编码到可执行文件中，这对于实现我们的算法是一个主要障碍。即使每次比较时使用的字节数少于一个，对我来说工作量也太大了。
不过，糟糕的编译器和文件格式不应该阻止我们实现梦想。毕竟，编译器所做的只是将一些花哨的机器代码写入文件，而文件格式只是一些结构，告诉操作系统如何将二进制代码放入内存——其实，我们自己就能做到。

sxosmui3bor640106052232.png

解决最后一个问题，程序性能很不错
让我们先用 x86-64 汇编语言编写一个 IsEven 函数，因为这是我 Intel 处理器驱动的本地语言，它看起来是这样的：
; Argument is stored in ECX, return value in EAX
XOR EAX, EAX ; Set eax to zero (return value for odd number)
CMP ECX, 0h ; Compare arg to 0
JNE 3h ; Skip next two instructions if it wasn't equal
INC EAX ; It was even, set even return value (1)
RET ; Return
CMP ECX, 1h ; Compare arg to 1
JNE 2 ; Skip next instruction if not equal
RET ; Odd return value already in EAX, just RET
; add the next 2...2^32-1 comparisons here
RET ; Fallback return
这并不是真正正确的汇编代码，但这不重要，因为我们要手动将其编译成机器代码。
你问我是怎么做到的？我上网查阅了x86(-64) 体系结构手册，还利用我早年编写仿真器和黑客经验，找出了每条指令的正确操作码和格式……开个玩笑，这是不可能的。实际上，我是直接问 ChatGPT 每条指令的正确操作码是什么，幸运的是，它也没有产生 x86-64 的任何新扩展。
所以现在我们只需编写一个“编译器”来输出这段代码。请注意，我们将直接使用从 AI 获取的指令操作码，下面是用 Python 编写的代码：
import struct
with open('isEven.bin', 'wb') as file:
file.write(b"1à")                   # XOR EAX, EAX

for i in range(2**32):
      ib = struct.pack("[I], i)             # Encode i as 32 bit little endian integer

      file.write(b"?ù" + ib)          # CMP ECX, i

      if i%2 == 0:
         file.write(b"u")          # JNE +3
         file.write(b"?à")          # INC EAX
         file.write(b"?")                # RET
      else:
         file.write(b"u")          # JNE +1
         file.write(b"?")                # RET

file.write(b"?")                      # Fallback RET
虽然我们在一定程度上偏离了开头 TikTok 帖子的最初构想，但本质并没有改变：我们创建了一个非常长的 if 语句列表，用于确定某个数字是奇数还是偶数，并忽略了任何有助于简化问题的算术运算。
运行这个程序后，我们就得到了一个 40GB 的文件，其中包含了确定 32 位数字是偶数还是奇数所需的全部 42 亿次比较！现在，我们只需编写能够加载和使用这些指令的主程序。为了提高性能（这一点非常重要），我决定将文件映射到地址空间，而非一次性读取全部文件。这样，我们就可以假装整个文件已经在内存中，让可怜的操作系统来处理将一个 40GB 的 Blob 装入虚拟内存的问题。用 READ 和 EXECUTE 权限映射文件后，我们就可以使用函数指针调用代码了，代码如下：
#include
#include
#include

int main(int argc, char* argv[])
{
uint32_t number = atoi(argv[1]); // No problems here

// Open code file
HANDLE binFile = CreateFileA(
                     "isEven.bin",
                     GENERIC_READ | GENERIC_EXECUTE, FILE_SHARE_READ,
                     NULL,
                     OPEN_EXISTING,
                     FILE_ATTRIBUTE_NORMAL,
                     NULL);
// Get 64 bit size of file
LARGE_INTEGER codeSize;
GetFileSizeEx(binFile, &codeSize);

// Create memory map of the file
HANDLE mapping = CreateFileMapping(
                     binFile,
                     NULL,
                     PAGE_EXECUTE_READ,
                     0,
                     0,
                     NULL);

// Get a pointer to the code
LPVOID code = MapViewOfFile(
                  mapping,FILE_MAP_EXECUTE | FILE_MAP_READ,
                  0,
                  0,
                  codeSize.QuadPart);

// Create a function that points to the code
int (*isEven)(int) = (int(*)(int))code;

if (isEven(number))
      printf("even
");
else
      printf("odd
");

CloseHandle(binFile);
}
就是这样！现在我们已经具备了判断任何 32 位（32-bit）数字是奇是偶的所有功能，让我们试一试：
PS >.\program.exe 300
even
PS >.\program.exe 0
even
PS >.\program.exe 1000000
even
PS >.\program.exe 100000007
odd
PS >.\program.exe 400000000
even
PS >.\program.exe 400000001
odd
PS >.\program.exe 400000006
even
PS >.\program.exe 4200000000
odd 差不多了！似乎算法在符号性方面有问题，任何超过 2^31 的值似乎都会给出随机结果。那么，让我们来修复最后一个错误：原来 atoi 不能处理无符号性，所以它无法解析大数字。用 strtoul 代替它就能解决所有问题。
uint32_t number = strtoul(argv[1], NULL, 10);// No problems here
PS >.\program.exe 4200000000
even
PS >.\program.exe 4200000001
odd顺便提一句，这个程序的性能很不错。对于小数字，结果能即时返回，而对于接近 2^32 极限的大数字，结果仍能在大约 10 秒内返回。考虑到计算机必须从磁盘读取 40GB 的数据，将其映射到物理内存，然后让 CPU 在没有缓存的情况下对其进行处理，老实说这个速度已经相当令人惊叹了。作为参考，我电脑的配置为 Core i5 12600K，32GB 内存，文件存储在 M.2 SSD 硬盘上。在计算过程中，我看到 SSD 硬盘的峰值读取速度约为 800 MB/s。
至此，互联网再次被证明是错误的：你不仅可以按照 TikTok 帖子的方式编写一个功能齐全、性能良好的程序，而且还非常有趣。

153x1nda3eq640106052332.png

网友：没必要，一个简单的 for 循环就能解决
不过 Andreas Karlsson 的分享，并没有得到部分开发者的认可，甚至认为他有些“哗众取宠”：
“在我看来，这几乎是过度设计。为什么要费尽心思生成代码？只需一个简单的‘for 循环’就能解决。”
func isOdd(n int) bool {
var odd bool
for i := 0; i return odd
  }

“真正高质量的运行应始终使用递归。”
func isOdd(n int) bool {
switch {
case n == 0:
   return false
case n > 0:
   return !isOdd(n-1)
default:
   return !isOdd(n+1)
}
  }
还有人指出：“我完全听不懂这个笑话。我们从中学到了什么？exe 文件不能超过4GB？一个2^32 if 的程序大约是300GB？这看起来并不疯狂，只是毫无意义。”
对此，有人反驳道：“可笑的是，他真的做到了。几十年来，人们一直在拿它开玩笑，但这个人是认真的。由于代码多得太极端，没有编译器可以处理，甚至没有任何已知的汇编程序，因此他必须生成自己的机器码二进制文件才能运行。结果最后，他居然还真的成功了。”
参考链接：
https://andreasjhkarlsson.github.io/jekyll/update/2023/12/27/4-billion-if-statements.html
https://news.ycombinator.com/item?id=38790597
使用函数指针可以帮助我们编写更加灵活和通用的代码，并提高代码的可重用性和可扩展性。
?版权声明：本文来源网络，免费传达知识，版权归原作者所有。如涉及作品版权问题，请联系我进行删除。——EOF——你好，我是飞宇，本硕均于某中流985 CS就读，先后于百度搜索以及字节跳动电商等部门担任Linux C/C++后端研发工程师。
最近跟朋友一起开发了一个新的网站：编程资源网，已经收录了不少资源（附赠下载地址），如果屏幕前的靓仔/女想要学习编程找不到合适资源的话，不妨来我们的网站看看，欢迎扫码下方二维码白嫖~

5540en5towj640106052434.gif

同时，我也是知乎博主@韩飞宇，日常分享C/C++、计算机学习经验、工作体会，欢迎点击此处查看我以前的学习笔记&经验&分享的资源。
我组建了一些社群一起交流，群里有大牛也有小白，如果你有意可以一起进群交流。

mhzl0i1wv3o640106052534.png

欢迎你添加我的微信，我拉你进技术交流群。此外，我也会经常在微信上分享一些计算机学习经验以及工作体验，还有一些内推机会。

04h1jnkv4ir640106052634.png

加个微信，打开另一扇窗

afrslusxa5q640106052734.gif