c - 分数与位运算相乘

Question

好吧，我一直在试图找出如何在 c 中将分数 (3/4) 乘以有符号整数。挑战在于仅使用逻辑运算符 (! ~ & ^ | + << >>)，不使用（if 语句、循环等）并且最多使用 12 个逻辑运算符。目标是准确模拟以下表达式 (x*3/4)。现在我已经查看了具有类似问题（只是分数不同）的其他问题，但是这些问题的解决方案使用了超过 12 个运算符。我试过简化它们，但如果解决方案不起作用，我似乎无法做到这一点。这是 5/8 问题的答案：

int s = -((num >> 31) & 1); // sign bit as -1 or 0

int n = (num ^ s) - s; // twos complement if negative

int x = n >> 3; // divide by 8

x = (x << 2) + x;   // multiply by 5; no overflow yet since 5/8 is less than one

int y = n & 7;  // the bits we shifted out

y = (y << 2) + y;   // multiply by 5; no overflow

return (s ^ (x + (y >> 3))) - s; // the two pieces and complemented back

我不确定上面的方法是否正确，因为我插入了-2 并手动完成并得到了-3。应该是 -1 因为 -2 * (5/8) = -1.25

我最初解决这个问题的想法是检查溢出。这是因为一个简单的程序，如：

x = (x<<1) + x;
x = X>>2;

在溢出的情况下会导致答案偏离 +1。为了解决这个问题，我想我必须将限制除以 3，然后检查乘以的整数是否大于 715827882 或 -715827882。如果数字更大，则从比较中获得 1 并将其添加到最终结果中，或者如果数字小于则获得 0 并将 0 添加到最终结果中。我觉得这种方式很难在没有 if 语句的情况下实现，并且它可能使用超过 12 个运算符。我只是在寻求解决问题的最佳方法的帮助。提前致谢！

Answer 1

您想到的是：

x=(x<<1)+x; // do x=x*3 x=x>>2; // do x=x/4

这可能会溢出，因为 x 首先保存一个较大的值。这行得通吗？

x=x-(x>>2); // do x=x-x/4, equal to 3/4

当然，因为x>>2丢掉了最低位，所以结果被截断了。如果你需要向下截断，这是错误的，你应该使用加法：

x=(x>>1)+((x+1)>>2); // x=x/2+x/4

编辑：您需要 (x+1)>>2 以避免双截断结果丢失，例如 x=7。

c - 分数与位运算相乘

c - Multiplying Fractions with Bitwise Operations

c

bit-manipulation

fractions