Мы с другом идем взад и вперед с мозгами-тизерами, и я понятия не имею, как решить эту проблему. Мое предположение заключается в том, что это возможно с некоторыми побитовыми операторами, но не уверенными.
Каков наилучший способ добавить два числа без использования оператора +?
Ответ 1
В Си с побитовыми операторами:
#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
) - сложение без переноса. (x & y)
- вынос от каждого бита. (x & y) << 1
- это перенос каждого бита.
Цикл продолжает добавлять переносы, пока перенос не станет нулевым для всех битов.
Ответ 2
int add(int a, int b) {
const char *c=0;
return &(&c[a])[b];
}
Ответ 3
Нет + правильно?
int add(int a, int b)
{
return -(-a) - (-b);
}
Ответ 4
Определите "лучший". Здесь версия python:
len(range(x)+range(y))
+
выполняет конкатенацию списка, а не добавление.
Ответ 5
Функция CMS add() прекрасна. Это не должно быть омрачено унарным отрицанием (небитовая операция, равносильная использованию сложения: -y == (~ y) +1). Итак, здесь функция вычитания с использованием той же побитовой конструкции:
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;
}
Ответ 6
Чит. Вы можете отменить это число и вычесть его из первого:)
В противном случае посмотрите, как работает двоичный сумматор.:)
РЕДАКТИРОВАТЬ: Ах, увидели ваш комментарий после того, как я опубликовал.
Подробности двоичного добавления здесь.
Ответ 7
Обратите внимание, что это будет для сумматора, известного как сумматор-переносчик, который работает, но не работает оптимально. Большинство двоичных сумматоров, встроенных в аппаратные средства, представляют собой быстрые сумматоры, такие как сумматор с упреждением.
Мой сумматор с неравномерным переносом работает как для целых чисел без знака, так и для 2 целых чисел с дополнением, если вы установили значение 0 для carry_in, и для целых чисел 1 с дополнением, если для параметра carry_in установлено значение 1. Я также добавил флаги, чтобы отобразить переполнение или переполнение при добавлении.
#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;
}
Ответ 8
Java-решение с побитовыми операторами:
// 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;
}
Ответ 9
Почему бы просто не увеличивать первое число так часто, как второе число?
Ответ 10
Причина, по которой ADD реализуется в ассемблере как одна команда, а не как некоторая комбинация побитовых операций, заключается в том, что это трудно сделать. Вы должны беспокоиться о переносах от заданного младшего бита к следующему бит более высокого порядка. Это то, что машины делают в аппаратном обеспечении быстро, но даже с помощью C вы не можете быстро делать это в программном обеспечении.
Ответ 11
Добавление двух целых чисел не так сложно; есть много примеров бинарного добавления в Интернете.
Более сложной проблемой являются числа с плавающей запятой! Вот пример в http://pages.cs.wisc.edu/~smoler/x86text/lect.notes/arith.flpt.html
Ответ 12
В питоне используются побитовые операторы:
def sum_no_arithmetic_operators(x,y):
while True:
carry = x & y
x = x ^ y
y = carry << 1
if y == 0:
break
return x
Ответ 13
Вы можете сделать это, используя сдвиг битов и операцию 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;
}
Ответ 14
Реализовано так же, как мы могли бы сделать двоичное добавление на бумаге.
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);
}
Улучшено для скорости будет ниже ::
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);
}
Ответ 15
Я видел это как проблему 18.1 в интервью по кодированию. Мое решение на 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)
Этот метод использует итерацию, поэтому временная сложность не является оптимальной. Я считаю, что лучший способ - работать на более низком уровне с побитовыми операциями.
Ответ 16
Сама работала над этой проблемой на С# и не могла пройти все тестовые примеры. Затем я столкнулся с .
Вот реализация на С# 6:
public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a;
Ответ 17
Это моя реализация на Python. Это хорошо работает, когда мы знаем количество байтов (или бит).
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
Ответ 18
Ответ с наибольшим количеством голосов не будет работать, если входные данные имеют противоположный знак. Следующее однако будет. Я обманул в одном месте, но только чтобы сохранить код немного чистым. Любые предложения по улучшению приветствуются
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
Ответ 19
Здесь портативное однострочное троичное и рекурсивное решение.
int add(int x, int y) {
return y == 0 ? x : add(x ^ y, (x & y) << 1);
}
Ответ 20
Решение на основе Go
func add(a int, b int) int {
for {
carry := (a & b) << 1
a = a ^ b
b = carry
if b == 0 {
break
}
}
return a
}
то же решение может быть реализовано в Python следующим образом, но есть некоторая проблема с представлением чисел в Python, Python имеет более 32 битов для целых чисел. поэтому мы будем использовать маску для получения последних 32 бит.
Например: если мы не используем маску, мы не получим результат для чисел (-1, 1)
def add(a,b):
mask = 0xffffffff
while b & mask:
carry = a & b
a = a ^ b
b = carry << 1
return (a & mask) if b > mask else a
Ответ 21
Коды Python: (1)
add = lambda a,b : -(-a)-(-b)
использовать лямбда-функцию с оператором '-'
(2)
add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b)))))