Qual è il modo migliore per aggiungere due numeri senza utilizzare l’operatore +?

Un amico e io stiamo andando avanti e indietro con rompicapi e non ho idea di come risolvere questo. La mia ipotesi è che sia ansible con alcuni operatori bit a bit, ma non è sicuro.

In C, con operatori bit a bit:

#include int add(int x, int y) { int a, b; do { a = x & y; b = x ^ y; x = a << 1; y = b; } while (a); return b; } int main( void ){ printf( "2 + 3 = %d", add(2,3)); return 0; } 

XOR ( x ^ y ) è un'aggiunta senza carry. (x & y) è il riporto da ogni bit. (x & y) << 1 è il carry-in per ogni bit.

Il loop continua ad aggiungere il carry fino a quando il carry è zero per tutti i bit.

 int add(int a, int b) { const char *c=0; return &(&c[a])[b]; } 

No + giusto?

 int add(int a, int b) { return -(-a) - (-b); } 

Definisci “migliore”. Ecco una versione python:

 len(range(x)+range(y)) 

Il + esegue la concatenazione dell’elenco, non l’aggiunta.

La funzione add () di CMS è bellissima. Non dovrebbe essere imbrogliato dalla negazione unaria (un’operazione non bit a bit, equivale a utilizzare l’aggiunta: -y == (~ y) +1). Quindi, ecco una funzione di sottrazione usando lo stesso design bitwise-only:

 int sub(int x, int y) { unsigned a, b; do { a = ~x & y; b = x ^ y; x = b; y = a << 1; } while (a); return b; } 

Soluzione Java con operatori bit a bit:

 // Recursive solution public static int addR(int x, int y) { if (y == 0) return x; int sum = x ^ y; //SUM of two integer is X XOR Y int carry = (x & y) << 1; //CARRY of two integer is X AND Y return addR(sum, carry); } //Iterative solution public static int addI(int x, int y) { while (y != 0) { int carry = (x & y); //CARRY is AND of two bits x = x ^ y; //SUM of two bits is X XOR Y y = carry << 1; //shifts carry to 1 bit to calculate sum } return x; } 

Truffare. Potresti annullare il numero e sottrarlo dal primo 🙂

In caso contrario, guarda come funziona un addizionatore binario. 🙂

EDIT: Ah, ho visto il tuo commento dopo che ho postato.

I dettagli dell’aggiunta binaria sono qui .

Nota, questo sarebbe per un sumtore noto come un sumtore trasporta-ripple , che funziona, ma non ha prestazioni ottimali. La maggior parte dei sumtori binari integrati nell’hardware sono una forma di addizionatore veloce come un addetto al carry-look-ahead .

Il mio addizionatore ripple-carry funziona sia per interi senza complemento che per complementi a 2 se si imposta carry_in su 0 e gli interi del complemento a 1 se carry_in è impostato su 1. Ho aggiunto anche flag per mostrare underflow o overflow sull’aggiunta.

 #define BIT_LEN 32 #define ADD_OK 0 #define ADD_UNDERFLOW 1 #define ADD_OVERFLOW 2 int ripple_add(int a, int b, char carry_in, char* flags) { int result = 0; int current_bit_position = 0; char a_bit = 0, b_bit = 0, result_bit = 0; while ((a || b) && current_bit_position < BIT_LEN) { a_bit = a & 1; b_bit = b & 1; result_bit = (a_bit ^ b_bit ^ carry_in); result |= result_bit << current_bit_position++; carry_in = (a_bit & b_bit) | (a_bit & carry_in) | (b_bit & carry_in); a >>= 1; b >>= 1; } if (current_bit_position < BIT_LEN) { *flags = ADD_OK; } else if (a_bit & b_bit & ~result_bit) { *flags = ADD_UNDERFLOW; } else if (~a_bit & ~b_bit & result_bit) { *flags = ADD_OVERFLOW; } else { *flags = ADD_OK; } return result; } 

Perché non incremetare il primo numero più spesso, come il secondo numero?

