Cách thêm hai số không sử dụng ++ hoặc + hoặc toán tử số học khác

Question

Làm cách nào để thêm hai số không sử dụng ++ hoặc + hoặc bất kỳ toán tử số học nào khác?

Đó là câu hỏi được hỏi từ lâu trong một cuộc phỏng vấn trong khuôn viên trường. Dù sao, hôm nay có người hỏi một số câu hỏi liên quan đến một số thao tác bit, và trong câu trả lời một quide đẹp Stanford bit twiddling đã được giới thiệu. Tôi dành chút thời gian để nghiên cứu và nghĩ rằng thực sự có thể là câu trả lời cho câu hỏi. Tôi không biết, tôi không thể tìm được. Câu trả lời có tồn tại không?

Answer 1

Đây là điều mà tôi đã viết một thời gian trước đây cho vui. Nó sử dụng một biểu diễn two's complement và thực hiện bổ sung bằng cách sử dụng các ca lặp đi lặp lại với bit mang, thực hiện các toán tử khác chủ yếu về mặt bổ sung.

#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; 
} 

Answer 2

Bạn có thể chuyển đổi một adder circuit thành một thuật toán. Chúng chỉ thực hiện các thao tác bitwise =)

Answer 3

Tất cả các phép toán số học phân hủy thành các hoạt động bitwise được thực hiện trong các thiết bị điện tử, sử dụng các cổng NAND, AND, OR, vv.

Adder composition can be seen here.

Answer 4

Đối với số unsigned, sử dụng các thuật toán bổ sung tương tự như bạn đã học ở lớp đầu tiên, nhưng đối với cơ sở 2 thay vì cơ sở 10. Ví dụ 3 + 2 (cơ sở 10), tức là 11 + 10 tại cơ sở 2:

1   ‹--- carry bit 
    0 1 1  ‹--- first operand (3) 
+ 0 1 0  ‹--- second operand (2) 
------- 
    1 0 1  ‹--- total sum (calculated in three steps) 

Answer 5

Nếu bạn cảm thấy hài lòng, luôn có cách tiếp cận ngoạn mục ngoạn mục này để thêm hai số nguyên không dấu (tương đối nhỏ). Không có toán tử số học nào trong mã của bạn.

Trong 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; 
} 

Trong C, sử dụng stdio (thay thế snprintf với _snprintf trên trình biên dịch Microsoft):

#include <stdio.h> 
unsigned int JokeAdder(unsigned int a, unsigned int b) 
{ 
    return snprintf(NULL, 0, "%*.*s%*.*s", a, a, "", b, b, ""); 
} 

Answer 6

Sau đây sẽ hoạt động.

x - (-y) 

Answer 7

Hoặc, thay vì cách tiếp cận bitwise của Jason, bạn có thể tính toán nhiều bit song song - điều này sẽ chạy nhanh hơn nhiều với số lượng lớn. Trong mỗi bước tìm ra phần mang và phần là tổng. Bạn cố gắng để thêm carry vào tổng, mà có thể gây ra mang theo một lần nữa - do đó vòng lặp.

>>> 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 

khi bạn thêm 1 và 3, cả hai số đều có 1 bit được đặt, vì vậy tổng số 1 + 1 sẽ mang. Bước tiếp theo bạn thêm từ 2 đến 2 và đưa vào tổng số bốn chính xác.Gây ra một lối ra

>>> add(1,3) 
2 2 
4 0 
4 

Hoặc một ví dụ phức tạp hơn

>>> add(45, 291) 
66 270 
4 332 
8 328 
16 320 
336 

Edit: Đối với nó để làm việc một cách dễ dàng trên số ký bạn cần phải giới thiệu một giới hạn trên a và 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 

Dùng thử trên

add(-1, 1) 

để xem một chút đơn mang lên thông qua toàn bộ phạm vi và tràn qua 32 lần lặp

4294967294 2 
4294967292 4 
4294967288 8 
... 
4294901760 65536 
... 
2147483648 2147483648 
0 0 
0L 

Answer 8

