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

Question

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

То есть это можно сделать, используя только побитовые операции ИЛИ(|), И (&), XOR (^), НЕ (!), сдвиг влево (<<) и сдвиг вправо (>>)?

Answer 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, следующие итерации ничего не меняют.

Answer 2

Попробуйте:

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

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

Редактировать: Исправлено if Заявление

Answer 3

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

Answer 4

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

Answer 5

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 бита.Спасибо !!!

Answer 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

Answer 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 ");
        }