无广告解析 http://www.playm3u8.cn

博雯发自凹非寺量子位|公众号QbitAI

取整求个无符号整数的平均值，居然也能整出花儿来？

这不，微软大神RaymondChen最近的一篇长文直接引爆外网技术平台，引发无数讨论：

无数人点进去时无比自信：不就是一个简单的相加后除二的小学生编程题吗？

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（SIMDwithinaregister）：

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,upper32bitsunknownmoveax,ecx;rax=ecxzero-extendedto64-bitvaluemovedx,edx;rdx=edxzero-extendedto64-bitvalueaddrax,rdx;64-bitaddition:rax=rax+rdxshrrax,1;64-bitshift:rax=rax>>1;resultiszero-extended;Answerineax//AArch64(ARM64-bit):Assumew0=a,w1=b,upper32bitsunknownuxtwx0,w0;x0=w0zero-extendedto64-bitvalueuxtwx1,w1;x1=w1zero-extendedto64-bitvalueaddx0,x1;64-bitaddition:x0=x0+x1ubfxx0,x0,1,32;Extractbits1through32fromresult;(shift+zero-extendinoneinstruction);Answerinx0

而AlphaAXP、mips64等架构则会将32位值符号扩展为64位值。

这种时候，就需要额外增加归零的指令，比如通过向左进位两字的删除指令rldicl：

//AlphaAXP:Assumea0=a,a1=b,bothincanonicalforminslla0,#0,a0;a0=a0zero-extendedto64-bitvalueinslla1,#0,a1;a1=a1zero-extendedto64-bitvalueaddqa0,a1,v0;64-bitaddition:v0=a0+a1srlv0,#1,v0;64-bitshift:v0=v0>>1addlzero,v0,v0;Forcecanonicalform;Answerinv0//MIPS64:Assumea0=a,a1=b,sign-extendeddexta0,a0,0,32;Zero-extenda0to64-bitvaluedexta1,a1,0,32;Zero-extenda1to64-bitvaluedadduv0,a0,a1;64-bitaddition:v0=a0+a1dsrlv0,v0,#1;64-bitshift:v0=v0>>1sllv0,#0,v0;Sign-extendresult;Answerinv0//Power64:Assumer3=a,r4=b,zero-extendedaddr3,r3,r4;64-bitaddition:r3=r3+r4rldiclr3,r3,63,32;Extractbits63through32fromresult;(shift+zero-extendinoneinstruction);resultinr3

或者直接访问比本机寄存器更大的SIMD寄存器，当然，从通用寄存器跨越到SIMD寄存器肯定也会增加内存消耗。

如果电脑的处理器支持进位加法，那么还可以采用第三种思路。

这时，如果寄存器大小为n位，那么两个n位的无符号整数的和就可以理解为n+1位，通过RCR（带进位循环右移）指令，就可以得到正确的平均值，且不损失溢出的位。

//x86-32moveax,aaddeax,b;Add,overflowgoesintocarrybitrcreax,1;Rotaterightoneplacethroughcarry//x86-64movrax,aaddrax,b;Add,overflowgoesintocarrybitrcrrax,1;Rotaterightoneplacethroughcarry//32-bitARM(A32)movr0,aaddsr0,b;Add,overflowgoesintocarrybitrrxr0;Rotaterightoneplacethroughcarry//SH-3clrt;ClearTflagmova,r0addcb,r0;r0=r0+b+T,overflowgoesintoTbitrotcrr0;Rotaterightoneplacethroughcarry

那如果处理器不支持带进位循环右移操作呢？

也可以使用内循环（rotationintrinsic）：

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_VERmovecx,aaddecx,b;Add,overflowgoesintocarrybitsetcal;al=1ifcarrysetandecx,-2;Clearbottombitmovzxecx,al;Zero-extendbyteto32-bitvalueoreax,ecx;Combinerorear,1;Rotaterightoneposition;Resultineax//__clang__movecx,aaddecx,b;Add,overflowgoesintocarrybitsetcal;al=1ifcarrysetshldeax,ecx,31;Shiftleft64-bitvalue//__clang__withARM-Thumb2movsr2,#0;Preparetoreceivecarryaddsr0,r0,r1;Calculatesumwithflagsadcsr2,r2;r2holdscarrylsrsr0,r0,#1;Shiftsumrightonepositionlslsr1,r2,#31;Movecarrytobit31addsr0,r1,r0;Combine

微软大神的思考们

RaymondChen1992年加入微软，迄今为止已任职25年，做UEX-Shell，也参与Windows开发，Windows系统的很多最初UI架构就是他搞起来的。

他在MSDN上建立的blogTheOldNewThing也是业内非常出名的纯技术向产出网站。

这篇博客的评论区们也是微软的各路大神出没，继续深入探讨。

有人提出了新方法，在MIPSASM共有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位，中间计算值却不是”的情况。

只能说，学无止境啊。

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

参考链接：https://news.ycombinator.com/item?id=30252263

上一篇：

下一篇：