multiplication of two numbers

Question

Few days back I had an interview with Qualcomm. I was kinnda stucked to one question, the question thou looked very simple but neither me nor the interviewer were satisfied with my answers, if anyone can provide any good solution to this problem.

The question is:

Multiply 2 numbers without using any loops and additions and of course no multiplication and division.

To which I replied: recursion

He said anything else at very low level.

To which the genuine thought that came to my mind was bit shifting, but bit shifting will only multiply the number by power of 2 and for other numbers we finally have to do a addition.

For example: 10 * 7 can be done as: (binary of 7 ~~ 111) 10<< 2 + 10<<1 + 10 40 + 20 + 10 = 70

But again addition was not allowed.

Any thoughts on this issue guys.

Answer 1

Here is a solution just using lookup, addition and shifting. The lookup does not require multiplication as it is an array of pointers to another array - hence addition required to find the right array. Then using the second value you can repeat pointer arithmetic and get the lookup result.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
  /* Note:As this is an array of pointers to an array of values, addition is
     only required for the lookup.

     i.e. 

     First part: lookup + a value -> A pointer to an array
     Second part - Add a value to the pointer to above pointer to get the value
  */
  unsigned char lookup[16][16] = {
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },
    { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 },
    { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45 },
    { 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60 },
    { 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75 },
    { 0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90 },
    { 0, 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105 },
    { 0, 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120 },
    { 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, 135 },
    { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150 },
    { 0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143, 154, 165 },
    { 0, 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, 132, 144, 156, 168, 180 },
    { 0, 13, 26, 39, 52, 65, 78, 91, 104, 117, 130, 143, 156, 169, 182, 195 },
    { 0, 14, 28, 42, 56, 70, 84, 98, 112, 126, 140, 154, 168, 182, 196, 210 },
    { 0, 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, 210, 225 }
  };
  unsigned short answer, mult;
  unsigned char x, y, a, b;

  x = (unsigned char)atoi(argv[1]);
  y = (unsigned char)atoi(argv[2]);
  printf("Multiple %d by %d\n", x, y);

  answer = 0;
  /* First nibble of x, First nibble of y */
  a = x & 0xf;
  b = y & 0xf;
  mult = lookup[a][b];
  answer += mult;
  printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer);

  /* First nibble of x, Second nibble of y */
  a = x & 0xf;
  b = (y & 0xf0) >> 4;
  mult = lookup[a][b];
  answer += mult << 4;
  printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer);

  /* Second nibble of x, First nibble of y */
  a = (x & 0xf0) >> 4;
  b = y & 0xf;
  mult = lookup[a][b];
  answer += mult << 4;
  printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer);

  /* Second nibble of x, Second nibble of y */
  a = (x & 0xf0) >> 4;
  b = (y & 0xf0) >> 4;
  mult = lookup[a][b];
  answer += mult << 8;
  printf("Looking up %d, %d get %d - Answer so far %d\n", a, b, mult, answer);

  return 0;
} 

Answer 2

Perhaps you could recursively add, using bitwise operations as a replacement for the addition operator. See: Adding Two Numbers With Bitwise and Shift Operators

Answer 3

You can separate your problems by first implementing the addition and then the multiplication based on the addition.

For the addition, implement what they do on processors at the gate level using the C bitwise operators:

http://en.wikipedia.org/wiki/Full_adder

Then for the multiplication, with the addition you implemented, use goto statements and labels so no loop statement (the for, while and do iteration statements) will be used.