我需要对这个按位拼图做一些解释

Question

我已经在这个按位拼图上卡了几个小时了。我在 google 上寻找解决这个问题的好方法，看看其他人是如何解决它的，我遇到了这个解决方案。我想弄清楚它是如何工作的。我唯一不明白的是舍入过程和丢失的位？丢失了哪些位？

非常感谢有人向我解释这个解决方案。

提前谢谢大家，Yosemite:)

/*
 * ezThreeFourths - multiplies by 3/4 rounding toward 0,
 *   Should exactly duplicate effect of C expression (x*3/4),
 *   including overflow behavior.
 *   Examples: ezThreeFourths(11) = 8
 *             ezThreeFourths(-9) = -6
 *             ezThreeFourths(1073741824) = -268435456 (overflow)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */

int ezThreeFourths(int x) {
/*
 *sets y to make up for the lost bits while rounding. Multiplies
 *by three by adding x 3 times. Records the sign since
 * what is added will be different depending on whether the sign
 *is positive or negative and adds this to to the number. Then
 *divedes by 8 by shifting.
 */
  int y = 3;
  x =x+x+x;
  int z = x>>31;
  z = y & z;
  x = z + x;
  x = x>>2;
  return x;
}

这是link我从哪里得到的：link个人没有在文件中标记他的名字所以我不知道他的名字

Answer 1

这里的所有工作只是为了匹配 iso C 定义除法以向零舍入的事实。乘以 3/4 的更简单的版本是乘以 3 然后移动 2:

return (x+x+x) >> 2;

不幸的是，负值有 wrong behaviour（它降低了值而不是向零四舍五入）。

为了解决这个问题，我们需要在负数项上加上 3^*，然后再平移 2 位以通过截断模拟舍入。我们是这样做的：

int z = x >> 31; // Arithmetic right shift extracts sign mask (0xffffffff or 0x0)
int y = 3 & z; // 3 for negative values, 0 for nonnegative
return (x + x + x + y) >> 2; // Multiply and divide with rounding

为了更正确，我们应该考虑到我们并不知道整数的大小是 32，通过像这样更改代码：

int three_fourths(int x) {
    return (x + x + x + (3 & (x >> (8 * sizeof(x) - 1)))) >> 2;
}

您可以看到这个最终实施的效果 here。

^{*_{这是把地板分界线变成天花板分界线的成语。如果您有 x / N 向下舍入，您可以将表达式更改为 (x + N - 1) / N 以改为向上舍入。对于 N==4，转换将是 x / 4->(x + 3) / 4}}

未定义的行为

我们终于有了一些假设。当然 x + x + x 可以溢出并产生未定义的行为，这与 x * 3 没有什么不同（忽略问题作者暗示这具有相同的溢出行为，它会在某些实现上但不能保证）。

实现定义行为的主要部分是算术右移。以下是 C 标准在这个问题上的说法（ISO/IEC 9899:TC3 §6.5.7 ¶5）：

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

因此，掩码提取只有在将任何负值右移一个小于 int 宽度的位置产生一个在所有位位置都为 1 的值时才会起作用。这在 common implementation 中适用于二进制补码系统（并且可能是您将要使用的任何系统），但标准在技术上不保证。

我需要对这个按位拼图做一些解释

I need a little explaination on this bitwise puzzle

c

bit-manipulation

bit-shift

bit