2

I was tasked to write the Russian Multiplication Algorithm in any programming language without using any multiplication/division operators (or math methods from libraries etc.) except the shift operators. I used Java and this is my method:

public static int multiply(int a, int b) {
    System.out.printf("%d %d\n",a,b);

    if(b == 1 || b == -1 || a == 0)
        return a;

    int a0 = a << 1;
    int b0 = b >>> 1;
    
    int recursionResult = multiply(a0,b0);
    
    if((b & 1) == 1)
        recursionResult += a;
    
    return recursionResult;
}

This works for me without any problems. However, I don't understand why it does for negative b.

I tried using the arithmetic right shift for dividing b by 2 at first. It failed, and when I looked at the output, I completely get why. Then I tried using the logic right shift just for fun (before maybe trying to invert b if it is negative, and inverting it back at the end), and it suddenly worked!

The output looks like this (for a=11, b=-50, as an example):

11 -50
22 2147483623
44 1073741811
88 536870905
176 268435452
352 134217726
704 67108863
1408 33554431
2816 16777215
5632 8388607
11264 4194303
22528 2097151
45056 1048575
90112 524287
180224 262143
360448 131071
720896 65535
1441792 32767
2883584 16383
5767168 8191
11534336 4095
23068672 2047
46137344 1023
92274688 511
184549376 255
369098752 127
738197504 63
1476395008 31
-1342177280 15
1610612736 7
-1073741824 3
-2147483648 1

This looks quite random to me, but in the end, you get -550, the correct result. Can anyone explain this to me?

Eddie
  • 21
  • 1
  • 1
  • "Narrow" multiplication like this does not have separate signed and unsigned versions, there is just one version that does both, though for "wide" multiplication there is a difference. Semi-duplicate: [Why are signed and unsigned multiplication different instructions on x86(-64)?](https://stackoverflow.com/questions/14063599/why-are-signed-and-unsigned-multiplication-different-instructions-on-x86-64) So any narrow unsigned multiplication can also be used as a narrow signed multiplication and vice versa, since they're the same thing. – harold Jun 03 '21 at 18:45

0 Answers0