微软|看完微软大神写的求平均值代码我意识到自己还是too young了代码|看完微软大神写的求平均

取整求个无符号整数的平均值，居然也能整出花儿来？
这不，微软大神Raymond Chen最近的一篇长文直接引爆外网技术平台，引发无数讨论：

文章图片

无数人点进去时无比自信：不就是一个简单的相加后除二的小学生编程题吗？
unsigned average(unsigned a, unsigned b) { return (a + b) / 2; }但跟着大神的一路深挖，却逐渐目瞪狗呆……
【微软|看完微软大神写的求平均值代码我意识到自己还是too young了】没那么简单的求平均值
先从开头提到的小学生都会的方法看起，这个简单的方法有个致命的缺陷：
如果无符号整数的长度为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寄存器肯定也会增加内存消耗。

微软|看完微软大神写的求平均值代码 我意识到自己还是too young了

微软|看完微软大神写的求平均值代码我意识到自己还是too young了