++ 또는 + 또는 다른 산술 연산자를 사용하지 않고 두 숫자를 추가하는 방법
++ 또는 + 또는 다른 산술 연산자를 사용하지 않고 두 숫자를 더하려면 어떻게 해야 합니까?
그것은 오래 전에 어떤 캠퍼스 인터뷰에서 물어본 질문이었다.어쨌든, 오늘 누군가가 비트 조작에 관한 질문을 했고, 답변에는 아름다운 스탠포드 비트 트위들링이 언급되었다.나는 그것을 연구하면서 실제로 그 질문에 대한 답이 있을지도 모른다고 생각했다.모르겠어요, 못 찾겠어요.답은 존재하는가?
이것은 제가 예전에 재미로 쓴 것입니다.2의 보완 표현을 사용하고, 캐리어 비트로 반복 시프트를 사용하여 덧셈을 구현하며, 주로 덧셈 측면에서 다른 연산자를 구현합니다.
#include <stdlib.h> /* atoi() */
#include <stdio.h> /* (f)printf */
#include <assert.h> /* assert() */
int add(int x, int y) {
int carry = 0;
int result = 0;
int i;
for(i = 0; i < 32; ++i) {
int a = (x >> i) & 1;
int b = (y >> i) & 1;
result |= ((a ^ b) ^ carry) << i;
carry = (a & b) | (b & carry) | (carry & a);
}
return result;
}
int negate(int x) {
return add(~x, 1);
}
int subtract(int x, int y) {
return add(x, negate(y));
}
int is_even(int n) {
return !(n & 1);
}
int divide_by_two(int n) {
return n >> 1;
}
int multiply_by_two(int n) {
return n << 1;
}
int multiply(int x, int y) {
int result = 0;
if(x < 0 && y < 0) {
return multiply(negate(x), negate(y));
}
if(x >= 0 && y < 0) {
return multiply(y, x);
}
while(y > 0) {
if(is_even(y)) {
x = multiply_by_two(x);
y = divide_by_two(y);
} else {
result = add(result, x);
y = add(y, -1);
}
}
return result;
}
int main(int argc, char **argv) {
int from = -100, to = 100;
int i, j;
for(i = from; i <= to; ++i) {
assert(0 - i == negate(i));
assert(((i % 2) == 0) == is_even(i));
assert(i * 2 == multiply_by_two(i));
if(is_even(i)) {
assert(i / 2 == divide_by_two(i));
}
}
for(i = from; i <= to; ++i) {
for(j = from; j <= to; ++j) {
assert(i + j == add(i, j));
assert(i - j == subtract(i, j));
assert(i * j == multiply(i, j));
}
}
return 0;
}
또는 Jason의 비트 단위 접근 방식이 아니라 여러 비트를 병렬로 계산할 수 있습니다. 이 방법은 숫자가 클수록 훨씬 더 빠르게 실행됩니다.각 단계에서 반송 부품과 합계를 구합니다.합계에 반송파를 추가하려고 하면 반송파가 다시 발생할 수 있으므로 루프가 발생합니다.
>>> def add(a, b):
while a != 0:
# v carry portion| v sum portion
a, b = ((a & b) << 1), (a ^ b)
print b, a
return b
1과 3을 더하면 두 숫자 모두 1비트가 설정되기 때문에 1+1의 합이 전달됩니다.다음 단계는 2에 2를 더하면 정확한 합계가 4가 됩니다.그것이 출구의 원인이 된다.
>>> add(1,3)
2 2
4 0
4
또는 보다 복잡한 예
>>> add(45, 291)
66 270
4 332
8 328
16 320
336
편집: 서명된 번호로 쉽게 작동하려면 a와 b의 상한을 설정해야 합니다.
>>> def add(a, b):
while a != 0:
# v carry portion| v sum portion
a, b = ((a & b) << 1), (a ^ b)
a &= 0xFFFFFFFF
b &= 0xFFFFFFFF
print b, a
return b
입어보세요
add(-1, 1)
전체 범위에 걸쳐 하나의 비트가 전송되고 32회 이상 오버플로가 발생하는 것을 확인합니다.
4294967294 2
4294967292 4
4294967288 8
...
4294901760 65536
...
2147483648 2147483648
0 0
0L
int Add(int a, int b)
{
while (b)
{
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
가산기 회로를 알고리즘으로 변환할 수 있습니다.비트 연산만 수행합니다 =).
부울 연산자를 사용하여 동등한 기능을 구현하는 것은 매우 간단합니다. 즉, 비트별 합계(XOR)와 자리올림(AND)을 사용합니다.다음과 같이 합니다.
int sum(int value1, int value2)
{
int result = 0;
int carry = 0;
for (int mask = 1; mask != 0; mask <<= 1)
{
int bit1 = value1 & mask;
int bit2 = value2 & mask;
result |= mask & (carry ^ bit1 ^ bit2);
carry = ((bit1 & bit2) | (bit1 & carry) | (bit2 & carry)) << 1;
}
return result;
}
당신은 이미 몇 가지 조작에 대한 답을 가지고 있습니다.여기 뭔가 다른 게 있어요.
주식회사,arr[ind] == *(arr + ind)이것에 의해, 다음과 같은 약간 혼란스러운(그러나 법률적인) 작업을 실시할 수 있습니다.int arr = { 3, 1, 4, 5 }; int val = 0[arr];.
따라서 (산술 연산자를 명시적으로 사용하지 않고) 다음과 같이 사용자 정의 추가 함수를 정의할 수 있습니다.
unsigned int add(unsigned int const a, unsigned int const b)
{
/* this works b/c sizeof(char) == 1, by definition */
char * const aPtr = (char *)a;
return (int) &(aPtr[b]);
}
또는 이 트릭을 피하고 싶은 경우, 그리고 산술 연산자에 의해 다음이 포함되는 경우,|,&,그리고.^ 테이블에서 할 수
typedef unsigned char byte;
const byte lut_add_mod_256[256][256] = {
{ 0, 1, 2, /*...*/, 255 },
{ 1, 2, /*...*/, 255, 0 },
{ 2, /*...*/, 255, 0, 1 },
/*...*/
{ 254, 255, 0, 1, /*...*/, 253 },
{ 255, 0, 1, /*...*/, 253, 254 },
};
const byte lut_add_carry_256[256][256] = {
{ 0, 0, 0, /*...*/, 0 },
{ 0, 0, /*...*/, 0, 1 },
{ 0, /*...*/, 0, 1, 1 },
/*...*/
{ 0, 0, 1, /*...*/, 1 },
{ 0, 1, 1, /*...*/, 1 },
};
void add_byte(byte const a, byte const b, byte * const sum, byte * const carry)
{
*sum = lut_add_mod_256[a][b];
*carry = lut_add_carry_256[a][b];
}
unsigned int add(unsigned int a, unsigned int b)
{
unsigned int sum;
unsigned int carry;
byte * const aBytes = (byte *) &a;
byte * const bBytes = (byte *) &b;
byte * const sumBytes = (byte *) ∑
byte * const carryBytes = (byte *) &carry;
byte const test[4] = { 0x12, 0x34, 0x56, 0x78 };
byte BYTE_0, BYTE_1, BYTE_2, BYTE_3;
/* figure out endian-ness */
if (0x12345678 == *(unsigned int *)test)
{
BYTE_0 = 3;
BYTE_1 = 2;
BYTE_2 = 1;
BYTE_3 = 0;
}
else
{
BYTE_0 = 0;
BYTE_1 = 1;
BYTE_2 = 2;
BYTE_3 = 3;
}
/* assume 4 bytes to the unsigned int */
add_byte(aBytes[BYTE_0], bBytes[BYTE_0], &sumBytes[BYTE_0], &carryBytes[BYTE_0]);
add_byte(aBytes[BYTE_1], bBytes[BYTE_1], &sumBytes[BYTE_1], &carryBytes[BYTE_1]);
if (carryBytes[BYTE_0] == 1)
{
if (sumBytes[BYTE_1] == 255)
{
sumBytes[BYTE_1] = 0;
carryBytes[BYTE_1] = 1;
}
else
{
add_byte(sumBytes[BYTE_1], 1, &sumBytes[BYTE_1], &carryBytes[BYTE_0]);
}
}
add_byte(aBytes[BYTE_2], bBytes[BYTE_2], &sumBytes[BYTE_2], &carryBytes[BYTE_2]);
if (carryBytes[BYTE_1] == 1)
{
if (sumBytes[BYTE_2] == 255)
{
sumBytes[BYTE_2] = 0;
carryBytes[BYTE_2] = 1;
}
else
{
add_byte(sumBytes[BYTE_2], 1, &sumBytes[BYTE_2], &carryBytes[BYTE_1]);
}
}
add_byte(aBytes[BYTE_3], bBytes[BYTE_3], &sumBytes[BYTE_3], &carryBytes[BYTE_3]);
if (carryBytes[BYTE_2] == 1)
{
if (sumBytes[BYTE_3] == 255)
{
sumBytes[BYTE_3] = 0;
carryBytes[BYTE_3] = 1;
}
else
{
add_byte(sumBytes[BYTE_3], 1, &sumBytes[BYTE_3], &carryBytes[BYTE_2]);
}
}
return sum;
}
모든 산술 연산은 NAND, AND, OR 게이트 등을 사용하여 전자제품에서 구현되는 비트 연산으로 분해됩니다.
부호 없는 숫자의 경우 첫 번째 클래스에서 배운 것과 동일한 덧셈 알고리즘을 사용합니다.단, 베이스 10 대신 베이스 2를 사용합니다.3+2(베이스 10), 즉 베이스 2의 11+10의 예:
1 ‹--- carry bit
0 1 1 ‹--- first operand (3)
+ 0 1 0 ‹--- second operand (2)
-------
1 0 1 ‹--- total sum (calculated in three steps)
만약 여러분이 희극적이라고 느낀다면, 부호 없는 두 개의 정수를 더하는 데는 항상 이런 끔찍한 방법이 있습니다.코드 어디에도 산술 연산자가 없습니다.
C#의 경우:
static uint JokeAdder(uint a, uint b)
{
string result = string.Format(string.Format("{{0,{0}}}{{1,{1}}}", a, b), null, null);
return result.Length;
}
C에서 stdio를 사용하는 경우(Microsoft 컴파일러에서는 snprintf를 _snprintf로 대체):
#include <stdio.h>
unsigned int JokeAdder(unsigned int a, unsigned int b)
{
return snprintf(NULL, 0, "%*.*s%*.*s", a, a, "", b, b, "");
}
여기 컴팩트한 C용액이 있습니다.루프보다 재귀가 읽기 쉬운 경우가 있습니다.
int add(int a, int b){
if (b == 0) return a;
return add(a ^ b, (a & b) << 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;
}
short int ripple_adder(short int a, short int b)
{
short int i, c, s, ai, bi;
c = s = 0;
for (i=0; i<16; i++)
{
ai = a & 1;
bi = b & 1;
s |= (((ai ^ bi)^c) << i);
c = (ai & bi) | (c & (ai ^ bi));
a >>= 1;
b >>= 1;
}
s |= (c << i);
return s;
}
## to add or subtract without using '+' and '-' ##
#include<stdio.h>
#include<conio.h>
#include<process.h>
void main()
{
int sub,a,b,carry,temp,c,d;
clrscr();
printf("enter a and b:");
scanf("%d%d",&a,&b);
c=a;
d=b;
while(b)
{
carry=a&b;
a=a^b;
b=carry<<1;
}
printf("add(%d,%d):%d\n",c,d,a);
temp=~d+1; //take 2's complement of b and add it with a
sub=c+temp;
printf("diff(%d,%d):%d\n",c,d,temp);
getch();
}
다음과 같이 하면 됩니다.
x - (-y)
이것은 재귀적으로 실행할 수 있습니다.
int add_without_arithm_recursively(int a, int b)
{
if (b == 0)
return a;
int sum = a ^ b; // add without carrying
int carry = (a & b) << 1; // carry, but don’t add
return add_without_arithm_recursively(sum, carry); // recurse
}
또는 반복:
int add_without_arithm_iteratively(int a, int b)
{
int sum, carry;
do
{
sum = a ^ b; // add without carrying
carry = (a & b) << 1; // carry, but don’t add
a = sum;
b = carry;
} while (b != 0);
return a;
}
add,을 구현하기 위한 , add, multipliation을 하지 않음, add, multipliation을 합니다.+ ,*의 경우 숫자의 +을 뺄셈에 합니다. 뺄셈 통과 1의 +1의 숫자에서 뺄셈 통과의 경우add
#include<stdio.h>
unsigned int add(unsigned int x,unsigned int y)
{
int carry=0;
while (y != 0)
{
carry = x & y;
x = x ^ y;
y = carry << 1;
}
return x;
}
int multiply(int a,int b)
{
int res=0;
int i=0;
int large= a>b ? a :b ;
int small= a<b ? a :b ;
for(i=0;i<small;i++)
{
res = add(large,res);
}
return res;
}
int main()
{
printf("Sum :: %u,Multiply is :: %d",add(7,15),multiply(111,111));
return 0;
}
질문에서 두 숫자를 어떻게 더해야 하는지 묻는데 왜 모든 솔루션이 두 정수를 더해야 하는지 이해가 안 가네요.약약면면면면면면면면면면면? 2.3 + 1.8한한 숫자 ?주 주? ???문제를 수정하거나 답변을 수정해야 합니다.
플로트의 경우 숫자를 구성 요소로 세분해야 합니다. 2.3 = 2 + 0.3 0.3는 그 0.3 = 3 * 10^-1다른 숫자에 대해서도 동일한 작업을 수행한 다음 처리 상황 위의 해결책으로 주어진 비트 시프트 방법 중 하나를 사용하여 정수 세그먼트를 추가합니다. 2.7 + 3.3 = 6.0 = 2+3+0.7+0.3 = 2 + 3 + 7x10^-1 + 3x10^-1 = 2 + 3 + 10^10^-1은 두 의 덧셈(즉, 2개의 덧셈, 의 덧셈)으로 취급할 수 .2+3=5 다음에 또 한 번.5+1=6
상기의 회답에서는, 1 행의 코드로 실시할 수 있습니다.
int add(int a, int b) {
return (b == 0) ? a : add(a ^ b, (a & b) << 1);
}
예를 들어 double negetive를 사용하여 두 개의 정수를 추가할 수 있습니다.
int sum2(int a, int b){
return -(-a-b);
}
연산자를 사용하지 않고 다음과 같이 두 정수를 추가할 수 있습니다.
int sum_of_2 (int a, int b){
int sum=0, carry=sum;
sum =a^b;
carry = (a&b)<<1;
return (b==0)? a: sum_of_2(sum, carry);
}
// Or you can just do it in one line as follows:
int sum_of_2 (int a, int b){
return (b==0)? a: sum_of_2(a^b, (a&b)<<1);
}
// OR you can use the while loop instead of recursion function as follows
int sum_of_2 (int a, int b){
if(b==0){
return a;
}
while(b!=0){
int sum = a^b;
int carry = (a&b)<<1;
a= sum;
b=carry;
}
return a;
}
int add_without_arithmatic(int a, int b)
{
int sum;
char *p;
p = (char *)a;
sum = (int)&p[b];
printf("\nSum : %d",sum);
}
언급URL : https://stackoverflow.com/questions/1149929/how-to-add-two-numbers-without-using-or-or-another-arithmetic-operator
'programing' 카테고리의 다른 글
| Vue.js - 요소 UI - 변경 중단 드롭다운 개체 및 값 키 선택 (0) | 2022.07.16 |
|---|---|
| Django 및 Vue.js를 {% verbatim %}과(와) 연동시키다 (0) | 2022.07.12 |
| 휴지 상태: hbm2dl.auto=업데이트를 실가동 중입니까? (0) | 2022.07.12 |
| v-를 사용하여 개체 사용을 위한 선택 옵션 생성 (0) | 2022.07.12 |
| Java 8 lamda Void 인수 (0) | 2022.07.12 |