c-我需要对这个按位排列的谜题做一点解释

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

这里所做的所有工作都是为了匹配isoC定义除法向零取整的事实。乘3/4更简单的版本是只乘3并移动2：

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

不幸的是，这对负值有错误的行为(它将值降到最低，而不是向零取整(。

为了修复它，我们需要在偏移2之前将3^*添加到负项，以通过截断模拟舍入。我们这样做：

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以向上取整。对于CCD_ 3，变换将是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具有带符号类型和非负值，则结果的值为积分CCD_ 13/2^E2的商的一部分。如果E1具有带符号类型和负值结果值是实现定义的。

因此，只有当将任何负值右移一个小于int宽度的值时，掩码提取才会起作用。这适用于two的互补系统(以及您可能使用的任何系统(的通用实现，但该标准在技术上没有保证。