您现在的位置是：主页 > 品牌 > 微软 >
从微软大师的求均值代码中我领悟到自己仍然太年轻了
发布时间：2022年02月14日 22:51:53 微软 人已围观
简介微软大神Raymond Chen最近的一篇文章引发了外网技术平台的热议，讨论围绕整出无符号整数平均值这一看似简单的数学问题展开。许多人自信地认为这只是简单的相加后除以二，然而文章...
想求一个无符号整数的平均值，竟然也会引发如此多的讨论？
最近，微软的技术专家Raymond Chen撰写了一篇深入探讨的文章，瞬间在海外技术社区引发热议：
很多人自信满满地点击进去，以为只是个简单的加法后除以2的编程练习：
unsigned average(unsigned a, unsigned b) { return (a + b) / 2; }但在大神的详细解析中，逐步让人惊愕……
求平均并没有那么简单
先来看小学生也能处理的基本方法，这个看似简单的解法有一个致命问题：
若无符号整数的长度是32位，假设两个值相加都达到最大值的一半，在第一步相加时就可能会造成内存溢出。
这就导致了average（0x80000000U, 0x80000000U）=0。
不过，解决这个问题的方法有很多，资深开发者通常会考虑通过限制加数的范围来避免溢出。
具体来说，有两种思路：
1、如果已知两个无符号整数中较大的那个数字，就可以先减去较小的数字再除以2，从而提前减少计算长度：
unsigned average(unsigned low, unsigned high) { return low + (high - low) / 2; }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) { // 假设 "unsigned" 是32位类型，而 // "unsigned long long" 是64位类型。 return ((unsigned long long)a + b) / 2; }不过要特别留意：必须确保64位寄存器的前32位为0，以免影响到后32位的结果。
如x86-64和aarch64等架构会自动将32位值扩展为64位：
// x86-64: 假设ecx = a, edx = b，前32位未知 mov eax, ecx ; rax = ecx 零扩展到64位 mov edx, edx ; rdx = edx 零扩展到64位 add rax, rdx ; 64位相加: rax = rax + rdx shr rax, 1 ; 64位右移: rax = rax >> 1 ; 结果零扩展 ; 答案在eax // AArch64 (ARM 64位): 假设w0 = a, w1 = b，前32位未知 uxtw x0, w0 ; x0 = w0 零扩展到64位 uxtw x1, w1 ; x1 = w1 零扩展到64位 add x0, x1 ; 64位相加: x0 = x0 + x1 ubfx x0, x0, 1, 32 ; 从结果中提取1到32位；（一次指令实现右移 +零扩展）; 答案在x0但像Alpha AXP、mips64等架构就会将32位值符号扩展为64位。