TAOCP

TAOCP V4F1にこういう問題があった(7.1.3-102).

日, 時, 分, 秒, ミリ秒がそれぞれ3, 1, 1, 1, 2バイトに収まっている. 3バイトで日を表わすと, 2²⁴/365=45964年分だから, ここはどうでもいい. こういう時間データ2つを足したり引いたりする方法である. その解答の最後に「`fc81'の`c'が偶数なのは運が良かった.」とあるのはなぜか.

方法はこうである. 2つの数をxとyとする. 減算ならz←x-y, 加算ならz←x+y+#e8c4c4c4fc18とする. 分の桁でいうと, xの分とyの分を足して60になるか60を超えたとき, 256の桁に1を送りたいので, 256-60=196=11000100₂=#c4を足す. しかし和が60に満たない時はどうするか. 60はバイトサイズ256の半分以下なので, バイトの先頭のビットが1なら繰上げはなかった, 0なら繰上げがあったが分かる. なかった場合は先ほどの#c4を引かなければならない. 従って, 先頭のビットが1ならそのバイトを#c4に, 0ならそのバイトを0にしたものが欲しい. それは簡単だ. バイトを#80で&をとる. その1を左に1ビットシフトしたものから, その1を右に7ビットシフトしたものを引けば, 11111111か00000000になるので, これを#c4を&したものを引く. 時, 分, 秒はそれで良い. ミリ秒はどうするか.

2バイトのミリ秒の区域の先頭が1のとき, 上の伝では 11111111 0000000になってしまう. そこで, 先頭が１の時, この区域ではさらに1を引くのである. するとこの右端の1から引かれて,11111110 11111111が出来る. これとfc18の&をとることになり, うまい具合いにマスクが0になったビットは, cなので0であったわけだ.

なるほど. 運がよかった.