Умножение двух целых чисел с использованием побитовых операторов
Как я могу умножить два целых числа, используя побитовые операторы?
Я нашел реализацию здесь. Есть ли лучший способ реализации умножения?
Например: 2 * 6 = 12 должно выполняться с использованием побитовых операторов.
ПРИМЕЧАНИЕ: числа являются произвольными, а не степенью 2
8 ответов
#include<stdio.h>
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);
}
Я пришел сюда в поисках этого вопроса и нашел правильный ответ Зенгра. Спасибо Зенгр! Но есть одна модификация, которую я хотел бы увидеть, которая избавляется от оператора '+' в его коде. Это должно сделать умножение двух произвольных чисел, используя БЕЗ АРИТМЕТИЧЕСКИХ ОПЕРАТОРОВ, но все побитовые.
Решение Zengr первым:
#include<stdio.h>
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<stdio.h>
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 <stdio.h>
#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;
}
#include<stdio.h>
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);
}