ビット演算(AND,XOR,左シフト)だけで、足し算を行う。単純なようでいて、結構難しい…。

ビット演算(AND,XOR,左シフト)だけで、足し算を行う。単純なようでいて、結構難しい…。

2bitで考えると

00 + 00 = 00
01 + 00 = 01
00 + 01 = 01
01 + 01 = 10

1bit目は、XOR演算の結果と同じ
2bit目は、AND演算の結果と同じ

つまり
XOR演算は「繰り上がりが無ければ、足し算と同じ結果」
AND演算は「繰り上がるかどうかが分かる(結果が1なら繰り上がる)」

この2つをうまく組み合わせれば、足し算が出来る。

パターンその1(繰り上がり無し)
1000 + 0001 = 1001
8 + 1 = 9
繰り上がりが無いので、XORするだけで足し算になる。

パターンその2(繰り上がり有り)
0001 + 0001 = 0010
1 + 1 = 2

0001 xor 0001 = 0000
繰り上がりがあるので、XORするだけじゃダメ!

0001 AND 0001 = 0001
AND演算するだけでもダメ!

(0001 AND 0001) << 1 = 0010
AND演算+左シフト1桁で、正解となった。

パターンその3(繰り上がり有り+アルファ)
0001 + 0011 = 0100(4)
1 + 3 = 4

(0001 AND 0011) << 1 = 0010(2)
AND演算+左シフト1桁ではダメ!1桁目の繰り上がりは出来ているけど、2桁目が出来てない…。

a, 0001 xor 0011 = 0010(繰り上がらない桁の足し算を行う)
b, (0001 AND 0011) << 1 = 0010(繰り上がる桁を1出力して、左シフト1で実際に繰り上げる)
c, (a and b) << 1 すなわち (0010 AND 0010) << 1 = 0100(4)

ビット演算なので、各ビット同士の処理となる。
最初に、XORで繰り上がらない桁の足し算を行う
次に、ANDで繰り上がる桁を1出力して、左シフト1で実際に繰り上げる
最後に、最初と次の結果をXORと左シフトで、足し算を行う。
終了条件は、繰り上がりがなくなったら足し算終了。
一気に複雑になった…。

単純なようでいて、結構難しい…。
ビット演算は各ビットが独立して演算されるのが特徴だけど、足し算の桁上がりをANDと左シフトで計算しているのが印象的。
あと、XORが繰り上がりの無い足し算という発想はなかった…。

手計算だと、下の桁から一桁毎に計算して繰り上がって・・・みたいな感じで計算するけど、ビット演算だと全ビットを一気に処理するので
1, 各ビットで、繰り上がりだけの足し算
2, 各ビットで、繰り上がりのない足し算
3, 結果を足す(繰り上がりのない足し算)
4, 繰り上がりがなくなるまでリピート

というやり方になるのね。なるほど~。

コメントを残す

メールアドレスが公開されることはありません。