c - 两个数的乘法

Question

几天前，我接受了高通公司的采访。我被困在一个问题上，你的问题看起来很简单，但我和面试官都不满意我的答案，如果有人能提供任何好的解决方案。

问题是:

在不使用任何循环和加法的情况下将 2 个数字相乘，当然也没有乘法和除法。

我的回答是:递归

他用非常低的水平说了其他任何事情。

我想到的真正想法是位移，但位移只会将数字乘以 2 的幂，对于其他数字，我们最终必须进行加法。

例如:10 * 7 可以写成:(7 ~~ 111 的二进制)10<< 2 + 10<<1 + 1040 + 20 + 10 = 70

但是再次不允许添加。

大家对这个问题有什么想法。

Answer 1

这是一个仅使用查找、加法和移位的解决方案。查找不需要乘法，因为它是指向另一个数组的指针数组 - 因此需要添加才能找到正确的数组。然后使用第二个值可以重复指针运算并获得查找结果。

#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;
}