+演算子を使用せずに2つの番号を追加するための最良の方法は何ですか？

https://stackoverflow.com/questions/365522

21-08-2019
|

質問

友人と私は、脳の体操を行ったり来たりしていると私はこの1つを解決するためにどのようには考えています。私の仮定は、それは確かいくつかのビット演算子で可能だが、ではないということです。

解決

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が各ビットにキャリーインである。

ループは、キャリーは、すべてのビットはゼロになるまで運ぶ追加続ける。

他のヒント

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

"最高" を定義します。ここではPythonのバージョンがあります：

len(range(x)+range(y))

+リストの連結ではなく加算を行う。

ビット演算子と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;
}

チート。あなたは、番号を否定し、最初からそれを引くこともできます）。

2進加算器がどのように機能するかを調べ、それに失敗。：）

編集：私は投稿後にああ、あなたのコメントを見ました。

。

2進加算の詳細されているここを。

注、これはリップルキャリー加算器として知られているためであろう動作しますが、最適に動作しない加算する、。ハードウェアに組み込まれているほとんどのバイナリ加算器は、キャリールックアヘッド加算器などの高速加算器の形をしています。

あなたが0にcarry_inを設定し、1の補数整数場合carry_inが1に設定されている場合は、

符号なしと2の両方の補数整数のための私のリップルキャリー加算器の作品を私はまた、ほかにアンダーフローやオーバーフローを表示するためにフラグを追加しました。

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

なぜ、二番目の数字として、できるだけ頻繁に最初の数をincremetない？

理由ADDを1つの命令としてではなく、ビット演算の組み合わせとして、アセンブラでimplememtedされ、それを行うのは難しいということです。あなたは、次の上位ビットに与えられた下位ビットから運びを心配する必要があります。これは、マシンがハードウェアで行うことを速いものですが、それでもCとのそれは、あなたがソフトウェアで行うことができない速います。

2つの整数を追加することは困難ではありません。 2進加算の多くの例は、オンラインあります。

より多くの困難な問題は、浮動小数点数です！ //pages.cs：でhttp例があります.wisc.edu /〜smoler / x86text / lect.notes / arith.flpt.htmlする

Pythonではビット演算子を使用します：

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;

私たちは紙の上で2進加算を行う可能性がありますと同じように実装されています。

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としてこれを見ました。私の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)

この方法は、反復を使用するため、時間の複雑さは最適ではありません。私は最善の方法は、ビット単位の操作と低レベルで作業することであると信じています。

これは、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

あなたはビットシフトと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;
}

入力は反対の符号である場合は、

最も票を投じた答えは動作しません。しかします以下。私は一箇所にだまされているが、唯一のビットクリーンコードを維持します。改善歓迎のための任意の提案

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

ここでポータブル一行三元および再帰的なソリューションです。

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

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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow