++ または + または別の算術演算子を使用せずに 2 つの数値を加算する方法

これは私が少し前に趣味で書いたものです。これは 2 の補数表現を使用し、桁上げビットによるシフトの繰り返しを使用して加算を実装し、主に加算に関して他の演算子を実装します。

#include <stdlib.h> /* atoi() */
#include <stdio.h>  /* (f)printf */
#include <assert.h> /* assert() */

int add(int x, int y) {
    int carry = 0;
    int result = 0;
    int i;

    for(i = 0; i < 32; ++i) {
        int a = (x >> i) & 1;
        int b = (y >> i) & 1;
        result |= ((a ^ b) ^ carry) << i;
        carry = (a & b) | (b & carry) | (carry & a);
    }

    return result;
}

int negate(int x) {
    return add(~x, 1);
}

int subtract(int x, int y) {
    return add(x, negate(y));
}

int is_even(int n) {
    return !(n & 1);
}

int divide_by_two(int n) {
    return n >> 1;
}

int multiply_by_two(int n) {
    return n << 1;
}

int multiply(int x, int y) {
    int result = 0;

    if(x < 0 && y < 0) {
        return multiply(negate(x), negate(y));
    }

    if(x >= 0 && y < 0) {
        return multiply(y, x);
    }

    while(y > 0) {
        if(is_even(y)) {
            x = multiply_by_two(x);
            y = divide_by_two(y);
        } else {
            result = add(result, x);
            y = add(y, -1);
        }
    }

    return result;
}

int main(int argc, char **argv) {
    int from = -100, to = 100;
    int i, j;

    for(i = from; i <= to; ++i) {
        assert(0 - i == negate(i));
        assert(((i % 2) == 0) == is_even(i));
        assert(i * 2 == multiply_by_two(i));
        if(is_even(i)) {
            assert(i / 2 == divide_by_two(i));
        }
    }

    for(i = from; i <= to; ++i) {
        for(j = from; j <= to; ++j) {
            assert(i + j == add(i, j));
            assert(i - j == subtract(i, j));
            assert(i * j == multiply(i, j));
        }
    }

    return 0;
}

または、ジェイソンのビットごとのアプローチではなく、多くのビットを並行して計算できます。これは、大きな数ではるかに高速に実行されるはずです。各ステップで、キャリー部分と合計部分を把握します。キャリーを合計に追加しようとすると、再びキャリーが発生する可能性があります - したがって、ループが発生します。

>>> def add(a, b):
    while a != 0:
        #      v carry portion| v sum portion
        a, b = ((a & b) << 1),  (a ^ b)
        print b, a
    return b

1 と 3 を加算すると、両方の数値に 1 ビットが設定されるため、その 1+1 の合計になります。次のステップで 2 を 2 に足すと、正しい合計 4 になります。それは終了を引き起こします

>>> add(1,3)
2 2
4 0
4

またはもっと複雑な例

>>> add(45, 291)
66 270
4 332
8 328
16 320
336

編集: 符号付きの数値で簡単に動作させるには、a と b に上限を導入する必要があります

>>> def add(a, b):
    while a != 0:
        #      v carry portion| v sum portion
        a, b = ((a & b) << 1),  (a ^ b)
        a &= 0xFFFFFFFF
        b &= 0xFFFFFFFF
        print b, a
    return b

試してみる

add(-1, 1)

1 つのビットが範囲全体に繰り上がり、32 回の反復でオーバーフローすることを確認する

4294967294 2
4294967292 4
4294967288 8
...
4294901760 65536
...
2147483648 2147483648
0 0
0L

int Add(int a, int b)
{
    while (b)
    {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}