雯 發自 凹非寺

量子位 | 公眾號 QbitAI

取整求個無符號整數的平均值，居然也能整出花兒來？

這不，微軟大神Raymond Chen最近的一篇長文直接引爆外網技術平臺，引發無數討論：

無數人點進去時無比自信：不就是一個簡單的相加后除二的小學生編程題嗎？

unsigned average(unsigned a, unsigned b)
{
return (a + b) / 2;
}

但跟著大神的一路深挖，卻逐漸目瞪狗呆……

沒那么簡單的求平均值

先從開頭提到的小學生都會的方法看起，這個簡單的方法有個致命的缺陷：

如果無符號整數的長度為32位，那么如果兩個相加的值都為最大長度的一半，那么僅在第一步相加時，就會發生內存溢出。

也就是average（0x80000000U, 0x80000000U）=0。

不過解決方法也不少，大多數有經驗的開發者首先能想到的，就是預先限制相加的數字長度，避免溢出。

具體有兩種方法：

1、當知道相加的兩個無符號整數中的較大值時，減去較小值再除二，以提前減少長度：

unsigned average(unsigned low, unsigned high)
{
return low + (high - low) / 2;
}

2、對兩個無符號整數預先進行除法，同時通過按位與修正低位數字，保證在兩個整數都為奇數時，結果仍然正確。

（順帶一提，這是一個被申請了專利的方法，2016年過期）

unsigned average(unsigned a, unsigned b)
{
return (a / 2) + (b / 2) + (a & b & 1);
}

這兩個都是較為常見的思路，不少網友也表示，自己最快想到的就是2016年專利方法。

同樣能被廣大網友快速想到的方法還有SWAR（SIMD within a register）：

