I was just going through some basic stuff as I am learning C. I came upon a question to multiply a number by 7 without using the * operator. Basically it's like this
(x << 3) - x;
Now I know about basic bit manipulation operations, but I can't get how do you multiply a number by any other odd number without using the * operator? Is there a general algorithm for this?
Think about how you multiply in decimal using pencil and paper:
12
x 26
----
72
24
----
312
What does multiplication look like in binary?
0111
x 0101
-------
0111
0000
0111
-------
100011
Notice anything? Unlike multiplication in decimal, where you need to memorize the "times table," when multiplying in binary, you are always multiplying one of the terms by either 0 or 1 before writing it down in the list addends. There's no times table needed. If the digit of the second term is 1, you add in the first term. If it's 0, you don't. Also note how the addends are progressively shifted over to the left.
If you're unsure of this, do a few binary multiplications on paper. When you're done, convert the result back to decimal and see if it's correct. After you've done a few, I think you'll get the idea how binary multiplication can be implemented using shifts and adds.
Everyone is overlooking the obvious. No multiplication is involved:
10^(log10(A) + log10(B))
The question says:
multiply a number by 7 without using * operator
This doesn't use *:
number / (1 / 7)
Edit:
This compiles and works fine in C:
int number,result;
number = 8;
result = number / (1. / 7);
printf("result is %d\n",result);
An integer left shift is multiplying by 2, provided it doesn't overflow. Just add or subtract as appropriate once you get close.
int multiply(int multiplicand, int factor)
{
if (factor == 0) return 0;
int product = multiplicand;
for (int ii = 1; ii < abs(factor); ++ii) {
product += multiplicand;
}
return factor >= 0 ? product : -product;
}
You wanted multiplication without *, you got it, pal!
It's easy to avoid the '*' operator:
mov eax, 1234h
mov edx, 5678h
imul edx
No '*' in sight. Of course, if you wanted to get into the spirit of it, you could also use the trusty old shift and add algorithm:
mult proc
; Multiplies eax by ebx and places result in edx:ecx
xor ecx, ecx
xor edx, edx
mul1:
test ebx, 1
jz mul2
add ecx, eax
adc edx, 0
mul2:
shr ebx, 1
shl eax, 1
test ebx, ebx
jnz mul1
done:
ret
mult endp
Of course, with modern processors, all (?) have multiplication instructions, but back when the PDP-11 was shiny and new, code like this saw real use.
Mathematically speaking, multiplication distributes over addition. Essentially, this means:
x * (a + b + c ...) = (x * a) + (x * b) + (x * c) ...
Any real number (in your case 7), can be presented as a series of additions (such as 8 + (-1), since subtraction is really just addition going the wrong way). This allows you to represent any single multiplication statement as an equivalent series of multiplication statements, which will come up with the same result:
x * 7
= x * (8 + (-1))
= (x * 8) + (x * (-1))
= (x * 8) - (x * 1)
= (x * 8) - x
The bitwise shift operator essentially just multiplies or divides a number by a power of 2. So long as your equation is only dealing with such values, bit shifting can be used to replace all occurrence of the multiplication operator.
(x * 8) - x = (x * 23) - x = (x << 3) - x
A similar strategy can be used on any other integer, and it makes no difference whether it's odd or even.
Any number, odd or even, can be expressed as a sum of powers of two. For example,
1 2 4 8
------------------
1 = 1
2 = 0 + 2
3 = 1 + 2
4 = 0 + 0 + 4
5 = 1 + 0 + 4
6 = 0 + 2 + 4
7 = 1 + 2 + 4
8 = 0 + 0 + 0 + 8
11 = 1 + 2 + 0 + 8
So, you can multiply x by any number by performing the right set of shifts and adds.
1x = x
2x = 0 + x<<1
3x = x + x<<1
4x = 0 + 0 + x<<2
5x = x + 0 + x<<2
11x = x + x<<1 + 0 + x<<3
When it comes down to it, multiplication by a positive integer can be done like this:
int multiply(int a, int b) {
int ret = 0;
for (int i=0; i<b; i++) {
ret += b;
}
return ret;
}
Efficient? Hardly. But it's correct (factoring in limits on ints and so forth).
So using a left-shift is just a shortcut for multiplying by 2. But once you get to the highest power-of-2 under b you just add a the necessary number of times, so:
int multiply(int a, int b) {
int ret = a;
int mult = 1;
while (mult <= b) {
ret <<= 1;
mult <<= 1;
}
while (mult < b) {
ret += a;
}
return ret;
}
or something close to that.
To put it another way, to multiply by 7.
b 3 times.One evening, I found that I was extremely bored, and cooked this up:
#include <iostream>
typedef unsigned int uint32;
uint32 add(uint32 a, uint32 b) {
do {
uint32 s = a ^ b;
uint32 c = a & b;
a = s;
b = c << 1;
} while (a & b)
return (a | b)
}
uint32 mul(uint32 a, uint32 b) {
uint32 total = 0;
do {
uint32 s1 = a & (-(b & 1))
b >>= 1; a <<= 1;
total = add(s1, total)
} while (b)
return total;
}
int main(void) {
using namespace std;
uint32 a, b;
cout << "Enter two numbers to be multiplied: ";
cin >> a >> b;
cout << "Total: " << mul(a,b) << endl;
return 0;
}
The code above should be quite self-explanatory, as I tried to keep it as simple as possible. It should work, more or less, the way a CPU might perform these operations. The only bug I'm aware of is that a is not permitted to be greater than 32,767 and b is not permitted to be large enough to overflow a (that is, multiply overflow is not handled, so 64-bit results are not possible). It should even work with negative numbers, provided the inputs are appropriately reinterpret_cast<>.
unsigned int Multiply(unsigned int m1, unsigned int m2)
{
unsigned int numBits = sizeof(unsigned int) * 8; // Not part of the core algorithm
unsigned int product = 0;
unsigned int mask = 1;
for(int i =0; i < numBits; ++i, mask = mask << 1)
{
if(m1 & mask)
{
product += (m2 << i);
}
}
return product;
}
@Wang, that's a good generalization. But here is a slightly faster version. But it assumes no overflow and a is non-negative.
int mult(int a, int b){
int p=1;
int rv=0;
for(int i=0; a >= p && i < 31; i++){
if(a & p){
rv += b;
}
p = p << 1;
b = b << 1;
}
return rv;
}
It will loop at most 1+log_2(a) times. Could be faster if you swap a and b when a > b.
unsigned int Multiply( unsigned int a, unsigned int b )
{
int ret = 0;
// For each bit in b
for (int i=0; i<32; i++) {
// If that bit is not equal to zero
if (( b & (1 << i)) != 0) {
// Add it to our return value
ret += a << i;
}
}
return ret;
}
I avoided the sign bit, because it's kind of not the subject of the post. This is an implementation of what Wayne Conrad said basically. Here is another problem is you want to try more low level math operations. Project Euler is cool!
In C#:
private static string Multi(int a, int b)
{
if (a == 0 || b == 0)
return "0";
bool isnegative = false;
if (a < 0 || b < 0)
{
isnegative = true;
a = Math.Abs(a);
b = Math.Abs(b);
}
int sum = 0;
if (a > b)
{
for (int i = 1; i <= b; i++)
{
sum += a;
}
}
else
{
for (int i = 1; i <= a; i++)
{
sum += b;
}
}
if (isnegative == true)
return "-" + sum.ToString();
else
return sum.ToString();
}
Another thinking-outside-the-box answer:
BigDecimal a = new BigDecimal(123);
BigDecimal b = new BigDecimal(2);
BigDecimal result = a.multiply(b);
System.out.println(result.intValue());
Loop it. Run a loop seven times and iterate by the number you are multiplying with seven.
Pseudocode:
total = 0
multiply = 34
loop while i < 7
total = total + multiply
endloop
By making use of recursion, we can multiply two integers with the given constraints.
To multiply x and y, recursively add x y times.
#include<stdio.h>
/* function to multiply two numbers x and y*/
int multiply(int x, int y)
{
/* multiplied with anything gives */
if(y == 0)
return 0;
/* Add x one by one */
if(y > 0 )
return (x + multiply(x, y-1));
/* the case where y is negative */
if(y < 0 )
return -multiply(x, -y);
}
int main()
{
printf("\n %d", multiply(5, -11));
getchar();
return 0;
}
A JavaScript approach for positive numbers
function recursiveMultiply(num1, num2){
const bigger = num1 > num2 ? num1 : num2;
const smaller = num1 <= num2 ? num1 : num2;
const indexIncrement = 1;
const resultIncrement = bigger;
return recursiveMultiplyHelper(bigger, smaller, 0, indexIncrement, resultIncrement)
}
function recursiveMultiplyHelper(num1, num2, index, indexIncrement, resultIncrement){
let result = 0;
if (index === num2){
return result;
}
if ((index+indexIncrement+indexIncrement) >= num2){
indexIncrement = 1;
resultIncrement = num1;
} else{
indexIncrement += indexIncrement;
resultIncrement += resultIncrement;
}
result = recursiveMultiplyHelper(num1, num2, (index+indexIncrement), indexIncrement, resultIncrement);
result += resultIncrement;
console.log(num1, num2, index, result);
return result;
}
Think about the normal multiplication method we use
1101 x =>13
0101 =>5
---------------------
1101
0000
1101
0000
===================
1000001 . => 65
Writing the same above in the code
#include<stdio.h>
int multiply(int a, int b){
int res = 0,count =0;
while(b>0) {
if(b & 0x1)
res = res + (a << count);
b = b>>1;
count++;
}
return res;
}
int main() {
printf("Sum of x+y = %d", multiply(5,10));
return 0;
}
Ugly and slow and untested, but...
int mult(a,b){
int i, rv=0;
for(i=0; i < 31; ++i){
if(a & 1<<i){
rv += b << i;
}
}
if(a & 1<<31){ // two's complement
rv -= b<<31;
}
return rv;
}