How to implement multiplication without using mult

问题:

I want to implement multiplication of two integer numbers without using multiplication operator, in .NET

public uint MultiplyNumbers(uint x, uint y)
{

}

Any idea!

回答1:

I'm assuming this is homework... otherwise there's no sane reason you'd want to do it. Therefore I'll just give hints...

• If performance isn't terribly important, consider that x * 3 = x + x + x... think about using a loop.

• If performance is important but you know that one of the numbers will be small, loop on the smaller number.

• If performance is important and both numbers could be large, you'll need to think about bit-twiddling. Remember that x * 2 is x << 1, and go from there.

回答2:

It goes against the spirit of the assignment, but I'd do it for kicks...

Create your own class, overload the + operator to do multiplication.

Create your homework project; add your first project as a reference. Write your code to be

return new SuperInt(x) + SuperInt(y);

Everyone else is going to some variation of shifting bits or addition. Half of the kids are going to post the exact code returned by a Google search anyway. At least this way, you'll be unique.

The assignment itself is really just an exercise in lateral thinking. Any sane person would use the * operator when working in .Net.

EDIT: If you really want to be a class clown - overload the * operator and implement it with bitwise operations and addition.

Additional Answer #1 (if you are willing to change your method signature...) What about this?

static void Main(string[] args)
{
    Console.WriteLine(string.Format("{0} * {1} = {2}", 5, 6, MultiplyNumbers(5, 6)));
    Console.WriteLine(string.Format("{0} * {1} = {2}", -5, 6, MultiplyNumbers(-5, 6)));
    Console.WriteLine(string.Format("{0} * {1} = {2}", -5, -6, MultiplyNumbers(-5, -6)));
    Console.WriteLine(string.Format("{0} * {1} = {2}", 5, 1, MultiplyNumbers(5, 1)));
    Console.Read();
}


static double MultiplyNumbers(double x, double y)
{
    return x / (1 / y);
}

Outputs:

5 * 6 = 30
-5 * 6 = -30
-5 * -6 = 30
5 * 1 = 5

One straight-forward line of code.

But still, if you take this approach, be prepared to argue a bit. It does multiply integers; by implicitly converting them to doubles in the call. Your question didn't say you could use only integers, just that it had to multiply two integers without using '*'.

EDIT: Since you say you can't change the signature of MultiplyNumbers - you can accomplish it without doing that:

static uint MultiplyNumbers(uint x, uint y)
{
    return MultiplyDouble(x, y);
}

static uint MultiplyDouble(double x, double y)
{
    return Convert.ToUInt32(x / (1 / y));
}

Additional Answer #2 This is my favorite approach yet.

Take the values, send them to Google, parse the result.

static uint MultiplyNumbers(uint x, uint y)
{
    System.Net.WebClient myClient = new System.Net.WebClient();
    string sData = myClient.DownloadString(string.Format("http://www.google.com/search?q={0}*{1}&btnG=Search",x,y));

    string ans = x.ToString() + " * " + y.ToString() + " = ";
    int iBegin = sData.IndexOf(ans,50) + ans.Length ;
    int iEnd = sData.IndexOf('<',iBegin);

    return Convert.ToUInt32(sData.Substring(iBegin, iEnd - iBegin).Trim());
}

回答3:

Look, ma, no * operator!

using System;
using System.Reflection.Emit;

static class Program
{
    delegate uint UintOpDelegate(uint a, uint b);

    static void Main()
    {
        var method = new DynamicMethod("Multiply",
            typeof(uint), new Type[] { typeof(uint), typeof(uint) });
        var gen = method.GetILGenerator();
        gen.Emit(OpCodes.Ldarg_0);
        gen.Emit(OpCodes.Ldarg_1);
        gen.Emit(OpCodes.Mul);
        gen.Emit(OpCodes.Ret);

        var del = (UintOpDelegate)method.CreateDelegate(typeof(UintOpDelegate));

        var product = del(2, 3); //product is now 6!
    }
}

Even better:

using System;
using System.Runtime.InteropServices;

delegate uint BinaryOp(uint a, uint b);

static class Program
{
    [DllImport("kernel32.dll", SetLastError = true)]
    static extern bool VirtualProtect(
        IntPtr address, IntPtr size, uint protect, out uint oldProtect);

    static void Main()
    {
        var bytes = IntPtr.Size == sizeof(int) //32-bit? It's slower BTW
            ? Convert.FromBase64String("i0QkBA+vRCQIww==")
            : Convert.FromBase64String("D6/Ki8HD");
        var handle = GCHandle.Alloc(bytes, GCHandleType.Pinned);
        try
        {
            uint old;
            VirtualProtect(handle.AddrOfPinnedObject(),
                (IntPtr)bytes.Length, 0x40, out old);
            var action = (BinaryOp)Marshal.GetDelegateForFunctionPointer(
                handle.AddrOfPinnedObject(), typeof(BinaryOp));
            var temp = action(3, 2); //6!
        }
        finally { handle.Free(); }
    }
}

回答4:

You can simply loop for x times, adding y to a running total on each iteration.

回答5:

Repeated addition would work. Add 'x' to a running total 'y' times.

var total = 0;

for(int i = 0; i < y; i++)
{
    total += x;
}

回答6:

You can use bitwise operators to do multiplication.

x<<1

is x*2 and so on.

You will still have to do some addition.

   result=0;
   while(b != 0)               
   {
      if (b&01)                
        {
          result=result+a;     
        }
      a<<=1;                   
      b>>=1;                   
   }

From: Multiplication of two integers using bitwise operators

回答7:

public uint MultiplyNumbers(uint x, uint y) {
    if (x == 0 || y == 0) return 0;

    uint answer = x;

    for (uint i = 1; i < y; ++i) 
        answer += x;

    return answer;
}