Vâng, để thực hiện một tương đương với các toán tử logic là khá đơn giản: bạn làm một bit-by-bit sum (mà là một XOR), với carry (là AND). Như thế này:

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; 
} 

Answer 9

int Add(int a, int b) 
{ 
    while (b) 
    { 
     int carry = a & b; 
     a = a^b; 
     b = carry << 1; 
    } 
    return a; 
} 

Answer 10

Bạn đã nhận được một vài thao tác bit câu trả lời. Đây là một cái gì đó khác nhau.

Trong C, arr[ind] == *(arr + ind). Điều này cho phép chúng tôi làm những điều hơi khó hiểu (nhưng hợp pháp) như int arr = { 3, 1, 4, 5 }; int val = 0[arr];.

Vì vậy, chúng ta có thể xác định một tùy chỉnh thêm chức năng (mà không sử dụng rõ ràng của một toán tử số học) thusly:

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]); 
} 

Cách khác, nếu chúng ta muốn tránh thủ thuật này, và nếu bằng toán tử số học chúng bao gồm |, & và ^ (vì vậy chút trực tiếp thao tác không được phép), chúng ta có thể làm điều đó thông qua bảng tra cứu:

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; 
} 

Answer 11

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; 
} 

Answer 12

#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; 
} 

Answer 13

## 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(); 
} 

Answer 14

Mã để triển khai thêm, nhân mà không sử dụng +, * nhà điều hành; cho phép trừ đường chuyền 1 của bổ sung 1 số để add chức năng

#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; 
} 

Answer 15

Điều này có thể được thực hiện một cách đệ quy:

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 
} 

hoặc lặp đi lặp lại:

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; 
} 

Answer 16

Câu hỏi đặt ra yêu cầu làm thế nào để thêm hai số vì vậy tôi không hiểu tại sao tất cả các giải pháp cung cấp thêm hai số nguyên? Điều gì sẽ xảy ra nếu hai số này trôi nổi tức là 2.3 + 1.8 chúng cũng không được coi là số không? Hoặc câu hỏi cần phải được sửa đổi hoặc câu trả lời.

Đối với phao Tôi tin rằng các số nên được chia thành các thành phần của chúng, tức là 2.3 = 2 + 0.3 thì chuyển đổi thành số nguyên bằng cách nhân với hệ số mũ i của nó.e 0.3 = 3 * 10^-1 làm tương tự cho số khác và sau đó thêm phân số nguyên sử dụng một trong các phương pháp thay đổi bit được đưa ra như một giải pháp trên xử lý tình huống để chuyển sang vị trí số đơn vị tức là 2.7 + 3.3 = 6.0 = 2+3+0.7+0.3 = 2 + 3 + 7x10^-1 + 3x10^-1 = 2 + 3 + 10^10^-1 (điều này có thể được xử lý như hai bổ sung riêng biệt 2+3=5 và sau đó 5+1=6)

Answer 17

int add_without_arithmatic(int a, int b) 
{ 
    int sum; 
    char *p; 
    p = (char *)a; 
    sum = (int)&p[b]; 
    printf("\nSum : %d",sum); 
} 

Answer 18

Đây là giải pháp C gọn nhẹ. Đôi khi đệ quy có thể đọc được nhiều hơn các vòng lặp.

int add(int a, int b){ 
    if (b == 0) return a; 
    return add(a^b, (a & b) << 1); 
} 

Answer 19

Với câu trả lời đưa ra ở trên, nó có thể được thực hiện trong mã dòng duy nhất:

int add(int a, int b) { 
    return (b == 0) ? a : add(a^b, (a & b) << 1); 
} 

Answer 20

Tôi nghĩ rằng đoạn mã này sẽ rất hữu ích cho thêm hai số mà không cần cộng thêm hành

#include<stdio.h> 

int main() 

{ 
    int a, b, c; 

    printf("enter two no. : "); 
    scanf("%d%d", &a, &b); 

    c = (a - ~b - 1); 
    printf("%d\n", c); 

    return 0; 
}