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

2bitで考えると

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

1bit目は、XOR演算の結果と同じ
2bit目は、AND演算の結果と同じ
つまり
XOR演算は「繰り上がりが無ければ、足し算と同じ結果」
AND演算は「繰り上がるかどうかが分かる(結果が1なら繰り上がる)」
この２つをうまく組み合わせれば、足し算が出来る。

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

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

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

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

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

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

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

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

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

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

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

<?php

$a = 0x03; // 3
$b = 0x05; // 5
// 引き算の場合は、2の補数で負数にするだけ。32bit扱いになる。
// $b = (~$b) + 1;

// １ループ毎に左シフトしているので、最大でもビット数ループすれば終わる。
// bは繰り上がったビットを管理していて、繰り上がりがなくなったら足し算終了。
while ($b != 0)
{

    // AND演算して、繰り上がるビットを算出。左シフトして実際に繰り上げる(繰り上がる足し算だけを行う)
    $c = ($a & $b) ＜＜ 1;

    // XOR演算して、繰り上がらない各ビットの足し算を行う。
    $a ^= $b;

    // $b($c)は繰り上がったビットを管理していて、繰り上がりがなくなったら足し算終了。
    $b = $c;

    printf("%x, %x, %x<br>", $a, $b, $c);

}
printf("%x", $a);

<?php

$a = 0x03; // 3

$b = 0x05; // 5

// 引き算の場合は、2の補数で負数にするだけ。32bit扱いになる。

// $b = (~$b) + 1;

// １ループ毎に左シフトしているので、最大でもビット数ループすれば終わる。

// bは繰り上がったビットを管理していて、繰り上がりがなくなったら足し算終了。

while ($b != 0)

{

// AND演算して、繰り上がるビットを算出。左シフトして実際に繰り上げる(繰り上がる足し算だけを行う)

$c = ($a & $b) ＜＜ 1;

// XOR演算して、繰り上がらない各ビットの足し算を行う。

$a ^= $b;

// $b($c)は繰り上がったビットを管理していて、繰り上がりがなくなったら足し算終了。

$b = $c;

printf("%x, %x, %x<br>", $a, $b, $c);

}

printf("%x", $a);

関連記事