views:

1843

answers:

20

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 * operator. Basically its like this

      (x<<3)-x;

Now I know about basic bit manipulation operations, But I cant get how do you multiply a number by any other odd number number without using * operator?? Is there any general algorithm for this??

+14  A: 

An integer left shift is multiplying by 2, provided it doesn't overflow. Just add or subtract as appropriate once you get close.

Ignacio Vazquez-Abrams
+2  A: 

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.

  • Left shift by 2 (times 4). Left shift 3 is 8 which is >7;
  • Add b 3 times.
cletus
In your first example, you either mean: `ret += a;` or `i < a`. You should mention that it assumes non-negatives integers in the "and so forth".
jamesdlin
I dont get it....What do we add 3 times?? Like if the the number is 7 to be mulitplied by 7, like I wrote, it is left shift by 3 and subtract 7, the result is 49. What exactly is b? Pardon my lack of knowledge.
Race
Left shit? Tehehehe
pyrochild
+5  A: 

It is the same as x*8-x = x*(8-1) = x*7

Igor Zevaka
A: 

Ugly and slow and untested, but...

int mult(a,b){
    int i, rv=0;
    for(i=0; i < 31; ++i){
        if(a & i<<i){
            rv += b << i
        }
    }
    if(a & 1<<31){ // two's complement
        rv -= b<<31;
    }
    return rv;
}
Wang
You could at least test it before submitting to Stack Overflow.
Adam Pierce
Bear
Adam: Didn't have a compiler, I'm afraid. But point taken. I won't do that again.Bear: Yep, I think that was supposed to be 1<<i. This is why Adam is telling me to test my code.
Wang
+31  A: 

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.

Wayne Conrad
+3  A: 

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
benzado
Useful! But how about scenarios similar to the OP's, such as multiplying by shifting and *subtracting* too? i.e. 6x = (x << 3) - (x << 1) etc?
dreamlax
I thought the only rule was to avoid the `*` operator.
benzado
Also, your table is a little out, 2x is (x << 1), and 4x is (x << 2) etc.
dreamlax
+3  A: 
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;
}
Andrew Shepherd
-1: code assumes 8 bits in a byte.
benzado
Rather than using `* 8` you could just use `<< 3` :)
dreamlax
Or use `CHAR_BIT`
LiraNuna
+15  A: 
int multiply(int multiplicand, int factor)
{
    if (factor == 0) return 0;

    for (int ii = 1; ii < abs(factor); ++ii) {
        multiplicand += multiplicand;
    }

    return factor >= 0 ? multiplicand : -multiplicand;
}

You wanted multiplication without *, you got it, pal!

Wow, thanks dkantowitz. I had no idea! +10 to you my good man!(oh, and *nothing* in the question necessitates bit shifting, but I'm sure you realized that too.)
+1  A: 

@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.

Apprentice Queue
+6  A: 

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 the it, you can 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.

Jerry Coffin
That's not fair, the question is tagged `c`, `c++`, and `java` ;)
dreamlax
@dreamlax: Quite true -- and if somebody reverse engineers the algorithm from assembly code to get an A on their C, C++ or Java homework, I'm willing to believe they probably earned the grade...
Jerry Coffin
My first home computer was a TRS-80, sporting a zippy 1.7MHz Z80, and I typed in a lot of multiplication routines like this. Turned out the fastest way was to do as many 8x16 bit multiplications as necessary, and add them up.
David Thornley
Gotta love x86's LEA instruction... shift and add in a single instruction :)
ephemient
Even many modern CPUs (small, low-power ones) can't multiply or divide. Why waste microcode on that when it can easily be done in software?
Artelius
A: 

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());
igor
How does this work in "C"? I think you may have misread the original question.
S.Robins
@S.Robins: use libgmp for exapmle. mpz_mul (mpz_t rop, mpz_t op1, mpz_t op2)
Tadeusz A. Kadłubowski
Good point, I guess I'm seeing the world through java colored glasses.
igor
A: 

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<>.

greyfade
+9  A: 

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);
Carlos Gutiérrez
+1 for the idea, but it won't work in Java: `java.lang.ArithmeticException: / by zero` since (1 / 7) is done by integer division (workaround is easy)
Carlos Heuberger
actually it won't work in c either! I'm pretty sure you'd get a core dump if you ran that line :).
vicatcu
@vicatcu - Tested in gcc, it works ( `.` are cheap :)
Carlos Gutiérrez
Will probably fail for some values due to rounding. Will fail if your `int` is 64 bits and `number` is greater than 2^51 or so...
Chris Dodd
When you are assigning the result to `result` variable, the fractional part is truncated. The means that if the reslt is imprecise (often happens with FP arithmetics), the truncation might easily produce an incorrect result - off by 1.
AndreyT
@Chris Dodd, AndreyT - True, FP can byte you. My point is the idea, not the implementation.
Carlos Gutiérrez
You still need an explicit cast to convert the `double` result to an `int`.
Loadmaster
@Loadmaster: You don't need an explicit cast to convert `double` to `int`. This is a standard conversion in both C and C++, so no cast is needed. The only reason people might use an explicit cast is to suppress some annoying compiler warnings.
AndreyT
+1  A: 
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;
}

Avoided the sign bit because its kind 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!

Buttink
+2  A: 

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 occurances of 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.

goldPseudo
+11  A: 

Everyone is overlooking the obvious. no multiplication involved.

10^(log10(A) + log10(B))
Jim C
Which in C would be `exp(log(A) + log(B))`.
Loadmaster
I suppose you're being sarcastic, but if you're not, have you ever looked at source code for logn?
Arthur Kalliokoski
I looked at it as more of a history lesson then being sarcastic. People today tend to forget we did do thing before we had computers or even electronic calculators. I've seen to many engineers and programs who accept the result from the "magic box" without understanding how it works. No one can know everything, but we should understand as much as we can. I know the general algorithm for computing logs, but I admit I have not studied them in great depth. They od involve shifting which is multiplying in binary as many people have pointed out. Not unexpected, early CPUS can only add and shift.
Jim C
Even many modern CPUs (small, low-power ones) can't multiply or divide. Why waste microcode on that when it can easily be done in software?
Artelius
The old slide rule implementation! Gotta love the scene in Apollo 13 where 10 engineers are simultaneously doing a calculation on their slide rules - multi-core at its infancy!
franji1
A: 

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();

}

-----in C#

A: 

Why not just loop it? Run a loop 7 times and iterate by the number you are multiplying with 7

pseudo code

total = 0
multiply = 34

loop while i < 7

total = total + multiply

endloop
Thomas Winsnes
A: 

very simple pal ...each time when you left shift a number it means u r multiplying the number by 2 which means ans is (x<<3)-x

ram
A: 
import java.math.BigInteger;

public class MultiplyTest {
    public static void main(String[] args) {
        BigInteger bigInt1 = new BigInteger("5");
        BigInteger bigInt2 = new BigInteger("8");
        System.out.println(bigInt1.multiply(bigInt2));
    }
}
lordstriker24
@lord please format your code next time
seanizer