Добавить два целых числа, используя только побитовые операторы?

В С# можно ли выполнить сумму двух 32-битных целых чисел без использования таких вещей, как if..else, loop и т.д.?

То есть, это можно сделать, используя только побитовые операции OR (|), AND (&), XOR (^), NOT (!), Shift left (<<) и shift right (>>)?

Ответ 1

Вот пример вашего развлечения

unsigned int myAdd(unsigned int a, unsigned int b)
{
    unsigned int carry = a & b;
    unsigned int result = a ^ b;
    while(carry != 0)
    {
        unsigned int shiftedcarry = carry << 1;
        carry = result & shiftedcarry;
        result ^= shiftedcarry;
    }
    return result;
}

Цикл может быть развернут. Количество выполняемых операций зависит от количества бит, установленного в операндах, но не больше ширины unsigned int. Когда carry становится 0, следующие итерации ничего не меняют.

Ответ 2

Попробуйте следующее:

    private int add(int a, int b) {
        if(b == 0)
            return a;

        return add( a ^ b, (a & b) << 1);
    }

Edit: Исправлено утверждение if

Ответ 3

Подумайте о том, как добавление происходит по частям. Сдвиньте значения, чтобы поочередно получить каждый бит каждого операнда, затем просмотрите четыре возможных значения для двух бит и определите, что должен быть бит результата, и нужно ли беспокоить бит бит. Затем посмотрите, как результат и перенос могут быть запрограммированы с использованием побитовых операций.

Ответ 4

public static int getSum(int p, int q)
{
    int carry=0, result =0;
    for(int i=0; i<32; i++)
    {
        int n1 = (p & (1<<(i)))>>(i); //find the nth bit of p
        int n2 = (q & (1<<(i)))>>(i); //find the nth bit of q

        int s = n1 ^ n2 ^ carry; //sum of bits
        carry = (carry==0) ? (n1&n2): (n1 | n2); //calculate the carry for next step
        result = result | (s<<(i)); //calculate resultant bit
    }

    return result;
}

Взятие 32 бит в качестве int занимает 32 бит. Спасибо!!!

Ответ 5

static int binaryadd(int x, int y)
{
  while (x != 0)
  {
    int c = y & x;
    y = y ^ x; 
    x = c << 1;             
  }
  return y;
}

Ответ 6

int Add(int a, int b)
{
      int result = 0,
          // carry now contains common set bits of "a" and "b"
          carry = a & b;

      if (Convert.ToBoolean(carry))
      {
          // Sum of bits of "a" and "b" where at least one 
          // of the bits is not set
          result = a ^ b;

          // carry is shifted by one so that adding it 
          // to "a" gives the required sum
          carry = carry << 1;

          result = add(carry, result);
      }
      else
      {
          result = a ^ b;
      }

      return result;
}

Сумма двух бит может быть выполнена с использованием оператора XOR ^ а бит переноса может быть получен с использованием оператора AND &. Если a и b не имеют битов в одном и том же положении, то оператор ^ дает сумму a и b.

Комментарии от geeksforgeeks

Ответ 7

        int  b =  25;
        for (int t = 128; t > 0; t = t / 2)
        {
            if ((b & t) != 0) Console.Write("1 ");
            if ((b & t) == 0) Console.Write("0 ");
        }
        Console.WriteLine();
        //b = (sbyte)~b;
        int e = 22;
        for (int t = 128; t > 0; t = t / 2)
        {
            if ((e & t) != 0) Console.Write("1 ");
            if ((e & t) == 0) Console.Write("0 ");
        }
        Console.WriteLine();
        int c = b | e;
        for (int t = 128; t > 0; t = t / 2)
        {
            if ((c & t) != 0) Console.Write("1 ");
            if ((c & t) == 0) Console.Write("0 ");
        }