2800


掛け算の場合は

[code]

    5 * 10 = 0b101 * 0b1010
           = 0b101 * (2^3 + 2^1)
           = (0b101 << 3) + (0b101 << 1) = 0b110010 = 50
    
[/code]

で計算できるのは分かるのですが、5/3などを計算する場合どうすればいいのか思い当たらないので説明いただければと思います。
そのまま割る方法でも、1/3をバイナリで表現する方法でも大丈夫です（5 * 1/3 と出来るので）。


CC BY-SA 3.0
2014-12-29T11:34:25.987
2792
2014-12-30T04:17:49.387
2014-12-29T12:10:17.743
3974
3974
question
アルゴリズム
ビット演算子だけで整数の割り算（余あり）をする方法


下記コードは、割り算の筆算アルゴリズムを2進数でそのまま実装したものです。（C言語を使用）

[code]

    void div(int n, int d)
    {
      int m = 1, q = 0;
      while (d <= n) {
        d <<= 1;
        m <<= 1;
      }
      while (1 < m) {
        d >>= 1;
        m >>= 1;
        if (n >= d) {
          n -= d;
          q |= m;
        }
      }
      // q=商 / n=余り
    }
    
[/code]

LiveDemo: <http://melpon.org/wandbox/permlink/blNO0ai7MChwg4a0>


CC BY-SA 3.0
2014-12-29T13:27:50.603
2800
2014-12-29T13:27:50.603
49
2792
answer


実用性がまるでありませんが、ビット演算子 **のみ** を利用した除算の例です。  
`+`, `-`, 比較演算子, ループは使用していません。

<http://ideone.com/FMuNWh>

[code]

    #include <stdio.h>
    
    char add(char a, char b)
    {
        char r = 0;
        char n = 0;
        r |= (a & 0x1) ^ (b & 0x1);
        n =  (a & 0x1) & (b & 0x1);
        r |= (((a >> 1) & 0x1) ^ ((b >> 1) & 0x1) ^ n) << 1;
        n = (((a >> 1) & 0x1) & ((b >> 1) & 0x1)) | (((a >> 1) & 0x1) & n) | (n & ((b >> 1) & 0x1));
        r |= (((a >> 2) & 0x1) ^ ((b >> 2) & 0x1) ^ n) << 2;
        n = (((a >> 2) & 0x1) & ((b >> 2) & 0x1)) | (((a >> 2) & 0x1) & n) | (n & ((b >> 2) & 0x1));
        r |= (((a >> 3) & 0x1) ^ ((b >> 3) & 0x1) ^ n) << 3;
        n = (((a >> 3) & 0x1) & ((b >> 3) & 0x1)) | (((a >> 3) & 0x1) & n) | (n & ((b >> 3) & 0x1));
        r |= (((a >> 4) & 0x1) ^ ((b >> 4) & 0x1) ^ n) << 4;
        n = (((a >> 4) & 0x1) & ((b >> 4) & 0x1)) | (((a >> 4) & 0x1) & n) | (n & ((b >> 4) & 0x1));
        r |= (((a >> 5) & 0x1) ^ ((b >> 5) & 0x1) ^ n) << 5;
        n = (((a >> 5) & 0x1) & ((b >> 5) & 0x1)) | (((a >> 5) & 0x1) & n) | (n & ((b >> 5) & 0x1));
        r |= (((a >> 6) & 0x1) ^ ((b >> 6) & 0x1) ^ n) << 6;
        n = (((a >> 6) & 0x1) & ((b >> 6) & 0x1)) | (((a >> 6) & 0x1) & n) | (n & ((b >> 6) & 0x1));
        r |= (((a >> 7) & 0x1) ^ ((b >> 7) & 0x1) ^ n) << 7;
        return r;
    }
    
    char sub(char a, char b)
    {
        return add(a, add(~b, 1));
    }
    
    char cmp(char a, char b, char c)
    {
        return (~(add(~add(a, b), add(c, 1)) >> 7)) & 0x1;
    }
    
    char mask(char a)
    {
        return (a | a << 1 | a << 2 | a << 3 | a << 4 | a << 5 | a << 6 | a << 7);
    }
    
    char ds(char *sum, char *d, char *r, char a, char b)
    {
        char c = cmp(*sum, b, a); *d = add(*d, c); *sum = add(*sum, b & mask(c)); *r = sub(*r, b & mask(c));
    }
    
    char ds8(char *sum, char *d, char *r, char a, char b)
    {
        ds(sum, d, r, a, b); ds(sum, d, r, a, b); ds(sum, d, r, a, b); ds(sum, d, r, a, b);
        ds(sum, d, r, a, b); ds(sum, d, r, a, b); ds(sum, d, r, a, b); ds(sum, d, r, a, b);
    }
    
    char ds128(char *sum, char *d, char *r, char a, char b)
    {
        ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b);
        ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b);
        ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b);
        ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b); ds8(sum, d, r, a, b);
    }
    
    char div(char a, char b, char *r)
    {
        char sum = 0, d = 0;
        *r = a;
        ds128(&sum, &d, r, a, b); 
        return d;
    }
    
    int main(void) {
        int a, b;
        char reminder, division;
        scanf("%d / %d", &a, &b);
        division = div(a, b, &reminder);
        printf("%d / %d = %d (%d)", a, b, division, reminder);
        return 0;
    }
    
[/code]


CC BY-SA 3.0
2014-12-30T04:17:49.387
2814
2014-12-30T04:17:49.387
3639
2792
answer