Qual è il modo migliore per aggiungere due numeri senza utilizzare l'operatore +?
https://stackoverflow.com/questions/365522
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Un amico e io stiamo andando avanti e indietro con rompicapo e non ho idea di come risolvere questo. La mia ipotesi è che è possibile con alcuni operatori bit per bit, ma non è sicuro.
Soluzione
In C, con gli operatori bit per bit:
#include<stdio.h>
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) è aggiunta, senza trasportare. (x & y) è il carry-out da ogni bit. (x & y) << 1 è il carry-in per ogni bit.
Il ciclo continua ad aggiungere la porta finché il riporto è zero per tutti i bit.
Altri suggerimenti
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);
}
del CMS add () è bellissimo. Non dovrebbe essere macchiata da negazione unaria (un'operazione non bit a bit, equivale ad usare aggiunta: == -y (~ y) +1). Quindi, ecco una funzione di sottrazione utilizzando lo stesso disegno bit a bit-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;
}
Definisci "migliore". Ecco una versione python:
len(range(x)+range(y))
Il + esegue lista concatenazione, non oltre.
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;
}
barare. Si potrebbe negare il numero e sottrarre dal primo:)
In mancanza di questo, cercare come un binario funziona vipera. :)
EDIT: Ah, visto il tuo commento dopo che ho postato
.Dettagli di somma binaria sono qui .
Nota, questo sarebbe per una vipera conosciuto come un ripple-carry vipera , che funziona, ma non esegue in modo ottimale. La maggior parte delle vipere binari integrato in hardware sono una forma di vipera veloce, come un carry-look-ahead vipera .
Il mio sommatore ripple-carry funziona sia unsigned e 2 di interi complemento Se si imposta carry_in a 0 e 1 di interi complemento se carry_in è impostato a 1. Ho anche aggiunto bandiere per mostrare underflow o l'overflow con semplice 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 solo incremet il primo numero di volte, come il secondo numero?
Il motivo ADD è implememted in assembler come una singola istruzione, piuttosto che come una combinazione di operazioni bit per bit, è che è difficile da fare. Bisogna preoccuparsi della porta da un dato po 'basso per il prossimo bit di ordine superiore. Questa è roba che le macchine fanno in hardware veloce, ma che anche con C, non si può fare in software veloce.
L'aggiunta di due numeri interi non è poi così difficile; ci sono molti esempi di somma binaria in linea.
Un problema più impegnativo è mobile numeri in virgola! C'è un esempio a http: //pages.cs .wisc.edu / ~ Smoler / x86text / lect.notes / arith.flpt.html
In Python usando operatori bit a bit:
def sum_no_arithmetic_operators(x,y):
while True:
carry = x & y
x = x ^ y
y = carry << 1
if y == 0:
break
return x
stava lavorando su questo problema me stesso in C # e non poteva ottenere tutti i casi di test per passare. Ho poi imbattuto in questo .
Ecco un'implementazione in C # 6:
public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a;
Implementato nel stesso modo in cui si potrebbe fare somma binaria 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 di 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 iterazione, così la complessità temporale non è ottimale. Credo che il modo migliore è quello di lavorare a un livello inferiore con le operazioni bit per bit.
E 'la mia implementazione su Python. Funziona bene, quando sappiamo che 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
È possibile farlo utilizzando bit-shifting e l'operazione AND.
#include <stdio.h>
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ù votato non funzionerà se gli ingressi sono di segno opposto. Il seguente invece si. Ho truffato in un posto, ma solo per mantenere un po 'il codice pulito. Eventuali suggerimenti per il miglioramento di 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
Ecco una soluzione one-line ternario e ricorsivo portatile.
int add(int x, int y) {
return y == 0 ? x : add(x ^ y, (x & y) << 1);
}
codici Python: (1)
add = lambda a,b : -(-a)-(-b)
funzione lambda uso con '-' operatore
(2)
add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b)))))