unsigned average(unsigned a, unsigned b)
{
return (a & b) + (a ^ b) / 2;// 變體 (a ^ b) + (a & b) * 2

以及C++ 20版本中的std: : midpoint函數。

接下來，作者提出了第二種思路：

如果無符號整數是32位而本機寄存器大小是64位，或者編譯器支持多字運算，就可以將相加值強制轉化為長整型數據。

unsigned average(unsigned a, unsigned b)
{
// Suppose "unsigned" is a 32-bit type and
// "unsigned long long" is a 64-bit type.
return ((unsigned long long)a + b) / 2;
}

不過，這里有一個需要特別注意的點：

必須要保證64位寄存器的前32位都為0，才不會影響剩余的32位值。

像是x86-64和aarch64這些架構會自動將32位值零擴展為64位值：

// x86-64: Assume ecx = a, edx = b, upper 32 bits unknown
mov eax, ecx ; rax = ecx zero-extended to 64-bit value
mov edx, edx ; rdx = edx zero-extended to 64-bit value
add rax, rdx ; 64-bit addition: rax = rax + rdx
shr rax, 1 ; 64-bit shift: rax = rax >> 1
; result is zero-extended
; Answer in eax

// AArch64 (ARM 64-bit): Assume w0 = a, w1 = b, upper 32 bits unknown
uxtw x0, w0 ; x0 = w0 zero-extended to 64-bit value
uxtw x1, w1 ; x1 = w1 zero-extended to 64-bit value
add x0, x1 ; 64-bit addition: x0 = x0 + x1
ubfx x0, x0, 1, 32 ; Extract bits 1 through 32 from result
; (shift + zero-extend in one instruction)
; Answer in x0

而Alpha AXP、mips64等架構則會將32位值符號擴展為64位值。

這種時候，就需要額外增加歸零的指令，比如通過向左進位兩字的刪除指令rldicl：

// Alpha AXP: Assume a0 = a, a1 = b, both in canonical form
insll a0, #0, a0 ; a0 = a0 zero-extended to 64-bit value
insll a1, #0, a1 ; a1 = a1 zero-extended to 64-bit value
addq a0, a1, v0 ; 64-bit addition: v0 = a0 + a1
srl v0, #1, v0 ; 64-bit shift: v0 = v0 >> 1
addl zero, v0, v0 ; Force canonical form
; Answer in v0

// MIPS64: Assume a0 = a, a1 = b, sign-extended
dext a0, a0, 0, 32 ; Zero-extend a0 to 64-bit value
dext a1, a1, 0, 32 ; Zero-extend a1 to 64-bit value
daddu v0, a0, a1 ; 64-bit addition: v0 = a0 + a1
dsrl v0, v0, #1 ; 64-bit shift: v0 = v0 >> 1
sll v0, #0, v0 ; Sign-extend result
; Answer in v0

// Power64: Assume r3 = a, r4 = b, zero-extended
add r3, r3, r4 ; 64-bit addition: r3 = r3 + r4
rldicl r3, r3, 63, 32 ; Extract bits 63 through 32 from result
; (shift + zero-extend in one instruction)
; result in r3

或者直接訪問比本機寄存器更大的SIMD寄存器，當然，從通用寄存器跨越到SIMD寄存器肯定也會增加內存消耗。

如果電腦的處理器支持進位加法，那么還可以采用第三種思路。

這時，如果寄存器大小為n位，那么兩個n位的無符號整數的和就可以理解為n+1位，通過RCR（帶進位循環右移）指令，就可以得到正確的平均值，且不損失溢出的位。

// x86-32
mov eax, a
add eax, b ; Add, overflow goes into carry bit
rcr eax, 1 ; Rotate right one place through carry

// x86-64
mov rax, a
add rax, b ; Add, overflow goes into carry bit
rcr rax, 1 ; Rotate right one place through carry

// 32-bit ARM (A32)
mov r0, a
adds r0, b ; Add, overflow goes into carry bit
rrx r0 ; Rotate right one place through carry

// SH-3
clrt ; Clear T flag
mov a, r0
addc b, r0 ; r0 = r0 + b + T, overflow goes into T bit
rotcr r0 ; Rotate right one place through carry

那如果處理器不支持帶進位循環右移操作呢？

也可以使用內循環（rotation intrinsic）：

unsigned average(unsigned a, unsigned b)
{
#if defined(_MSC_VER)
unsigned sum;
auto carry = _addcarry_u32(0, a, b, &sum);
sum = (sum & ~1) | carry;
return _rotr(sum, 1);
#elif defined(__clang__)
unsigned carry;
sum = (sum & ~1) | carry;
auto sum = __builtin_addc(a, b, 0, &carry);
return __builtin_rotateright32(sum, 1);
#else
#error Unsupported compiler.
#endif
}

結果是，x86架構下的代碼生成沒有發生什么變化，MSCver架構下的代碼生成變得更糟，而arm-thumb2的clang 的代碼生成更好了。

// _MSC_VER
mov ecx, a
add ecx, b ; Add, overflow goes into carry bit
setc al ; al = 1 if carry set
and ecx, -2 ; Clear bottom bit
movzx ecx, al ; Zero-extend byte to 32-bit value
or eax, ecx ; Combine
ror ear, 1 ; Rotate right one position
; Result in eax

// __clang__
mov ecx, a
add ecx, b ; Add, overflow goes into carry bit
setc al ; al = 1 if carry set
shld eax, ecx, 31 ; Shift left 64-bit value

// __clang__ with ARM-Thumb2
movs r2, #0 ; Prepare to receive carry
adds r0, r0, r1 ; Calculate sum with flags
adcs r2, r2 ; r2 holds carry
lsrs r0, r0, #1 ; Shift sum right one position
lsls r1, r2, #31 ; Move carry to bit 31
adds r0, r1, r0 ; Combine

微軟大神的思考們

Raymond Chen1992年加入微軟，迄今為止已任職25年，做UEX-Shell，也參與Windows開發，Windows系統的很多最初UI架構就是他搞起來的。

他在MSDN 上建立的blogThe Old New Thing也是業內非常出名的純技術向產出網站。

這篇博客的評論區們也是微軟的各路大神出沒，繼續深入探討。

有人提出了新方法，在MIPS ASM共有36個循環：

unsigned avg(unsigned a, unsigned b
{
return (a & b) + (a ^ b) / 2;
}

// lw $3,8($fp) # 5
// lw $2,12($fp) # 5
// and $3,$3,$2 # 4
// lw $4,8($fp) # 5
// lw $2,12($fp) # 5
// xor $2,$4,$2 # 4
// srl $2,$2,1 # 4
// addu $2,$3,$2 # 4

有人針對2016年專利法表示，與其用(a / 2) + (b / 2) + (a & b & 1)的方法，為啥不直接把 (a & 1) & ( b & 1 ) ) 作為進位放入加法器中計算呢？

還有人在評論區推薦了TopSpeed編譯器，能夠通過指定合適的代碼字節和調用約定來定義一個內聯函數，以解決“乘除結果是16位，中間計算值卻不是”的情況。

只能說，學無止境啊。

原文：
https://devblogs.microsoft.com/oldnewthing/20220207-00/?p=106223

參考鏈接：
https://news.ycombinator.com/item?id=30252263

誰還沒個獨占呢？

前段時間，微軟Excel官方發布了新一屆金融建模世界杯的比賽預告。尤其令人在意的是，他們特意宣稱這次比賽將是“一場電競賽事”。

金融建模世界杯（FMWC）是一個金融建模界的新興賽事，參賽者都是行業頂尖的金融建模師，通過Excel比拼建模實力來決出高下。在過去的幾個月中，這個比賽已經借鑒了許多競技體育的框架：嚴格劃分的賽季、積分制的世界排名以及分門別類的賽事體系。不過正式打出“電競”的招牌，這還是第一次。

抱著門外漢看熱鬧的心情，··比賽當天我準時點開了直播鏈接的地址，想看看這場金融界的電競賽事究竟能玩出怎樣的花樣。但比賽開始10分鐘后，我就后悔了。

這場金融建模世界杯的比賽，比我想象得還要更無趣。八位受邀參賽的建模師，在比賽中有40分鐘來解決賽事方提供的案例題目，最后分數最高者獲得冠軍。

原以為這場8人混戰的比賽能有一些更具觀賞性的形式，來調劑沉悶的比賽本身，但很可惜并沒有。組織者最后采用的方式，最公平、最能體現選手實力，但同時也最無聊。

直播間里和我一樣沖著“電競”名號去看的人不少，不時就有人詢問“競技的部分呢？”，但回答他們的大都只是抖機靈的話：“（e-Sports指的是）eXCEL-Sports”。

這場羊頭招牌狗肉攤上的“電競賽事”，似乎用事實給我們展示了Excel這款軟件和電競、游戲間的遙遠距離，但事實真是這樣嗎？

1

在我們普通人眼中，Excel這個微軟Office全家桶中的一員，似乎就只是一個用來建表格的專職軟件，功能垂直且單一。而在真正精通者的手中，要用它制作一款游戲其實并沒有多少技術上的鴻溝——它就是隱藏在我們每一臺PC上的“青春版”游戲引擎。

能成為游戲制作工具，Excel強大的圖形處理能力功不可沒。這一個個能隨意調整的方格，天然就是一張像素畫畫布。

格子間出沒的社畜們應該或多或少都和Excel纏斗過，或許無聊時會偶爾給格子填填色、畫點什么寫點什么。而對于更專業的像素畫師來說，即使現在有越來越多更全面、更專業的像素畫軟件誕生，但Excel依然是一款好用的像素畫工具，仍被他們中的許多人當作生產力工具在使用。

除了最直觀的像素畫之外，Excel還靠著“插入任意多邊形”和“3D圖形繪制”這兩個強大的功能，同樣具備了拓展其他繪圖領域的潛力。

不管是日漫風格的立繪圖，擬真風格的風景畫，還是3D建模的真實系繪畫，都在它的射程范圍內。再加上對Flash動畫的插入支持，一款游戲引擎的圖形功能它也就被它掌握得七七八八了。

Excel的圖形能力固然強大，而真正能讓它與游戲引擎一比的，還是它背后對編程語言的支持。

VBA（Visual Basic for Applications）是Excel全面支持的一種編程語言，準確來說它是基于VB語言的宏語言，原本是微軟開發用來實現辦公自動化服務的。從名字中的“Visual”也能看出，可視化是這個語言的重要特點，它誕生的一大標準就是“簡單”,不用太多編程基礎就能輕松上手。

因此可能你并沒有在“誰是天下第一語言”的爭論中聽過它的名字，但使用它的人群其實并不算少。遠遠比不上屠龍之技，但酷暑時節學來打打蚊子絕對夠用。

可以直接在Excel中處理代碼，邏輯、數據和圖形就能輕松綁定到一起，這些圖形變成游戲的最后一步也就得以實現。簡單地使用VBA和圖形功能，已經足夠制作出許多游戲的雛形。而對于更精通的高手來說，通過插件實現更多功能，讓它變成一個功能齊全的游戲引擎也完全能做到。

Excel擁有如此接近游戲引擎的功能，發現的人自然不會少，好在其中除了有我這樣的空想家外還有不少實踐者，才誕生了眾多“Excel平臺獨占游戲”。

2

說起“Excel平臺獨占游戲”，可能許多人早就聽說過其中一款。這個游戲不是由用戶開發，而是一個能稱為“Excel2000的護航大作”的彩蛋——一個通過“作弊秘籍”呼出的Excel賽車游戲。

在Excel2000中，通過把新建表格另存發布為Web頁、勾選交互選項并保存、通過IE瀏覽器打開文件并點擊第2000行第WC列的那一格，最后同時按住Ctrl、Alt、Shift按鈕再點擊Office圖標，就能成功呼出游戲。

在短暫的全屏切換后，進入到這個彩蛋游戲中的玩家可以在一條公路上漫無目的地駕駛汽車，能撞擊其他汽車也能放出油漬來干擾它們。如果在游戲中留心觀察，還會發現公路上寫著的單詞是一個個名字，他們正是這一版Excel的幕后開發者。

在此前發布的Excel95和Excel97中，也分別有兩個藏有開發者名單的彩蛋，而直到這一作才第一次以游戲的形式展現出來，就此成為了許多人小時候計算機課上的回憶。

這些用游戲來刻下自己姓名的開發者，或許自己也不曾想到，他們這款辦公軟件的游戲之路并沒有就此結束，反而在之后成為了許多開發者的一大選擇，甚至成為了諸多經典作品的“移植平臺”。

如果沒有游戲源代碼，那么復刻一款游戲的難度就取決于它的規則復雜程度。諸如《Monopoly》《數獨》等邏輯性強表現力弱的游戲，自然成了Excel游戲的移植首選。同時因為Excel辦公軟件身份的隱蔽性，摸魚黨想要劃水的需求也成為了開發的動力，讓這類游戲在Excel上的版本格外多。

許多經典主機老游戲的邏輯雖然更復雜，但在情懷的推動下這點難度自然算不了什么，也讓它們也成為了Excel平臺移植的常客。于是《塞爾達傳說》《超級馬力歐兄弟2》《文明》《勇者斗惡龍》等游戲紛紛登陸，都有著完成度很高的Excel版本。

既然這么多成熟的游戲都在Excel上證明了它作為引擎的可能性，懷著原創熱情的開發者自然也不會缺席，《Arena.Xlsm》就是其中知名度最高的作品之一。從它標題的后綴就能看出，這是一款專為Excel打造的獨立游戲。

這款游戲是一個俯視角的傳統RPG，畫面比較粗糙，但玩法設計卻很細致。根據作者主頁的介紹，游戲有著超過2000種不同AI的敵人、31種法術、39種道具模型、8場不同的BOSS戰和4個不同的故事結局，聽起來已經相當豐富。更讓人沒想到的是，游戲內還有積分排行榜功能和100個不同的成就，而這些全都是在Excel中實現的。

《Arena.Xlsm》最初開發于2012年，在這么多年后的WIN10系統里，依然能完美運行它。只要正常安裝了Excel的宏功能，就能在Excel 2007以上的版本上開始游戲。

游戲實機上手非常流暢，只是偶爾會有“卡頓”這個Excel游戲共有的通病。角色的加點升級、豐富的道具和技能、以及時不時插入的劇情介紹，都讓游戲具有不低的可玩性。

如果它簡陋的符號化美術風格能獲得升級，相信能感受到它獨有魅力的人會更多，但可惜這款游戲的開發者Cary Walkin并不擅長美術，因此他把游戲系統完善升級到1.3版本后就停止了更新。

Cary Walkin是一名加拿大的注冊會計師，開發這款游戲時他正在攻讀自己的MBA學位。因為自己是一名《EVE》玩家，游戲時也經常會使用Excel來輔助游戲，所以他在一門相關課程的練習中突然想到：與其建立乏味的期權模型，不如用Excel來制作一款復雜的游戲，也能達到同樣的練習效果。

就這樣，《Arena.Xlsm》誕生了。據Cary Walkin的個人主頁統計，至今已有超過60萬人次下載游玩過這個游戲。

“我對電子游戲有著熱情，任何游戲相關的東西都比稅務要好”，Cary Walkin曾在采訪中作為游戲開發者這樣說。

3

距離Cary Walkin說出這句話已經過去了8年，如今“對游戲更有熱情”的他，還是選擇成為了一名金融從業者。

完成《Arena.Xlsm》的第二年，他又在Excel上制作了一款扮演《糖果傳奇》開發商的模擬經營游戲，游戲反響不錯但卻沒能再獲得前作那么高的關注度，他的游戲從業經歷也就此停在了這一年。

用Excel開發游戲，終究是一件吃力不討好的事。國內曾有一款《Excel三國殺》風靡一時，不過在獲得足夠知名度后，開發者們還是選擇了離開這個平臺，盡管它們此后的游戲標題中仍然含有“Excel”字樣。

畢竟Excel不是專業的游戲開發引擎，辦公軟件的框架限制給開發和游玩都帶來了很多不便。選擇更好的平臺、開發更好的游戲，這本就是無可厚非的事。但就算這樣，也依然有人沒做出這個選擇。

在B站有一個ID為“hongyunggg”的UP主，從2018年開始就在嘗試用Excel制作《王者榮耀》。他的視頻點擊量從沒突破過100，游戲做得也遠不如上面提到的那些高手作品。

不過從2018年12月29日的第一個視頻開始，他就在周期性地不斷更新他的游戲版本視頻，很明顯能感受到他游戲質量的提升，不管是圖形畫面，角色技能、AI、界面，還是音效動效等細枝末節處。

直到今年5月底，他依然在視頻下方回復著觀眾的相關技術問題，相信現在他還在繼續著這個項目，即使這份努力并沒有得到太多人的認可。

跟hongyunggg一樣的無名作者我相信還有很多，他們能一直堅持，追求的應該不只有那份他人的認可——愛好從來不是為了取悅他人。別人眼中的“沒意義”能照亮自己的一方小世界就夠了，這也是有這么多“Excel獨占游戲”誕生的原因。

成不了游戲引擎的Excel背后，應該也會一直站有這群，不一定能成功的Excel游戲制作者。

參考資料：

https://carywalkin.ca/

https://en.wikipedia.org/wiki/Visual_Basic

https://www.wikihow.com/Play-a-Car-Race-in-Excel-2000