兩個 unsigned int 取平均值的方法

Hacker News Daily 上看到 Raymond Chen 在講怎麼對兩個 unsigned int 取平均值的方法:「On finding the average of two unsigned integers without overflow」,這篇裡面提到了不少有趣的歷史,另外 Hacker News 上的討論「Finding the average of two unsigned integers without overflow (microsoft.com)」也可以翻翻。

最直覺的解法會有 overflow 的問題:

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

如果已知 a 與 b 的大小的話 (如同作者說的,蠻多時候都符合這個情況),可以用這個方法避免 integer overflow:

unsigned average(unsigned low, unsigned high)
{
    return low + (high - low) / 2;
}

另外還有個方法是有專利的 (「Calculating the average of two integer numbers rounded towards zero in a single instruction cycle」),雖然在 2016 年到期了,各除以二相加後,只有 ab 都是奇數的情況下需要補 1:

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

接下來的這個方法用 AND 與 XOR 搞事,其中的原理可以解釋成,相同的 bit 不動表示值不需要動,不同的 bit 表示降一位 (除以 2):

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

最後是暴力解,用個比較大的 data type 搞定他:

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;
}

後面有很多 assembly 的妖魔鬼怪跑出來就不提了 XDDD

Leave a Reply

Your email address will not be published.