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

Question

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

我真的很感激有人向我解释这个解决方案。

在此先感谢大家，优胜美地 :)

/*
 * 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;
}

这是我得到它的链接：链接这个人没有在文件中标记他的名字所以我不知道他的名字

Answer 1

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

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

不幸的是，这对于负值有错误的行为（它将值下限而不是向零舍入）。

为了解决这个问题，我们需要将 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;
}

您可以在此处查看此最终实现的实际效果。

^{*_{这是将地板分隔变成天花板分隔的成语。如果您有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）：

结果E1 >> E2是E1右移的E2位位置。如果E1 具有无符号类型或E1具有有符号类型和非负值，则结果的值是E1/ 2 ^E2的商的整数部分。如果E1具有有符号类型和负值，则结果值是实现定义的。

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