查看原文
其他

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

推荐关注↓

来源:量子位 公众号 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, 132   ; 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, 032   ; Zero-extend a0 to 64-bit value
    dext    a1, a1, 032   ; 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, 6332  ; 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

- EOF -

推荐阅读  点击标题可跳转

1、一些著名的软件都用什么语言编写?

2、“阿里味” PUA 编程语言火上 GitHub 热榜

3、深入理解 CPU 的调度原理


觉得本文有帮助?请分享给更多人

推荐关注「算法爱好者」,修炼编程内功

点赞和在看就是最大的支持❤️

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存