使用有限的按位运算符将无符号整数乘以10

Question

这是一个关于练习考试的问题:

编写一个将参数乘以10的函数.您只能使用这些运算符:<< - &^和唯一允许的常数移位为1 2 4 8 16.

功能原型是:

unsigned int(unsigned int x);

我们得到了一个解决方案,即:

unsigned int(unsigned int x) { 
    return (x << 4) - (x << 2) - (x << 1); 
} 

我知道它有效,并且它通过从整数中减去10的倍数来实现.我不明白为什么它有效,并想了解如何得出这个答案的过程.

提前感谢您的任何答案!

Answer 1

(x << 4)基本上是x * 16,(x << 2)是x * 4和(x << 1)是x * 2.因此,16x - 4x - 2x = 10x.

至于为什么(x << 4)等于x * 16,这是因为二进制表示.让我们用二进制10(为清晰起见只显示8位;左边实际上有一堆更多的零):

00001010

现在让我们左转4个空格:

10100000

那是160.

一种思考方式是,当你在基数十(即10 - > 100)中加零时,你乘以10.当你在基数2中加零时,你乘以2.因此,转移4个空格(因此增加4个零)乘以2*2*2*2= 16.

Answer 2

x << 1 = x*2.

x << 2 = x*4.

x << 4 = x*16.

16 - 4 - 2 = 10.

你也可以使用:

x << 3 = x*8

但是8 + 2 = 10,所以你可以使用(x << 2 << 1)+(x << 1).