如何取整求個(gè)無(wú)符號(hào)整數(shù)的平均值

取整求個(gè)無(wú)符號(hào)整數(shù)的平均值，居然也能整出花兒來(lái)？

這不，微軟大神Raymond Chen最近的一篇長(zhǎng)文直接引爆外網(wǎng)技術(shù)平臺(tái)，引發(fā)無(wú)數(shù)討論：

無(wú)數(shù)人點(diǎn)進(jìn)去時(shí)無(wú)比自信：不就是一個(gè)簡(jiǎn)單的相加后除二的小學(xué)生編程題嗎？

unsignedaverage(unsigneda,unsignedb)
{
return(a+b)/2;
}

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

沒(méi)那么簡(jiǎn)單的求平均值

先從開(kāi)頭提到的小學(xué)生都會(huì)的方法看起，這個(gè)簡(jiǎn)單的方法有個(gè)致命的缺陷：

如果無(wú)符號(hào)整數(shù)的長(zhǎng)度為32位，那么如果兩個(gè)相加的值都為最大長(zhǎng)度的一半，那么僅在第一步相加時(shí)，就會(huì)發(fā)生內(nèi)存溢出。

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

不過(guò)解決方法也不少，大多數(shù)有經(jīng)驗(yàn)的開(kāi)發(fā)者首先能想到的，就是預(yù)先限制相加的數(shù)字長(zhǎng)度，避免溢出。

具體有兩種方法：

1、當(dāng)知道相加的兩個(gè)無(wú)符號(hào)整數(shù)中的較大值時(shí)，減去較小值再除二，以提前減少長(zhǎng)度：

unsignedaverage(unsignedlow,unsignedhigh)
{
returnlow+(high-low)/2;
}

2、對(duì)兩個(gè)無(wú)符號(hào)整數(shù)預(yù)先進(jìn)行除法，同時(shí)通過(guò)按位與修正低位數(shù)字，保證在兩個(gè)整數(shù)都為奇數(shù)時(shí)，結(jié)果仍然正確。

（順帶一提，這是一個(gè)被申請(qǐng)了專利的方法，2016年過(guò)期）

unsignedaverage(unsigneda,unsignedb)
{
return(a/2)+(b/2)+(a&b&1);
}

這兩個(gè)都是較為常見(jiàn)的思路，不少網(wǎng)友也表示，自己最快想到的就是2016年專利方法。

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

