

コンピュータ独特のシフト演算や論理積。論理和などのビット演算で掛け算はどのように表現できますか


CC BY-SA 3.0
2015-04-25T13:48:15.193
9549
2015-07-11T19:24:52.180
9487
question
c アルゴリズム
ブール代数？による掛け算


掛け算（乗算）は足し算（加算）が必要になるので、まず加算の実現方法から考え、次に乗算に進みます。

# 加算

## 1ビットの加算

1ビット同士の加算は、繰り上がりを無視すれば排他的論理和です。

  * 0 ⊕ 0 = 0
  * 1 ⊕ 0 = 1
  * 0 ⊕ 1 = 1
  * 1 ⊕ 1 = 0

## 2ビットの加算

次に2ビット同士（3ビット目への繰り上がりは無視）です。

これには、下1桁から上の桁への繰り上がりを考慮する必要があります。繰り上がりが発生するかどうかはビット積で判定できます。繰り上がりが発生したら、上の桁に1を加算します。

そのため、`s = m + n`は以下のようになります。添え字は桁を表します。一番下の桁を0にしています。

  * s[0] = m[0] ⊕ n[0]
  * s[1] = m[1] ⊕ n[1] + (m[0] AND n[0]) = m[1] ⊕ n[1] ⊕ (m[0] AND n[0])

s[2]への繰り上がりを考慮しないので、繰り上がり時の加算は排他的論理和に変えています。

s[1]を求めるのに(m[0] AND n[0])の結果を使うには左シフトを使います。そのため、一時的な変数xとyを使い、以下のように表現できます。

  * x = m ⊕ n
  * y = (m AND n) << 1
  * s = x + y = x ⊕ y

質問にタグでCが付与されているので、Cのコードで書いてみます。0bプレフィックスを使っているので、GCC拡張またはC++としてコンパイルする必要があります。

[code]

    #include <stdio.h>
    #include <assert.h>
    
    unsigned sum2(unsigned m, unsigned n)
    {
        unsigned x = m ^ n;
        unsigned y = (m & n) << 1;
        return (x ^ y) & 0b11;
    }
    
    int main()
    {
        for (unsigned m = 0; m <= 0b11; ++m)
        {
            for (unsigned n = 0; n <= 0b11; ++n)
            {
                unsigned s = sum2(m, n);
                printf("%u + %u = %u\n", m, n, s);
                assert(s == ((m + n) & 0b11));
            }
        }
    }
    
[/code]

## 3ビットの加算

同様に3ビット以上も計算できます。ただし、繰り上がりを計算した結果、さらに繰り上がりが発生する可能性があるため、もう少し複雑です。

  * x1 = m ⊕ n
  * y1 = (m AND n) << 1
  * s = x1 + y1  
ここで、2ビットのときと異なり、この加算を再び排他的論理和・論理積・ビットシフトに展開します。

  * x2 = x1 ⊕ y1
  * y2 = (x1 AND y1) << 1
  * s = x2 ⊕ y2

Cのコードで書くと、このようになります。

[code]

    #include <stdio.h>
    #include <assert.h>
    
    unsigned sum3(unsigned m, unsigned n)
    {
        unsigned x1 = m ^ n;
        unsigned y1 = (m & n) << 1;
        unsigned x2 = x1 ^ y1;
        unsigned y2 = (x1 & y1) << 1;
        return (x2 ^ y2) & 0b111;
    }
    
    int main()
    {
        for (unsigned m = 0; m <= 0b111; ++m)
        {
            for (unsigned n = 0; n <= 0b111; ++n)
            {
                unsigned s = sum3(m, n);
                printf("%u + %u = %u\n", m, n, s);
                assert(s == ((m + n) & 0b111));
            }
        }
    }
    
[/code]

## 加算のまとめ

4ビット以上も、3ビットの場合を拡張していけば実現できます。

Cのコードで表現しようとしているため若干変形していますが、これは全加算器と呼ばれるものになります。

本来の全加算器は1ビットの入力を3つ受け取り、1ビットの加算結果と繰り上がり（キャリー）の1ビットを出力するデジタル回路です。入力が3つなのは、演算対象2つと下位桁からの繰り上がりのためです。下位ビットから順に全加算器に通すことで、複数ビットの加算が実現できます。

もちろん、このようなやり方ではビット数に比例して時間がかかってしまいます。そこで、複数ビットの加算には高速化の手法がいくつかあります（キャリーを別途計算するなど）。

# 乗算（掛け算）

愚直にやるなら`m * n`はmをn回加算することで実現できます。

もう少し効率的な方法として、筆算のように1桁ずつの乗算し、その合計を求める方法が考えられます。二進法で考えれば、1桁の乗算は1か0で掛けることなので、加算と幾ばくかのビット演算で実現できる話になります。

以下のコードでは、加算は実現済みとして、+=演算子を使用しています。ご容赦ください。

[code]

    #include <stdio.h>
    #include <assert.h>
    
    unsigned product(unsigned m, unsigned n)
    {
        unsigned result = 0;
        while (n != 0)
        {
            //result += n & 1 ? m : 0;
            result += (unsigned)-(n & 1) & m;
            n >>= 1;
            m <<= 1;
        }
        return result;
    }
    
    int main()
    {
        for (unsigned m = 0; m <= 256; ++m)
        {
            for (unsigned n = 0; n <= 256; ++n)
            {
                unsigned s = product(m, n);
                printf("%u * %u = %u\n", m, n, s);
                assert(s == m * n);
            }
        }
    }
    
[/code]


CC BY-SA 3.0
2015-04-25T16:39:41.943
9553
2015-07-11T19:24:52.180
2015-07-11T19:24:52.180
8616
8616
9549
answer


次は単純な筆算と同様の処理をＣで書いたもの  
３２ビット符号無し整数同士の掛け算。

[code]

    #include <stdio.h>
    #include <stdint.h>
    #include <inttypes.h>
    
    uint64_t add(uint64_t a, uint64_t b){
        uint64_t result = 0, carry = 0, mask = 1, x, y;
    
        while(mask){
            x = a & mask;
            y = b & mask;
            result |= x ^ y;
            if(carry){
                carry = (x & y) || (result & mask);
                result ^= mask;
            } else {
                carry = x & y;
            }
            mask <<= 1;
        }
        return result;
    }
    
    uint64_t mul(uint32_t a, uint32_t b){
        uint64_t result = 0;
        uint64_t tmp = a;
    
        while(b){
            if(b & 1){
                result = add(result, tmp);
            }
            tmp <<= 1;
            b   >>= 1;
        }
        return result;
    }
    
    int main(void){
        uint32_t x = 123456, y = 654321;
        uint64_t result = mul(x, y);
    
        printf("%" PRIu32 "*%" PRIu64 "=%" PRIu64 "\n", x, y, result);
    
        return 0;
    }
    
[/code]


CC BY-SA 3.0
2015-04-25T19:15:42.383
9557
2015-04-25T19:15:42.383
5044
9549
answer