Умножение двух целых чисел с использованием побитовых операторов

Как я могу умножить два целых числа с помощью побитовых операторов?

Я нашел реализацию здесь . Есть ли лучший способ реализации умножения?

Например: 2 * 6 = 12 должно выполняться с помощью побитовых операторов.

ПРИМЕЧАНИЕ. Числа являются произвольными, а не мощностью 2

#include main() { int a, b, result; printf("\nEnter the numbers to be multiplied:"); scanf("%d%d", &a, &b); // a > b result = 0; while (b != 0) // Iterate the loop till b == 0 { if (b & 01) // Bitwise & of the value of b with 01 { result = result + a; // Add a to result if b is odd . } a<<=1; // Left shifting the value contained in 'a' by 1 // Multiplies a by 2 for each loop b>>=1; // Right shifting the value contained in 'b' by 1. } printf("nResult:%d",result); } 

Источник

Я пришел сюда, чтобы найти этот вопрос, и я нахожу ответ Ценг правильно. Спасибо, Зенгр! Но есть одна модификация, которую я хотел бы видеть, которая избавляется от оператора «+» в его коде. Это должно сделать умножение двух произвольных чисел, используя NO ARITHMETIC OPERATORS, но все побитовое.

Решение Zengr:

 #include main() { int a,b,result; printf("nEnter the numbers to be multiplied :"); scanf("%d%d",&a,&b); // a>b result=0; while(b != 0) // Iterate the loop till b==0 { if (b&01) // Bitwise & of the value of b with 01 { result=result+a; // Add a to result if b is odd . } a<<=1; // Left shifting the value contained in 'a' by 1 // multiplies a by 2 for each loop b>>=1; // Right shifting the value contained in 'b' by 1. } printf("nResult:%d",result); } 

Мой ответ:

 #include main() { int a,b,result; printf("nEnter the numbers to be multiplied :"); scanf("%d%d",&a,&b); // a>b result=0; while(b != 0) // Iterate the loop till b==0 { if (b&01) // Bitwise & of the value of b with 01 { result=add(result,a); // Add a to result if b is odd . } a<<=1; // Left shifting the value contained in 'a' by 1 // multiplies a by 2 for each loop b>>=1; // Right shifting the value contained in 'b' by 1. } printf("nResult:%d",result); } 

где я бы написал add () как:

 int Add(int x, int y) { // Iterate till there is no carry while (y != 0) { // carry now contains common set bits of x and y int carry = x & y; // Sum of bits of x and y where at least one of the bits is not set x = x ^ y; // Carry is shifted by one so that adding it to x gives the required sum y = carry << 1; } return x; } 

или рекурсивное добавление:

 int Add(int x, int y) { if (y == 0) return x; else return Add( x ^ y, (x & y) << 1); } 

источник для кода добавления: http://www.geeksforgeeks.org/add-two-numbers-without-using-arithmetic-operators/

Это чисто побитно.

 public int bitwiseMultiply(int a, int b) { if (a ==0 || b == 0) { return 0; } if (a == 1) { return b; } else if (b == 1) { return a; } int result = 0; // Not needed, just for test int initA = a; boolean isORNeeded = false; while (b != 0 ) { if (b == 1) { break; } if ((b & 1) == 1) { // Carry needed, odd number result += initA; // Test, not needed isORNeeded = true; } a <<= 1; // Double the a b >>= 1; // Half the b System.out.println("a=["+a+"], b=["+b+"], result=["+result+"]"); } return (isORNeeded ? (a | initA) : a); // a + result; } 

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

Алгоритм сборки: Это следует непосредственно из того, что ax * 7 = (ax * 8) -ax.

 mov bx, ax ;Save AX*1 shl ax, 1 ;AX := AX*2 shl ax, 1 ;AX := AX*4 shl ax, 1 ;AX := AX*8 sub ax, bx ;AX := AX*7 

Каждый шаг сдвига – умножение на 2

В C # здесь реализована функция.

  public static int Mul(int a, int b) { int r = 0; while (b != 0) { var temp = b & 1; if (temp!= 0) { r = r + a; } a= a << 1; b= b >> 1; if (temp == 0) { r = a; break; } } return r; } 
  #include void main() { int n, m, i, j, x, large, small, t1, m2, result, a1, a2, a3, c, c1, c2, r, r1, la, re; printf("Enter two numbers\n"); scanf("%d%d", &n, &m); result = 0; if (n > m) { large = n; small = m; } else { large = m; small = n; } c = 0; while (small) { t1 = small; t1 &= 1; if (t1 == 1) { printf("\n %d", large); la = large; re = result; m2 = 0; r1 = 1; while (re || la || c) { a2 = la; a2 &= 1; a3 = re; a3 &= 1; c1 = a2 & a3; r = a3 ^ a2; c2 =r & c; r ^= c; if (c1 || c2) c = 1; else c = 0; result &= ~r1; x = r; m2 >>= 1; while (m2) { r <<= 1; m2 >>= 1; } result |= r; la >>= 1; re >>= 1; r1 <<= 1; m2 = r1; } } large <<= 1; small >>= 1; } printf("\n%dX%d= %d\n", n, m, result); } 

Ниже приведено одно возможное решение для умножения двух целых чисел с использованием побитовых операторов.

 #include  #define INT_BITS 32 int multiply(int a, int b) { int pos1, pos2, res; for (pos1 = 0; pos1 < INT_BITS; pos1++) { for (pos2 = 0; pos2 < INT_BITS; pos2++) { /* Find the bits set in both numbers and add their * corresponding powers of 2. */ if ((a & (1 << pos1)) && (b & (1 << pos2))) { res = res + (1 << (pos1 + pos2)); // res = res + ((1 << pos1) << pos2); /* Both the above statements calculating res are same */ } } } return res; } int main() { int num1, num2, product; printf("Enter two numbers to be multiplied:"); scanf("%d %d", &num1, &num2); product = multiply(num1, num2); printf("Product of %d and %d: %d\n", num1, num2, product); return 0; } 

Функция multiply () может быть изменена, как показано ниже, с помощью функции Shiv's Add ():

 int Add(int x, int y) { if (y == 0) return x; else return Add( x ^ y, (x & y) << 1); } int multiply(int a, int b) { int pos1, pos2, res, temp; for (pos1 = 0; pos1 < INT_BITS; pos1++) { for (pos2 = 0; pos2 < INT_BITS; pos2++) { /* Find the bits set in both numbers and add their * corresponding powers of 2. */ if ((a & (1 << pos1)) && (b & (1 << pos2))) { temp = (1 << pos1) << pos2; res = Add(res, temp); } } } return res; } 
Давайте будем гением компьютера.