在C位中，乘以3除以16

我的一个伙伴有这些谜题，这是一个让我望而却步的谜题。 这是问题，你得到一个数字，你想要返回该数字乘以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 

得到标志并将其存储在变量blarg中。

有另一个变量hold 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). 

（或者简单地应用欧几里得算法。）问题要求乘以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.因此可以通过应用单个AND运算找到k 。 两个进一步的操作将给3k 。 操作次数：3。
• 还可以使用AND运算（具有缺失的位）找到余数c 。 乘以3再使用两个操作。 轮class完成了分工。 操作次数：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  #include  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; }