La ragione per cui ADD viene implementata nell’assembler come una singola istruzione, piuttosto che come una combinazione di operazioni bit a bit, è che è difficile da fare. Devi preoccuparti del trasferimento da un dato bit di ordine basso al successivo bit di ordine superiore. Questo è ciò che le macchine fanno velocemente nell’hardware, ma anche con C non si può fare in fretta il software.

Aggiungere due interi non è così difficile; ci sono molti esempi di aggiunte binarie online.

Un problema più impegnativo sono i numeri in virgola mobile! C’è un esempio su http://pages.cs.wisc.edu/~smoler/x86text/lect.notes/arith.flpt.html

Stavo lavorando su questo problema io stesso in C # e non ho potuto far passare tutti i casi di test. Ho quindi incontrato questo .

Ecco un’implementazione in C # 6:

 public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a; 

Implementato nello stesso modo in cui potremmo fare aggiunte binarie su carta.

 int add(int x, int y) { int t1_set, t2_set; int carry = 0; int result = 0; int mask = 0x1; while (mask != 0) { t1_set = x & mask; t2_set = y & mask; if (carry) { if (!t1_set && !t2_set) { carry = 0; result |= mask; } else if (t1_set && t2_set) { result |= mask; } } else { if ((t1_set && !t2_set) || (!t1_set && t2_set)) { result |= mask; } else if (t1_set && t2_set) { carry = 1; } } mask <<= 1; } return (result); } 

Migliorata per la velocità sarebbe sotto ::

 int add_better (int x, int y) { int b1_set, b2_set; int mask = 0x1; int result = 0; int carry = 0; while (mask != 0) { b1_set = x & mask ? 1 : 0; b2_set = y & mask ? 1 : 0; if ( (b1_set ^ b2_set) ^ carry) result |= mask; carry = (b1_set & b2_set) | (b1_set & carry) | (b2_set & carry); mask <<= 1; } return (result); } 

Ho visto questo come problema 18.1 nell’intervista di codifica. La mia soluzione python:

 def foo(a, b): """iterate through a and b, count iteration via a list, check len""" x = [] for i in range(a): x.append(a) for i in range(b): x.append(b) print len(x) 

Questo metodo utilizza l’iterazione, quindi la complessità temporale non è ottimale. Credo che il modo migliore sia lavorare a un livello inferiore con operazioni bit a bit.

È la mia implementazione su Python. Funziona bene, quando conosciamo il numero di byte (o bit).

 def summ(a, b): #for 4 bytes(or 4*8 bits) max_num = 0xFFFFFFFF while a != 0: a, b = ((a & b) << 1), (a ^ b) if a > max_num: b = (b&max_num) break return b 

Puoi farlo usando il bit shifting e l’operazione AND.

 #include  int main() { unsigned int x = 3, y = 1, sum, carry; sum = x ^ y; // Ex - OR x and y carry = x & y; // AND x and y while (carry != 0) { carry = carry << 1; // left shift the carry x = sum; // initialize x as sum y = carry; // initialize y as carry sum = x ^ y; // sum is calculated carry = x & y; /* carry is calculated, the loop condition is evaluated and the process is repeated until carry is equal to 0. */ } printf("%d\n", sum); // the program will print 4 return 0; } 

La risposta più votata non funzionerà se gli input sono di segno opposto. Il seguente tuttavia lo farà. Ho truffato in un posto, ma solo per mantenere il codice un po ‘pulito. Qualche suggerimento per il miglioramento benvenuto

 def add(x, y): if (x >= 0 and y >= 0) or (x < 0 and y < 0): return _add(x, y) else: return __add(x, y) def _add(x, y): if y == 0: return x else: return _add((x ^ y), ((x & y) << 1)) def __add(x, y): if x < 0 < y: x = _add(~x, 1) if x > y: diff = -sub(x, y) else: diff = sub(y, x) return diff elif y < 0 < x: y = _add(~y, 1) if y > x: diff = -sub(y, x) else: diff = sub(y, x) return diff else: raise ValueError("Invalid Input") def sub(x, y): if y > x: raise ValueError('y must be less than x') while y > 0: b = ~x & y x ^= y y = b << 1 return x 

Codici Python: (1)

 add = lambda a,b : -(-a)-(-b) 

utilizzare la funzione lambda con l’operatore ‘-‘

(2)

 add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b)))))