умножение в C без арифметических операторов - PullRequest
Новая
       9

умножение в C без арифметических операторов

7 голосов
/ 28 июля 2011

Можно ли умножить два числа без использования арифметических операторов с использованием C?Используя оператор сдвига влево, я могу умножить любое число только на 2.Как насчет других номеров?

Ответы [ 4 ]

12 голосов
/ 28 июля 2011

Чтобы решить эту проблему, первое, что вы хотите сделать, это выяснить, как получить простые арифметические операции, используя только побитовые операторы.

Например, добавление может быть достигнуто с помощью этой техники 

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

Тогда нужно сделать умножение с использованием сложения: 

int mult(int a, int b) {
   int i = 0;
   int c = 0;
   while (i < b) {
      c = add(c, a);
      i = add(i, 1);
   }
   return c;
}

Это умножение еще не работает, если b отрицательно, но так как это похоже на домашнюю работу, я оставлю это в качестве упражнения для вас. ;)

Edit: Хотя умножение интуитивно понятно после добавления, функцию сложения не так просто понять, поэтому я объясню это здесь.

Допустим, вы хотите добавить два числа, 11010011 и 10101. Обычный способ сделать это - выстроить их в ряд так: 

11010011
 + 10101

Вы заметите, что когда вы добавляете два двоичных числа, если i-й бит обоих чисел равен 1, то результирующий бит равен 0, и слева от i идет перенос на бит.

Это перенос, который хранит переменная 'c' в коде. 

//...
c = b & a;
//...
c << 1;
//...

Мы используем биты b и a, чтобы получить только те биты, где a и b равны 1, затем мы смещаем его влево на 1, чтобы получить биты переноса.

Затем вы можете посмотреть на биты, где a и b различаются, то есть один из битов равен 1, а другой бит равен 0. Результирующий бит в этом случае будет равен 1 без переноса.

вот что хранит эта строка: 

b = b ^ a;

Строка выше по существу удаляет биты, где a и b равны 1 (теперь хранятся в c).

Итак, теперь у вас есть еще два числа b и c, которые вам нужно сложить вместе.

Сначала давайте посмотрим, где мы находимся, с примером после первой итерации цикла 

c = a = 00100010
    b = 11000110

Возможно, это еще не совсем очевидно, но b накапливает полученную сумму. Через большее количество итераций цикла «биты», которые переносятся, «добавляются» обратно в b, а переносы сохраняются снова в c. В этом смысле вы можете рассматривать оператор xor как операцию сложения без переноса.

Вот вторая итерация этого цикла: 

c = a = 00000010
    b = 11100100

3-я итерация: 

c = a = 00000000
    b = 11100110

Теперь c (и a) равно 0, так что больше нет переноса для добавления. Выходим из цикла и возвращаем б. Обратите внимание, что даже если вы продолжите цикл, ни одно из чисел не изменится.

5 голосов
/ 28 июля 2011

Возможно, см. Эту вики для направления: http://en.wikipedia.org/wiki/Binary_multiplier

3 голосов
/ 01 августа 2011 
void main()
{ 
  int n1, n2, n3, n4, x, y, i;
  printf("Enter first number");
  scanf("%d", &n1);
  printf("Enter second number");
  scanf("%d", &n2);
  n3 = n2;
  n4 = n2;
  n1-=1;
  for(i = n1;i > 0;i-=1)
  { 
    do { 
      x = n2 & n3; 
      y= n2 ^ n3; 
      n2 = x << 1; 
      n3 = y; 
    } while (x);
    n2 = y;
    n3 = n4;
  }
  printf("product of two number is %d", y);
  getch();
}
2 голосов
/ 28 июля 2011

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

...