本文经AI新媒体量子位（公众号ID：QbitAI）授权转载，转载请联系出处。四舍五入求一个无符号整数的平均值，居然能开花？这不，最近微软大师陈峰的一篇长文，直接引爆了网络技术平台，引发无数讨论：无数人点进去就信心满满：不就是一道简单的小学编程题吗加然后除以二的学生？unsignedaverage(unsigneda,unsignedb){return(a+b)/2;}但是跟着大神深入挖掘，却渐渐懵了...求平均值没那么简单。先从开头提到的小学生说起，这个简单的方法似乎有一个致命的缺陷：如果无符号整数的长度是32位，那么如果两个相加的值是最大长度的一半，那么只有在添加的第一步，才会发生内存溢出。即平均（0x80000000U，0x80000000U）=0。但是，有很多解决方案。大多数有经验的开发人员首先想到的是预先限制添加数字的长度以避免溢出。具体方法有两种：1、已知相加的两个无符号整数中较大的值，减去较小的值除以2，提前减长：unsignedaverage(unsignedlow,unsignedhigh){returnlow+(high-low)/2;}2.预先将两个无符号整数相除，同时通过按位AND对低位进行修正，保证两个整数均为奇数时结果仍然正确。（顺便说一句，这是2016年过期的专利方法）unsignedaverage(unsigneda,unsignedb){return(a/2)+(b/2)+(a&b&1);}这两个是比较常见的思路，很多网友也表示最先想到的是2016年的专利方法。广大网友也能很快想到的方法就是SWAR(SIMDwithinaregister):unsignedaverage(unsigneda,unsignedb){return(a&b)+(a^b)/2;//variant(a^b)+(a&b)*2和C++20版本中的std::midpoint函数。接下来作者提出第二个思路：如果无符号整数为32位，native寄存器大小为64位，或者编译器支持多字运算，可以强制将相加的值转换为长整型数据。unsignedaverage(unsigneda,unsignedb){//假设“unsigned”是32位类型和//“unsignedlonglong”是64位类型。return((unsignedlonglong)a+b)/2;}不过有一点需要特别注意：必须保证64位寄存器的前32位全为0，以免影响其余的32位值。x86-64和aarch64等架构自动将32位值零扩展为64位值：//x86-64:Assumeecx=a,edx=b,upper32bitsunknownmoveax,ecx;rax=ecx零扩展到64位值movedx,edx;rdx=edx零扩展到64位valueaddrax,rdx;64位加法：rax=rax+rdxshrrax,1;64位移位：rax=rax>>1;结果是零扩展的；Answerineax//AArch64(ARM64-bit):Assumew0=a,w1=b,upper32bitsunknownuxtwx0,w0;x0=w0零扩展为64位值uxtwx1,w1;x1=w1零扩展到64位valueaddx0,x1;64位加法：x0=x0+x1ubfxx0,x0,1,32；从结果中提取位1到32；（在一条指令中移位+零扩展）；Answerinx0而AlphaAXP、mips64等架构会将32位值符号扩展为64位值。在这种情况下，有必要添加一条额外的归零指令，例如删除指令rldicl：//AlphaAXP:Assumea0=a,a1=b,bothincanonicalforminslla0,#0,a0;a0=a0零扩展为64位值inlla1,#0,a1;a1=a1零扩展到64位valueaddqa0,a1,v0;64位加法：v0=a0+a1srlv0,#1,v0；64位移位：v0=v0>>1addl零,v0,v0;强制规范形式；v0//MIPS64中的答案：假设a0=a,a1=b,sign-extendeddexta0,a0,0,32;将a0零扩展为64位valuedexta1,a1,0,32；将a1零扩展为64位valuedadduv0,a0,a1；64位加法：v0=a0+a1dsrlv0,v0,#1；64位移位：v0=v0>>1sllv0,#0,v0;符号扩展结果；v0//Power64中的答案：假设r3=a,r4=b，零扩展添加r3,r3,r4；64位加法：r3=r3+r4rldiclr3,r3,63,32；从结果中提取位63到32；（在一条指令中移位+零扩展）；导致r3还是直接访问SIMD寄存器比native寄存器大，当然从通用寄存器跨到SIMD寄存器肯定也会增加内存消耗。如果计算机的处理器支持进位加法，那么也可以使用第三种思路。此时如果寄存器大小为n位，那么两个n位无符号整数之和可以理解为n+1位，通过RCR（带进位循环右移）指令可以得到正确的平均值。而不会丢失溢出的位。带进位向右旋转//x86-32moveax,aaddeax,b;添加，溢出进入进位bitrcreax,1;通过进位向右旋转一位//x86-64movrax,aaddrax,b;添加，溢出进入进位bitrcrrax,1;通过进位向右循环一位//32位ARM(A32)movr0,aaddsr0,b;添加，溢出进入进位bitrrxr0；通过进位//SH-3clrt向右旋转一位；清除Tflagmova,r0addcb,r0;r0=r0+b+T，溢出进入Tbitrotcrr0；通过进位右移一位如果处理器不支持带进位的右移操作怎么办？旋转内在也可以使用：unsignedaverage(unsigneda,unsignedb){#ifdefined(_MSC_VER)unsignedsum;autocarry=_addcarry_u32(0,a,b,&sum);sum=(sum&~1)|携带;返回_rotr（总和，1）；#elifdefined(__clang__)无符号进位；总和=(总和&~1)|携带;自动求和=__builtin_addc(a,b,0,&carry);return__builtin_rotateright32(sum,1);#else#errorUnsupportedcompiler.#endif}结果x86架构下的代码生成没变，MSCver架构下的代码生成变差了，arm-的c拇指2lang代码生成更好//_MSC_VERmovecx,aaddecx,b;添加，溢出进入进位位等；al=1如果进位setandecx,-2;清除底部bitmovzxecx,al;将字节零扩展为32位值或eax,ecx；组合器或耳朵，1;向右旋转一个位置；结果在eax//__clang__movecx,aaddecx,b;添加，溢出进入进位位等；al=1如果进位setshldeax,ecx,31;左移64位值//__clang__withARM-Thumb2movsr2,#0;准备接收进位符r0,r0,r1；用flagsadcsr2,r2计算总和；r2持有carrylsrsr0,r0,#1；一个位置lslsr1,r2,#31;将进位移动到位31addsr0,r1,r0;CombineRaymondChen于1992年加入微软，至今已工作25年。他是一名UEX-Shell，同时也参与了Windows的开发，Windows系统的很多初始UI架构都是他创建的。他在MSDN上建立的博客TheOldNewThing也是业内知名的纯技术输出网站。本博客评论区也有微软各路高手出没，继续深入讨论。有人提出了一种新方法，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有人说不用(a/2)+(b/2)+(a&b&1)，为什么不直接将(a&1)&(b&1))作为进位放入加法器进行计算呢？评论区也有人推荐了TopSpeed编译器，可以通过指定合适的代码字节和调用约定来定义一个内联函数，解决“乘除法的结果是16位，但中间计算值为不是”。只能说学无止境。
