Multiplication of two integers using bitwise operators
#include <stdio.h>
int main(void)
{
int a, b, result;
printf("Enter 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 & 1) // Bitwise & of the value of b with 1
{
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("Result: %d\n",result);
}
Source
I came here looking for this question and I find Zengr's answer correct. Thanks Zengr! But there is one modification I would want to see which is getting rid of the '+' operator in his code. This should make multiplication of two arbitrary numbers using NO ARITHMETIC OPERATORS but all bitwise.
Zengr's solution first:
#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);
}
My Answer would be:
#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);
}
where I would write add() as:
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;
}
or recursively adding as:
int Add(int x, int y)
{
if (y == 0)
return x;
else
return Add( x ^ y, (x & y) << 1);
}
source for addition code: http://www.geeksforgeeks.org/add-two-numbers-without-using-arithmetic-operators/
This one is purely with bit-wise operations.
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;
}
Assembly algorithm: This follows directly from the fact that 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
Every shift step is a multiplication by 2