Comment ajouter deux nombres sans utiliser ++ ou + ou un autre opérateur arithmétique

Question

Comment puis-je additionner deux nombres sans utiliser ++ ou + ou tout autre opérateur arithmétique?

C'était une question posée il y a longtemps, dans certains campus entrevue. De toute façon, aujourd'hui, quelqu'un a posé une question à propos de certains des bits de manipulations, et dans les réponses une belle quide Stanford peu tripoter a été renvoyé. J'ai passer un peu de temps à l'étude et de la pensée qu'il y a effectivement peut-être une réponse à la question. Je ne sais pas, je ne pouvais pas en trouver un. Une réponse existe pas?

Answer 1

C’est quelque chose que j’ai écrit il ya quelque temps pour le plaisir. Il utilise la représentation d'un complément à deux et implémente l'addition en utilisant des décalages répétés avec un bit de retenue, implémentant d'autres opérateurs principalement en termes d'addition.

 #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;
}
 

Answer 2

Ou, plutôt que de Jason au niveau du bit approche, vous pouvez calculer le nombre de bits en parallèle, cela devrait fonctionner beaucoup plus rapidement avec un grand nombre. À chaque étape, figure hors du porter partie et la partie qui est somme. Vous tentez d'ajouter le porter à la somme, ce qui pourrait provoquer un risque de contamination de nouveau - d'où la boucle.

>>> 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

lorsque vous ajoutez 1 et 3, les deux nombres ont le 1 ensemble de bits, de sorte que la somme de 1+1 porte. L'étape suivante, vous devez ajouter 2 à 2, et qui exerce dans la bonne somme de quatre. Qui provoque une sortie

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

Ou un exemple plus complexe

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

Edit: Pour travailler facilement sur des nombres signés, vous devez introduire une limite supérieure sur a et 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

Essayez-le sur

add(-1, 1)

pour voir d'un seul bit de transporter jusqu'à travers l'ensemble de la gamme et de dépassement de plus de 32 itérations

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

Answer 3

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

Answer 4

Vous pouvez transformer un circuit additionneur en un algorithme. Ils ne font que des opérations au niveau des bits =)

Answer 5

Bien, implémenter un équivalent avec des opérateurs booléens est assez simple: vous faites une somme bit par bit (qui est un XOR), avec une retenue (qui est un AND). Comme ça:

 int sum(int value1, int value2)
{
	int result = 0;
	int carry = 0;
	for (int mask = 1; mask != 0; mask <<= 1)
	{
		int bit1 = value1 & mask;
		int bit2 = value2 & mask;
		result |= mask & (carry ^ bit1 ^ bit2);
		carry = ((bit1 & bit2) | (bit1 & carry) | (bit2 & carry)) << 1;
	}
	return result;
}