在C位中，乘以3并除以16

Question

我的一个好友遇到了这些难题，这使我难以理解。这是问题所在，您将得到一个数字，并且要将该数字乘以3并除以16并取整为0。抓住？您只能使用！ 〜＆^ | + << >>运算符，其中只有12个的组合。

int mult(int x){
    //some code here...
return y;
}

我的尝试是：

    int hold = x + x + x;
    int hold1 = 8;
    hold1 = hold1 & hold;
    hold1 = hold1 >> 3;
    hold = hold >> 4;
    hold = hold + hold1;
    return hold;

但是这似乎不起作用。我认为我有一个丢失位的问题，但是我似乎无法想出一种保存它们的方法。另一个角度会很好。只是要添加，如果可以使用语句或函数调用，则也只能使用int类型的变量且不使用循环。

现在，我的电话号码是0xfffffff。它应该返回0x2ffffff，但它返回0x3000000。

Answer 1

对于这个问题，您需要担心划分之前丢失的位（显然）。本质上，如果它是负数，则要在乘以3后再加上15。一个简单的if语句（使用您的运算符）就足够了。

我不打算给您代码，但逐步说明，

x = x*3

获取符号并将其存储在变量foo中。

具有另一个变量，保持x + 15；

设置if语句，以便如果x为负数，则使用加15的值，否则，则使用常规数（我们上面做的3倍）。

然后除以16，您已经向您展示了如何做。祝你好运！

Answer 2

这似乎有效（只要不发生溢出）：

((num<<2)+~num+1)>>4

尝试此JavaScript代码，在控制台中运行：

for (var num = -128; num <= 128; ++num) {
  var a = Math.floor(num * 3 / 16);
  var b = ((num<<2)+~num+1)>>4;
  console.log(
    "Input:", num,
    "Regular math:", a,
    "Bit math:", b,
    "Equal: ", a===b
  );
}

Answer 3

数学

[将正整数n除以​​16后，将得到正整数商k和余数c < 16：

    (n/16) = k + (c/16).

（（或简单地应用Euclidan算法。）问题要求乘以3/16，所以乘以3

    (n/16) * 3 = 3k + (c/16) * 3.

数字k是整数，因此部分3k仍然是整数。但是，int算术运算会四舍五入，因此如果您先除以第二项，则可能会失去精度。而且由于c < 16，因此可以安全地先进行乘法运算而不会溢出（假设sizeof(int) >= 7）。所以算法设计可以是

    (3n/16) = 3k + (3c/16).

设计

• 整数k只是将n/16向下舍入为0。因此，可以通过应用单个k运算来找到AND。进行另外两个操作将得到3k。操作次数：3。
• c的余数也可以使用AND操作（缺少位）找到。 3的乘积还要使用两个运算。并转移完成分区。操作次数：4。
• 将它们加在一起将为您提供最终答案。

总操作次数：8。

负面

以上算法使用移位运算。在底片上可能效果不佳。但是，假设为二进制补码，则n的符号存储在符号位中。可以在应用算法之前将其删除并重新应用于答案。

• 要查找并存储n的符号，单个AND就足够了。
• 要删除该符号，可以使用OR。
• 应用上述算法。
• 要恢复符号位，请对带有已存储符号位的算法输出使用最后的OR操作。

这使最终操作数达到11。

Answer 4

您可以做的是先除以4，然后相加3倍，然后再除以4。

3*x/16=(x/4+x/4+x/4)/4

具有这种逻辑的程序可以是

main()
{
   int x=0xefffffff;
   int y;
   printf("%x",x);
   y=x&(0x80000000);
   y=y>>31;
   x=(y&(~x+1))+(~y&(x));
   x=x>>2;
   x=x&(0x3fffffff);
   x=x+x+x;
   x=x>>2;
   x=x&(0x3fffffff);
    x=(y&(~x+1))+(~y&(x));
   printf("\n%x %d",x,x);
}

与0x3fffffff并设为msb为零。甚至可以将数字转换为正数。这使用2的负数补码。如果使用直接的除法方法，则负数的位精度会损失。因此，请使用将-ve转换为+ ve数字然后执行除法运算的工作方法。

Answer 5

注意，C99标准在6.5.7节中指出，带符号负整数的右移会调用实现定义的行为。在int由32位组成并且有符号整数右移映射到算术移位指令的规定下，以下代码适用于所有int输入。一种完全可移植的解决方案也可能满足问题中提出的要求，但我现在想不出一个。

我的基本思想是将数字分成高和低位，以防止中间溢出。高位首先除以16（这是一个精确的运算），然后乘以3。低位首先乘以3，然后除以16。由于算术右移舍入为负无穷大，而不是像整数除法那样向零舍入，因此需要对负数的右移应用校正。对于右移N，如果要移位的数字为负，则需要在移位之前加2 ^N-1。

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

int ref (int a)
{
  long long int t = ((long long int)a * 3) / 16;
  return (int)t;
}

int main (void)
{
  int a, t, r, c, res;
  a = 0;
  do {
    t = a >> 4;         /* high order bits */
    r = a & 0xf;        /* low order bits */
    c = (a >> 31) & 15; /* shift correction. Portable alternative: (a < 0) ? 15 : 0 */
    res = t + t + t + ((r + r + r + c) >> 4);
    if (res != ref(a)) {
      printf ("!!!! error a=%08x  res=%08x  ref=%08x\n", a, res, ref(a));
      return EXIT_FAILURE;
    }
    a++;
  } while (a);
  return EXIT_SUCCESS;
}