Bitshift乘以任意数字

Question

仅使用加,减和位移,如何将整数乘以给定数？

例如,我想将整数乘以17.

我知道向左移动乘以2的倍数,向右移动除以2的幂,但我不知道如何推广.

负数怎么样？转换为二进制补码并执行相同的步骤？

(编辑:好的,我得到了这个,没关系.你转换成两个补码然后根据数字从左到右而不是从右到左移动.)

现在棘手的部分进来了.我们只能使用3个运营商.

例如,乘以60我可以通过使用这个来完成:

(x << 5) + (x << 4) + (x << 3) + (x << 2)

x我乘以的数字在哪里.但这是7个运营商 - 我如何将其缩减为仅使用3个？

Answer 1

它被称为shift-and-add.维基百科对此有一个很好的解释:

编辑:回答你的另一个问题,是转换为两个赞美将是有效的.但是你需要签名延长它足以容纳整个产品.(假设这是你想要的)

EDIT2:如果两个操作数都是负数,那么从一开始就只有两个操作符补充它们,你不必担心这个.

Answer 2

这是乘以3的示例:

unsigned int y = (x << 1) + (x << 0);

(我假设那x也是unsigned).

希望你能够概括这一点.

Answer 3

据我所知，一般来说，仅使用 3 个运算符进行乘法并不简单。

可以乘以 60，因为 60 = 64 - 4：(x << 6) - (x << 2)