ビット単位 (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の結果になります。

←解決時は質問者本人がここをチェックしてください。

戻る