+ 연산자를 사용하지 않고 두 개의 숫자를 추가하는 가장 좋은 방법은 무엇입니까?
https://stackoverflow.com/questions/365522
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
친구와 나는 뇌 티저와 함께 앞뒤로 가고 있으며 이것을 어떻게 해결 해야할지 전혀 모른다. 내 가정은 약간의 연산자에게는 가능하지만 확실하지 않다고 가정합니다.
해결책
비트 타이어 운영자와 함께 C에서 :
#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 각 비트의 휴대입니다.
루프는 모든 비트에 대해 캐리가 0이 될 때까지 캐리를 계속 추가합니다.
다른 팁
int add(int a, int b) {
const char *c=0;
return &(&c[a])[b];
}
아니요 + 맞습니까?
int add(int a, int b)
{
return -(-a) - (-b);
}
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;
}
"최고"를 정의합니다. 파이썬 버전은 다음과 같습니다.
len(range(x)+range(y))
그만큼 + 추가가 아닌 목록 연결을 수행합니다.
Bitwise 연산자가있는 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;
}
속이다. 숫자를 무효화하고 첫 번째로부터 빼낼 수 있습니다 :)
실패, 이진 가산기가 어떻게 작동하는지 찾아보십시오. :)
편집 : 아, 내가 게시 한 후 댓글을 보았습니다.
이진 첨가에 대한 세부 사항이 있습니다 여기.
참고, 이것은 잔물결 전환 가산기, 작동하지만 최적으로 수행되지 않습니다. 하드웨어에 내장 된 대부분의 이진 부가자는 캐리가 된 가산기.
Ripple-Carry Adder는 Unsigned와 2의 보완 정수 모두에 대해 작동하고 Carry_in을 0으로 설정하고 1의 보완 정수가 1으로 설정되어있는 경우 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;
}
두 번째 숫자만큼 자주 첫 번째 숫자를 인간 마케팅하지 않겠습니까?
ADD가 어셈블러에서 비트 동작의 일부 조합이 아니라 단일 명령으로 구현되는 이유는하기가 어렵 기 때문입니다. 주어진 낮은 주문 비트에서 다음 상위 주문 비트까지 캐리에 대해 걱정해야합니다. 이것은 기계가 하드웨어로 빠르게하는 일이지만 C를 사용하더라도 소프트웨어로 빠르게 할 수는 없습니다.
두 정수를 추가하는 것은 그리 어렵지 않습니다. 이진 추가의 온라인에 대한 많은 예가 있습니다.
더 어려운 문제는 부동 소수점 번호입니다! 예제가 있습니다 http://pages.cs.wisc.edu/~smoler/x86text/lect.notes/arith.flpt.html
Bitwise 연산자를 사용하는 파이썬에서 :
def sum_no_arithmetic_operators(x,y):
while True:
carry = x & y
x = x ^ y
y = carry << 1
if y == 0:
break
return x
C# 에서이 문제를 직접 작업하고 있었고 모든 테스트 사례를 통과 할 수는 없었습니다. 그런 다음 건너 뛰었습니다 이것.
다음은 C# 6의 구현입니다.
public int Sum(int a, int b) => b != 0 ? Sum(a ^ b, (a & b) << 1) : a;
종이에 이진을 추가 할 수있는 것과 같은 방식으로 구현되었습니다.
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);
}
코딩 인터뷰에서 이것을 문제 18.1로 보았습니다. 내 파이썬 솔루션 :
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)
이 방법은 반복을 사용하므로 시간 복잡성은 최적이 아닙니다. 가장 좋은 방법은 비트 운영으로 낮은 수준에서 일하는 것입니다.
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
비트 시프트 및 작업을 사용하여 수행 할 수 있습니다.
#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;
}
입력이 반대 부호 인 경우 가장 투표 된 답변은 작동하지 않습니다. 그러나 다음은 할 것입니다. 나는 한 곳에서 속임수를 썼지 만 코드를 약간 깨끗하게 유지하기 위해서만. 개선을위한 모든 제안을 환영합니다
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
다음은 휴대용 한 줄 3 배 및 재귀 솔루션입니다.
int add(int x, int y) {
return y == 0 ? x : add(x ^ y, (x & y) << 1);
}
파이썬 코드 : (1)
add = lambda a,b : -(-a)-(-b)
'-'연산자와 함께 Lambda 기능을 사용하십시오
(2)
add= lambda a,b : len(list(map(lambda x:x,(i for i in range(-a,b)))))
