“用 40 亿条 if 语句,只为判断一个数字是奇是偶?”

编译 | 郑丽媛
出品 | CSDN(ID:CSDNnews)

看到这个标题,相信大多数人的第一反应是:真的有人用 40 亿条 if 语句,只为判断一个数字是奇数还是偶数?的确有,这个开发者名为 Andreas Karlsson,他还把整个过程都整理成文了。

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

下为译文:

大于 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.cPS > .program.exe 0 evenPS > .program.exe 4evenPS > .program.exe 3oddPS > .program.exe 7odd

结果显示:0、4 是偶数,3、7 是奇数。这么看来,程序似乎运行得挺好,但在进一步测试后,我发现了一些问题:

PS > .program.exe 50PS > .program.exe 11PS > .program.exe 99

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

向 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("evenn");") else: print(" printf("oddn");")

print("}")

好了!现在我们可以生成一个程序,解决所有 8 位(8-bit)整数的奇偶问题!

PS > python programmer.py > program.cPS > cl.exe /Od program.cPS > .program.exe 99oddPS > .program.exe 50evenPS > .program.exe 240evenPS > .program.exe 241odd

看看,这个效果简直完美!现在,让我们把它放大到 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.cPS > cl.exe /Od program.cPS > .program.exe 21000evenPS > .program.exe 3475 oddPS > .program.exe 3 oddPS > .program.exe 65001oddPS > .program.exe 65532even

太棒了,我们的算法似乎能够处理大量数据!可执行文件大约只有 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.cMicrosoft (R) C/C++ Optimizing Compiler Version 19.32.31329 for x64Copyright (C) Microsoft Corporation. All rights reserved.

program.cprogram.c(134397076): warning C4049: compiler limit: terminating line number emissionprogram.c(134397076): note: Compiler limit for line number is 16777215program.c(41133672): fatal error C1060: compiler is out of heap space

太令人失望了!不仅编译器让我失望,在研究 Windows 可移植可执行文件格式(.exe)的限制时,我发现它无法处理超过 4GB 的文件!由于需要将 40 多亿次比较语句编码到可执行文件中,这对于实现我们的算法是一个主要障碍。即使每次比较时使用的字节数少于一个,对我来说工作量也太大了。

不过,糟糕的编译器和文件格式不应该阻止我们实现梦想。毕竟,编译器所做的只是将一些花哨的机器代码写入文件,而文件格式只是一些结构,告诉操作系统如何将二进制代码放入内存——其实,我们自己就能做到。

解决最后一个问题,程序性能很不错

让我们先用 x86-64 汇编语言编写一个 IsEven 函数,因为这是我 Intel 处理器驱动的本地语言,它看起来是这样的:

; Argument is stored in ECX, return value in EAXXOR 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 equalINC EAX ; It was even, set even return value (1)RET ; ReturnCMP ECX, 1h ; Compare arg to 1JNE 2 ; Skip next instruction if not equalRET ; Odd return value already in EAX, just RET; add the next 2...2^32-1 comparisons hereRET ; 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("

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, , OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, );
// Get 64 bit size of file LARGE_INTEGER codeSize; GetFileSizeEx(binFile, &codeSize);

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

// 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 300evenPS >.program.exe 0evenPS >.program.exe 1000000evenPS >.program.exe 100000007oddPS >.program.exe 400000000evenPS >.program.exe 400000001oddPS >.program.exe 400000006evenPS >.program.exe 4200000000odd <---- WRONG!

差不多了!似乎算法在符号性方面有问题,任何超过 2^31 的值似乎都会给出随机结果。那么,让我们来修复最后一个错误:原来 atoi 不能处理无符号性,所以它无法解析大数字。用 strtoul 代替它就能解决所有问题。

uint32_t number = strtoul(argv[1], , 10);// No problems here
PS >.program.exe 4200000000evenPS >.program.exe 4200000001odd

顺便提一句,这个程序的性能很不错。对于小数字,结果能即时返回,而对于接近 2^32 极限的大数字,结果仍能在大约 10 秒内返回。考虑到计算机必须从磁盘读取 40GB 的数据,将其映射到物理内存,然后让 CPU 在没有缓存的情况下对其进行处理,老实说这个速度已经相当令人惊叹了。作为参考,我电脑的配置为 Core i5 12600K,32GB 内存,文件存储在 M.2 SSD 硬盘上。在计算过程中,我看到 SSD 硬盘的峰值读取速度约为 800 MB/s。

至此,互联网再次被证明是错误的:你不仅可以按照 TikTok 帖子的方式编写一个功能齐全、性能良好的程序,而且还非常有趣。

网友:没必要,一个简单的 for 循环就能解决

不过 Andreas Karlsson 的分享,并没有得到部分开发者的认可,甚至认为他有些“哗众取宠”:

func isOdd(n int) bool { var odd bool for i := 0; i < n; i++ { odd = !odd } 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


展开阅读全文

页面更新:2024-03-23

标签:语句   数字   奇数   偶数   编译器   算法   内存   代码   文件   程序

1 2 3 4 5

上滑加载更多 ↓
推荐阅读:
友情链接:
更多:

本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828  

© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号

Top