ビット演算事始 - 株式会社リクルートテクノロジーズ Advent Calendar 2014 12/23

最近、Hacker's Delightという本を買いました。

作者: Henry S. Warren
出版社/メーカー: Addison-Wesley Professional
発売日: 2012/09/25
メディア: Kindle版
この商品を含むブログ (2件) を見る

この本の2章は、Basicsというタイトルで、ビット演算について、基本的な性質や関係式が述べられているのですが、この本は前文にあるとおり、証明は書かないので、慣れてないと読むのに苦労しますというか、しました。という訳で、特に2.2節に出てくる等式を読み解く為に考えた事のメモをもって、株式会社リクルートテクノロジーズAdvent Calendar 2014の12/23分の記事とさせていただきます。

以下、このエントリでは、8bitの符号付き/無し整数を考えます。また、整数を10進表記する際には日常通りに表記し、2進表記する際には、01010101bのように、最後にbを置きます。

2の補数表現

コンピュータの中では、符号付きの整数は、少し変わった方法で表現されます。普通に考えれば、+/-の表現に1bitを使い、残りの7bitで絶対値を表現すれば良いように思います。例えば、最左bitの0/1が+/-に対応するとすれば、

1 = 00000001b
2 = 00000010b ...
3 = 00000011b
-1 = 10000001b
-2 = 10000010b
-3 = 10000011b ...

というように。しかし、実際には、負の数は

-1 = 11111111b
-2 = 11111110b
-3 = 11111101b

と、11111111bを-1として、後ろから順番に値が割当てられていて、これは2の補数表現と呼ばれています。これは何故かと言うと、引き算が足し算で出来るというご利益があるので、こうなっています。ちょっと何を言っているのか分からないと思うので、詳しく説明します。唐突ですが、xy平面上の単位円周を想像して下さい。点P0を(0,1)として、点P1から順に点P255までが、単位円周上に等間隔に並んでいるとします。さらに、

点P0に8bitのbit列00000000を割当て、
右回りに順番に点P1には00000001,
点P2には00000010, …
点P255には11111111が

割当てられているとします。この時、2の補数表現では、てっぺんの点P0が0,右回りに進むと、点P1が1, 点P2が2, …と1ずつ値が増加し、逆に左に進むと点255が-1, 点254が-2と、1ずつ値が減少していきます。右回りと左回りのカウントアップ/ダウンは、0のちょうど反対側、10000000が割当てられている点P128でぶつかるのですが、この点は128ではなくて、-128と解釈することになっています。こうすれば、先頭bitの0/1で値の正/負を判断出来るからです。0の場合が有るので、正確には正or0/負の判断ですが。このように値が表現されているのが、整数型の変数の値がオーバーフローした時に、絶対値の大きい負の値が出てくる理由です。

2の補数表現での引き算3 - 1を考えてみます。3は、点P3(00000011)に割当てられています。ここから1引いた値を知りたければ、単位円周上を、左回りに1目盛だけ進めば良いです。が、今、円周を考えているので、1目盛左回り進む事は、255目盛右回りに進む事と同じです。点P3から円周上を255目盛進んだ場所とは、点P3のbit列00000011に点P255のbit列11111111を2進数として足し算して、桁あふれを無視すれば得られます。これが、引き算が足し算で出来るという意味です。

+1, -1の意味

ここでは、整数に+1, -1をする事の、bit演算としての意味を考えてみます。例えば01010111bという整数に00000001bを足すと、01011000bになります。これは「右に詰まった1を0に反転し、最右の0を1に反転」という操作です。逆に、-1は「右に詰まった0を1に反転し、最右の1を0に反転」という操作になります。

論理否定の意味

ここでは、全てのbitを反転する操作の意味を考えてみます。2の補数表現の所で出てきた単位円を思い出します。点P0と点255の中点を点N1として、点N1と原点を結ぶ直線をnと呼ぶことにします。直線nは、y軸をちょっとだけ(目盛半分だけ)左に傾けた直線です。論理否定は、直線nに関する線対称移動です。これを今から数学的帰納法のような議論で示します。

まず、点P0(00000000b)と点P255(11111111b)は、bit列としては反転しており、かつ、直線nに関して線対称の位置に有ります。

次に、直線nの右側の点X、点Xと直線nに関して線対称な位置にある点Yについて、それらに割当てられたbit列が反転していると仮定します。この時、Xから1目盛右回りに進んだ点と、Yから1目盛左回りに進んだ点のbitが反転していることを示したいのですが、それは、先の+1, -1の操作の意味を考えると分かります。

-1倍の意味

-1倍は、シンプルにy軸での反転です。これは、殆ど自明だと思います。

-x = ¬x + 1の意味

2.2節には、上のような等式が出てきます。最初見たとき、全く意味が分からなかったのですが、上の単位円周をイメージしたら理解出来ました。上で述べた事を総合すると

左辺は、y軸での反転
右辺は、直線nで反転した後、1目盛分の回転

を意味していて、これらが等しいと言っています。全て線形変換なので、行列を比較すれば良いです。面倒臭いので、Rで確認します。

theta <- pi/128 # 1目盛の角度

# -1倍: y軸での反転
minus <- matrix(c(-1,0,
                   0,1),
                byrow=T,nrow=2)

# 論理否定: 直線nでの反転
# = y軸をtheta/2だけ左に傾けた直線での反転
# = 全体をtheta/2だけ右に回転して、y軸で反転して、全体をtheta/2だけ左に回転
rot.theta.2 <- local({
    p <- theta/2
    cs <- cos(p)
    sn <- sin(p)
    matrix(c(cs,-sn,
             sn,cs),
           byrow=T,nrow=2)
})
not <- rot.theta.2 %*% minus %*% solve(rot.theta.2)

# +1: 1目盛右に進む
# = thetaだけ右に回転
rot.theta <- local({
    cs <- cos(theta)
    sn <- sin(theta)
    matrix(c(cs,-sn,
             sn,cs),
           byrow=T,nrow=2)
})
plusone <- solve(rot.theta)

# -x = ¬x + 1の確認
minus - (plusone %*% not)


# > minus - (plusone %*% not)
#               [,1]         [,2]
# [1,] -1.110223e-16 0.000000e+00
# [2,]  0.000000e+00 2.220446e-16

1個の式の説明だけでダラダラと書いてしまいましたが、他にも色々な関係式が載っていて勉強になります。