阅读全文

⭐⭐⭐ Spring Boot 项目实战	⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》	《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》	《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》	《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》	《Java 面试题 + Java 学习指南》

摘要: 原创出处量子位 | 公众号 QbitAI 「博雯发自凹非寺」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注**微信公众号：【芋道源码】**有福利：

RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表

RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址

您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。

新的源码解析文章实时收到通知。每周更新一篇左右。

认真的源码交流微信群。

博雯发自凹非寺

量子位 | 公众号 QbitAI

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

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

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

unsigned average(unsigned a, unsigned b)
{
    return (a + b) / 2;
}

但跟着大神的一路深挖，却逐渐目瞪狗呆……

没那么简单的求平均值

先从开头提到的小学生都会的方法看起，这个简单的方法有个致命的缺陷：

如果无符号整数的长度为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寄存器肯定也会增加内存消耗。

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

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

△带进位循环右移

// x86-32
    mov     eax, a
    add     eax, b          ; Add, overflow goes into carry bit
    rcr     eax, 1          ; Rotate right one place through carry

// x86-64
    mov     rax, a
    add     rax, b          ; Add, overflow goes into carry bit
    rcr     rax, 1          ; Rotate right one place through carry

// 32-bit ARM (A32)
    mov     r0, a
    adds    r0, b           ; Add, overflow goes into carry bit
    rrx     r0              ; Rotate right one place through carry

// SH-3
    clrt                    ; Clear T flag
    mov     a, r0
    addc    b, r0           ; r0 = r0 + b + T, overflow goes into T bit
    rotcr   r0              ; Rotate right one place through carry

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

也可以使用内循环（rotation intrinsic）：

unsigned average(unsigned a, unsigned b){#if defined(_MSC_VER)    unsigned sum;    auto carry = _addcarry_u32(0, a, b, &sum);    sum = (sum & ~1) | carry;    return _rotr(sum, 1);#elif defined(__clang__)    unsigned carry;    sum = (sum & ~1) | carry;    auto sum = __builtin_addc(a, b, 0, &carry);    return __builtin_rotateright32(sum, 1);#else#error Unsupported compiler.#endif}

结果是，x86架构下的代码生成没有发生什么变化，MSCver架构下的代码生成变得更糟，而arm-thumb2的clang 的代码生成更好了。

// _MSC_VER    mov     ecx, a    add     ecx, b          ; Add, overflow goes into carry bit    setc    al              ; al = 1 if carry set    and     ecx, -2         ; Clear bottom bit    movzx   ecx, al         ; Zero-extend byte to 32-bit value    or      eax, ecx        ; Combine    ror     ear, 1          ; Rotate right one position                            ; Result in eax// __clang__    mov     ecx, a    add     ecx, b          ; Add, overflow goes into carry bit    setc    al              ; al = 1 if carry set    shld    eax, ecx, 31    ; Shift left 64-bit value// __clang__ with ARM-Thumb2    movs    r2, #0          ; Prepare to receive carry    adds    r0, r0, r1      ; Calculate sum with flags    adcs    r2, r2          ; r2 holds carry    lsrs    r0, r0, #1      ; Shift sum right one position    lsls    r1, r2, #31     ; Move carry to bit 31    adds    r0, r1, r0      ; Combine

微软大神的思考们

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

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

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

有人提出了新方法，在MIPS ASM共有36个循环：

unsigned avg(unsigned a, unsigned b)
{
    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

芋道源码 —— 纯源码解析博客

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

没那么简单的求平均值

△带进位循环右移

微软大神的思考们