兩個 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

Facebook 在 MySQL 裡存時間的型態

MySQL at Facebook這邊說明提到了,Facebook 內部是使用 INT UNSIGNED 儲存時間:

Which gets us to the point that it is no different than storing INT (hello 2038?) or UNSIGNED INT (a bit later) or BIGINT (till the end of time) and possibly passing binary values in efficient protocols eventually.

If you got that far of this post, your likes in Facebook graph are stored with 'INT UNSIGNED' time field.

順道一提,INT 是 2038 年問題,INT UNSIGNED 是 2106 年問題。

而 Facebook 在 MySQL 上會選擇不使用 DATETIMETIMESTAMP 的原因其實跟技術搭不上太多關係,主因是因為 MySQL 根本沒打算修 XDDD

It is my favorite MySQL bug, simply because it forces any reasonable mind not to use TIMESTAMP, and MySQL is never going to fix it (nor will ever understand time). I lost my temper a bit on that bug: https://bugs.mysql.com/bug.php?id=38455

我的猜測是已經爛成一團了,而且大家都有 workaround (呃,其實就是 Facebook 推薦用 INT UNSIGNED 的方法),再考慮到有一票現有程式,在上面狂用 side effect 讓執行結果正確,不如就不要修這種吃力不討好的東西了 XDDD

另外一方面 timezone 資訊其實常常變化,常常需要更新 MySQL 的 timezone database (而這對於維運來說不是什麼開心的事情):

There're few ways around that. One of them is side-load and maintain timezone data inside MySQL itself - it has support for internal timezone database and tracks obscure time shifts like ones for "Pacific War Time" and "Pacific Peace Time". That is operationally feasible (you have to remind yourself to update the database whenever time rules change, and they do change a lot, if you consider every timezone in the world), but has limited value.

這就是為什麼大家遇到 MySQL 時都會推薦用 INT UNSIGNED 了...

另外可以參考三年前的文章「MySQL 裡儲存時間的方式...」,裡面引用了 Baron Schwartz 的說明:

All date and time columns shall be INT UNSIGNED NOT NULL, and shall store a Unix timestamp in UTC.

其實這已經是個 best practice 了...

MySQL 裡儲存時間的方式...

這應該是 MySQL 的 best practice 之一,不知道為什麼 Baron Schwartz 又拿出來講:「A simple rule for sane timestamps in MySQL」。

MySQL 內可以儲存「日期與時間」的資料型態是 DATETIME 與 TIMESTAMP 兩種,不過 DATETIME 沒有時區觀念,而 TIMESTAMP 只能是 UTC (GMT+0)。

相較於隔壁棚 PostgreSQLDate/Time Types 就一種 TIMESTAMP,但支援 with timezone 與 without timezone 直接解決問題。

這使得 MySQL 上在儲存「日期與時間」以及處理的時候一直有種 WTF 的感覺...

就如同 Baron Schwartz 的建議,如果使用 MySQL,目前比較好的方法是用 INT UNSIGNED NOT NULL 儲存,把 timezone 的處理都放到應用程式端來處理,這樣產生的問題會比較少...

真的需要在 INSERT 或是 UPDATE 時更新欄位,可以用 trigger 處理,彈性反而比內建功能大不少。