unsignedaverage(unsigneda,unsignedb)
{
return(a&b)+(a^b)/2;//變體(a^b)+(a&b)*2

以及C++ 20版本中的std: : midpoint函數(shù)。

接下來(lái)，作者提出了第二種思路：

如果無(wú)符號(hào)整數(shù)是32位而本機(jī)寄存器大小是64位，或者編譯器支持多字運(yùn)算，就可以將相加值強(qiáng)制轉(zhuǎn)化為長(zhǎng)整型數(shù)據(jù)。

unsignedaverage(unsigneda,unsignedb)
{
//Suppose"unsigned"isa32-bittypeand
//"unsignedlonglong"isa64-bittype.
return((unsignedlonglong)a+b)/2;
}

不過(guò)，這里有一個(gè)需要特別注意的點(diǎn)：

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

像是x86-64和aarch64這些架構(gòu)會(huì)自動(dòng)將32位值零擴(kuò)展為64位值：

//x86-64:Assumeecx=a,edx=b,upper32bitsunknown
moveax,ecx;rax=ecxzero-extendedto64-bitvalue
movedx,edx;rdx=edxzero-extendedto64-bitvalue
addrax,rdx;64-bitaddition:rax=rax+rdx
shrrax,1;64-bitshift:rax=rax>>1
;resultiszero-extended
;Answerineax

//AArch64(ARM64-bit):Assumew0=a,w1=b,upper32bitsunknown
uxtwx0,w0;x0=w0zero-extendedto64-bitvalue
uxtwx1,w1;x1=w1zero-extendedto64-bitvalue
addx0,x1;64-bitaddition:x0=x0+x1
ubfxx0,x0,1,32;Extractbits1through32fromresult
;(shift+zero-extendinoneinstruction)
;Answerinx0

而Alpha AXP、mips64等架構(gòu)則會(huì)將32位值符號(hào)擴(kuò)展為64位值。

這種時(shí)候，就需要額外增加歸零的指令，比如通過(guò)向左進(jìn)位兩字的刪除指令rldicl：

//AlphaAXP:Assumea0=a,a1=b,bothincanonicalform
inslla0,#0,a0;a0=a0zero-extendedto64-bitvalue
inslla1,#0,a1;a1=a1zero-extendedto64-bitvalue
addqa0,a1,v0;64-bitaddition:v0=a0+a1
srlv0,#1,v0;64-bitshift:v0=v0>>1
addlzero,v0,v0;Forcecanonicalform
;Answerinv0

//MIPS64:Assumea0=a,a1=b,sign-extended
dexta0,a0,0,32;Zero-extenda0to64-bitvalue
dexta1,a1,0,32;Zero-extenda1to64-bitvalue
dadduv0,a0,a1;64-bitaddition:v0=a0+a1
dsrlv0,v0,#1;64-bitshift:v0=v0>>1
sllv0,#0,v0;Sign-extendresult
;Answerinv0

//Power64:Assumer3=a,r4=b,zero-extended
addr3,r3,r4;64-bitaddition:r3=r3+r4
rldiclr3,r3,63,32;Extractbits63through32fromresult
;(shift+zero-extendinoneinstruction)
;resultinr3

或者直接訪問(wèn)比本機(jī)寄存器更大的SIMD寄存器，當(dāng)然，從通用寄存器跨越到SIMD寄存器肯定也會(huì)增加內(nèi)存消耗。

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

這時(shí)，如果寄存器大小為n位，那么兩個(gè)n位的無(wú)符號(hào)整數(shù)的和就可以理解為n+1位，通過(guò)RCR（帶進(jìn)位循環(huán)右移）指令，就可以得到正確的平均值，且不損失溢出的位。

△帶進(jìn)位循環(huán)右移

//x86-32
moveax,a
addeax,b;Add,overflowgoesintocarrybit
rcreax,1;Rotaterightoneplacethroughcarry

//x86-64
movrax,a
addrax,b;Add,overflowgoesintocarrybit
rcrrax,1;Rotaterightoneplacethroughcarry

//32-bitARM(A32)
movr0,a
addsr0,b;Add,overflowgoesintocarrybit
rrxr0;Rotaterightoneplacethroughcarry

//SH-3
clrt;ClearTflag
mova,r0
addcb,r0;r0=r0+b+T,overflowgoesintoTbit
rotcrr0;Rotaterightoneplacethroughcarry

那如果處理器不支持帶進(jìn)位循環(huán)右移操作呢？

也可以使用內(nèi)循環(huán)（rotation intrinsic）：

unsignedaverage(unsigneda,unsignedb)
{
#ifdefined(_MSC_VER)
unsignedsum;
autocarry=_addcarry_u32(0,a,b,&sum);
sum=(sum&~1)|carry;
return_rotr(sum,1);
#elifdefined(__clang__)
unsignedcarry;
sum=(sum&~1)|carry;
autosum=__builtin_addc(a,b,0,&carry);
return__builtin_rotateright32(sum,1);
#else
#errorUnsupportedcompiler.
#endif
}

結(jié)果是，x86架構(gòu)下的代碼生成沒(méi)有發(fā)生什么變化，MSCver架構(gòu)下的代碼生成變得更糟，而arm-thumb2的clang 的代碼生成更好了。

//_MSC_VER
movecx,a
addecx,b;Add,overflowgoesintocarrybit
setcal;al=1ifcarryset
andecx,-2;Clearbottombit
movzxecx,al;Zero-extendbyteto32-bitvalue
oreax,ecx;Combine
rorear,1;Rotaterightoneposition
;Resultineax

//__clang__
movecx,a
addecx,b;Add,overflowgoesintocarrybit
setcal;al=1ifcarryset
shldeax,ecx,31;Shiftleft64-bitvalue

//__clang__withARM-Thumb2
movsr2,#0;Preparetoreceivecarry
addsr0,r0,r1;Calculatesumwithflags
adcsr2,r2;r2holdscarry
lsrsr0,r0,#1;Shiftsumrightoneposition
lslsr1,r2,#31;Movecarrytobit31
addsr0,r1,r0;Combine

微軟大神的思考們

Raymond Chen1992年加入微軟，迄今為止已任職25年，做UEX-Shell，也參與Windows開(kāi)發(fā)，Windows系統(tǒng)的很多最初UI架構(gòu)就是他搞起來(lái)的。

他在MSDN 上建立的blogThe Old New Thing也是業(yè)內(nèi)非常出名的純技術(shù)向產(chǎn)出網(wǎng)站。

這篇博客的評(píng)論區(qū)們也是微軟的各路大神出沒(méi)，繼續(xù)深入探討。

有人提出了新方法，在MIPS ASM共有36個(gè)循環(huán)：

unsignedavg(unsigneda,unsignedb)
{
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

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

還有人在評(píng)論區(qū)推薦了TopSpeed編譯器，能夠通過(guò)指定合適的代碼字節(jié)和調(diào)用約定來(lái)定義一個(gè)內(nèi)聯(lián)函數(shù)，以解決“乘除結(jié)果是16位，中間計(jì)算值卻不是”的情況。

只能說(shuō)，學(xué)無(wú)止境啊。