c - 尝试解决 C 语言中的位级操作难题时遇到困难

Question

所以我必须使用按位操作来解决这个问题。

Should duplicate effect of C expression (x*63),
including overflow behavior.
Examples: multi63(1) = 63
   multi63(-1) = -63
Available ops: ! ~ & ^ | + << >>

也许我不明白正在寻找什么，但我尝试不同的变化，每次我的结果要么非常接近需要返回的结果，要么不正确。

这就是我现在正在玩的。我想如果我可以掩盖 x，即周长 1，那么我就会知道我是乘以负数还是正数。

int y = x>>31;

return ~(y^x) 

这将返回:

 Test times63(2147483647[0x7fffffff]) failed...
...Gives -2147483648[0x80000000]. Should be 2147483585[0x7fffffc1]

如果我尝试返回 2147483585[0x7fffffc1] 它告诉我我需要返回 -2147483648[0x80000000] 所以我对需要返回什么感到困惑。

Answer 1

作为一般(!)规则，您可以考虑表达式 x*N 的这些公式，仅使用移位和加法/减法:

A: (x << n) + (x << n-1) << + ... + << (x << m)

B:(x << n+1) - (x << m)

N 可以被视为 0 和 1 的序列 [(0...0)(1...1)(0...0)(1...1)]。您必须考虑从位位置 n 到位位置 m 连续运行 1，其中 n == m 是可能的。

在您的情况下，N = 63，即二进制的 011_1111。所以我们有 n = 5 和 m = 0。 作为一个简单的例子，假设 x = 2:

使用B: (2 << 6) - (2 << 0) == (2*64) - (2*1) == 128 - 2 == 126 (你可以自己尝试一下A，它工作得很好。)

为了演示另一个数字的过程，假设 N = 55 且 x = 2. 55(二进制:011_0111)。这次我们有两个 1 序列。 n1 = 5、m1 = 4、n2 = 2、m2 = 0。

使用 B 表示 n1/m1:(2 << 6) - (2 << 4) == (2*64) - (2*16) == 128 - 32 == 96

使用 B 表示 n2/m2:(2 << 3) - (2 << 0) == (2*8) - (2*1) == 16 - 2 == 14

将两个结果相加得到 110，即所需的值。