ビット単位 (ID:61043)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文 別の視点からの方法をふと思いついたので書いてみます。 固定ビット数のみ対応、オーバーフロー検知なし、と手抜きしてますがご容赦のほどを。 考え方は後の方に書いています。 /* a+bの計算結果を返す。 */ unsigned Add(unsigned a, unsigned b) { while(b != 0){ unsigned next_b = (a & b) << 1; a ^= b; b = next_b; } return a; } /* 上関数の再帰版。効率はともかく、考え方はこちらの方がわかりやすいと思う */ unsigned RecursiveAdd(unsigned a, unsigned b) { if(b == 0){ return a; } else{ return RecursiveAdd(a ^ b, (a & b) << 1); } } /* 利用サンプル */ int main() { unsigned val1 = 0xba987654, val2 = 0xfedcba98; printf("%x + %x = &#92;n", val1, val2); printf(" %x (by Add())&#92;n", Add(val1, val2)); printf(" %x (by RecursiveAdd())&#92;n", RecursiveAdd(val1, val2)); printf(" %x (by '+' operator)&#92;n", val1 + val2); return 0; } 考え方: a + b == (繰り上がりを無視した足し算の結果) + (繰り上がり) == (a ^ b) + ((a & b) << 1) （＊） なので、 a_1 = a ^ b b_1 = (a & b) << 1 とすれば、a + b = a_1 + b_1。 ここから、a_1とb_1にさらに式(*)を適用してa_2、b_2をつくって、さらに…… とすることができます。 このようにすると、実はb_iの下位iビットは必ず0になります(証明は省略)。 nビット数の下位nビットが0とは、単なる0ですので、最大でもn回変形を繰り返せば、0との足し算になります。 なので、b_iが0になるまで変形を繰り返し、0になったときのa_iを返せば、それがa + bの結果になります。