Was ist der beste Weg, um zwei Zahlen zu addieren, ohne den + Operator?
https://stackoverflow.com/questions/365522
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ein Freund und ich gehen hin und her mit Knobelaufgaben und ich habe keine Ahnung, wie diese zu lösen. Meine Vermutung ist, dass es mit einigen Bitoperatoren möglich ist, aber nicht sicher.
Lösung
In C, mit Bit-Operatoren:
#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) ist zusätzlich ohne Übertrag. (x & y) ist die Carry-out von jedem Bit. (x & y) << 1 ist der Übertrag in jedem Bit.
Die Schleife hält die Zugabe trägt, bis der Übertrag Null für alle Bits.
Andere Tipps
int add(int a, int b) {
const char *c=0;
return &(&c[a])[b];
}
Nein + oder?
int add(int a, int b)
{
return -(-a) - (-b);
}
CMS add () Funktion ist schön. Es soll nicht von einstelliger Negation (: -y == (~ y) +1 eine nicht-bitweise Operation, gleichbedeutend mit der Verwendung von Zusatz) besudelt werden. Also hier ist eine Subtraktion Funktion die gleiche bitweise-only-Design mit:
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;
}
Define "best". Hier ist eine Python-Version:
len(range(x)+range(y))
Die + führt Liste Verkettung, nicht zusätzlich.
Java Lösung mit Bit-Operatoren:
// 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;
}
Cheat. Sie konnten die Zahl negieren und subtrahieren sie von der ersten:)
, dass Failing, nachschauen, wie ein binären Addierer funktioniert. :)
EDIT: Ah, sah Ihren Kommentar, nachdem ich gepostet
.Details von Binäraddition sind hier .
Beachten Sie, würde dies als eine Ripple-carry bekannt für einen Addierer sein Addierer , der arbeitet, führt aber nicht optimal. Die meisten Binäraddierer in Hardware aufgebaut sind eine Form von schnellen Addierer wie ein Carry-Look-Ahead-Addierer .
Meine Ripple-Carry-Addierer funktioniert sowohl für unsigned und Komplement ganze Zahlen von 2, wenn Sie auf 0 gesetzt carry_in und 1-Komplement-Zahlen, wenn carry_in auf 1 gesetzt ist ich auch Flags hinzugefügt Unter- oder Überlauf bei der Zugabe zu zeigen.
#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;
}
Warum nicht einfach die erste Nummer incremet so oft, wie die zweite Nummer?
Der Grund ADD ist in Assembler als einen einzigen Befehl implememted, anstatt als eine Kombination von Bit-Operationen, ist, dass es schwer ist, zu tun. Sie müssen sich Sorgen über die Überträge von einem gegebenen Bit niedriger Ordnung in die nächsthöhere Bit. Dies ist Zeug, dass die Maschinen in der Hardware zwar schnell, aber das auch mit C, Sie können in der Software schnell nicht tun.
Hinzufügen von zwei ganzen Zahlen ist nicht so schwierig; Es gibt viele Beispiele für binäre Addition online.
Ein schwieriges Problem ist Gleitkommazahlen! Es ist ein Beispiel unter http: //pages.cs .wisc.edu / ~ Smoler / x86text / lect.notes / arith.flpt.html
In Python mit Bit-Operatoren:
def sum_no_arithmetic_operators(x,y):
while True:
carry = x & y
x = x ^ y
y = carry << 1
if y == 0:
break
return x
Wurde die Arbeit für dieses Problem selbst in C # und nicht alle Testfälle passieren konnte. Ich lief dann über diese .
Hier ist eine Implementierung in C # 6:
public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a;
in gleicher Weise implementiert, wie wir Binäraddition auf Papier tun könnten.
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);
}
Verbesserte für Geschwindigkeit unter wäre ::
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);
}
Ich sah dies als Problem 18.1 in der Codierung Interview. Meine Python-Lösung:
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)
Diese Methode verwendet Iteration, so dass die Zeitkomplexität ist nicht optimal. Ich glaube, der beste Weg ist, auf einer niedrigeren Ebene mit bitweise Operationen zu arbeiten.
Es ist meine Implementierung auf Python. Es funktioniert gut, wenn wir die Anzahl von Bytes (oder Bits) kennen.
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
Sie können es mit Bitverschiebung und der UND-Verknüpfung.
#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;
}
Die meisten Stimmen Antwort wird nicht funktionieren, wenn die Eingänge von entgegengesetztem Vorzeichen sind. Die folgende jedoch wird. Ich habe an einem Ort betrogen, sondern nur den Code ein wenig sauber zu halten. Irgendwelche Vorschläge für Verbesserungen willkommen
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
Hier ist eine tragbare einzeilige ternäre und rekursive Lösung.
int add(int x, int y) {
return y == 0 ? x : add(x ^ y, (x & y) << 1);
}
Python-Codes: (1)
add = lambda a,b : -(-a)-(-b)
Verwendung Lambda-Funktion mit '-' Operator
(2)
add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b)))))
