如何取整求个无符号整数的平均值
取整求个无符号整数的平均值，居然也能整出花儿来？
这不，微软大神Raymond Chen最近的一篇长文直接引爆外网技术平台，引发无数讨论：
无数人点进去时无比自信：不就是一个简单的相加后除二的小学生编程题吗？
unsignedaverage(unsigneda,unsignedb)
{
return(a+b)/2;
}
但跟着大神的一路深挖，却逐渐目瞪狗呆……
没那么简单的求平均值
先从开头提到的小学生都会的方法看起，这个简单的方法有个致命的缺陷：
如果无符号整数的长度为32位，那么如果两个相加的值都为最大长度的一半，那么仅在第一步相加时，就会发生内存溢出。
也就是average（0x80000000U, 0x80000000U）=0。
不过解决方法也不少，大多数有经验的开发者首先能想到的，就是预先限制相加的数字长度，避免溢出。
具体有两种方法：
1、当知道相加的两个无符号整数中的较大值时，减去较小值再除二，以提前减少长度：
unsignedaverage(unsignedlow,unsignedhigh)
{
returnlow+(high-low)/2;
}
2、对两个无符号整数预先进行除法，同时通过按位与修正低位数字，保证在两个整数都为奇数时，结果仍然正确。
（顺带一提，这是一个被申请了专利的方法，2016年过期）
unsignedaverage(unsigneda,unsignedb)
{
return(a/2)+(b/2)+(a&b&1);
}
这两个都是较为常见的思路，不少网友也表示，自己最快想到的就是2016年专利方法。
同样能被广大网友快速想到的方法还有SWAR（SIMD within a register）：
unsignedaverage(unsigneda,unsignedb)
{
return(a&b)+(a^b)/2;//变体(a^b)+(a&b)*2
以及C++ 20版本中的std: : midpoint函数。
接下来，作者提出了第二种思路：
如果无符号整数是32位而本机寄存器大小是64位，或者编译器支持多字运算，就可以将相加值强制转化为长整型数据。
unsignedaverage(unsigneda,unsignedb)
{
//Suppose"unsigned"isa32-bittypeand
//"unsignedlonglong"isa64-bittype.
return((unsignedlonglong)a+b)/2;
}
不过，这里有一个需要特别注意的点：
必须要保证64位寄存器的前32位都为0，才不会影响剩余的32位值。
像是x86-64和aarch64这些架构会自动将32位值零扩展为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等架构则会将32位值符号扩展为64位值。
这种时候，就需要额外增加归零的指令，比如通过向左进位两字的删除指令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
或者直接访问比本机寄存器更大的SIMD寄存器，当然，从通用寄存器跨越到SIMD寄存器肯定也会增加内存消耗。
这时，如果寄存器大小为n位，那么两个n位的无符号整数的和就可以理解为n+1位，通过RCR（带进位循环右移）指令，就可以得到正确的平均值，且不损失溢出的位。
△带进位循环右移
//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
那如果处理器不支持带进位循环右移操作呢？
也可以使用内循环（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
}
结果是，x86架构下的代码生成没有发生什么变化，MSCver架构下的代码生成变得更糟，而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开发，Windows系统的很多最初UI架构就是他搞起来的。
他在MSDN 上建立的blogThe Old New Thing也是业内非常出名的纯技术向产出网站。
这篇博客的评论区们也是微软的各路大神出没，继续深入探讨。
有人提出了新方法，在MIPS ASM共有36个循环：
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
有人针对2016年专利法表示，与其用(a / 2) + (b / 2) + (a & b & 1)的方法，为啥不直接把 (a & 1) & ( b & 1 ) ) 作为进位放入加法器中计算呢？
还有人在评论区推荐了TopSpeed编译器，能够通过指定合适的代码字节和调用约定来定义一个内联函数，以解决“乘除结果是16位，中间计算值却不是”的情况。
只能说，学无止境啊。
原文标题：看完微软大神写的求平均值代码，我意识到自己还是too young了
文章出处：【微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。
审核编辑：汤梓红
-
微软
+关注
关注
4文章
6590浏览量
104024 -
寄存器
+关注
关注
31文章
5336浏览量
120230 -
编程
+关注
关注
88文章
3614浏览量
93685
原文标题：看完微软大神写的求平均值代码，我意识到自己还是too young了
文章出处：【微信号：TheAlgorithm，微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。
发布评论请先 登录
相关推荐
求解平均值
连续采样平均值比较取较小值
将100个0~100的随机数取整后构成10*10的二位数组，计算该二维数组的最大值及平均值
求双字节十六进制无符号数据块的平均值
求单字节十六进制无符号数据块的平均值
ADC取初始平均值
工商网监
评论