Bitwise和Shifting写乘法函数

写在前面——

准备从这周开始,平常每两天一道题,周末争取一天一道题,练练招式。题目会源自一个叫做CareerCup的网站(需翻了个墙),上面有各种IT公司的面试题,基本集中在基础算法方面。这将成为我的博客中的一个系列——“做做题”。

今天的题目是:

“Write a code which return square of any number, but you can not use Star or caret sign”

我的第一个思路就是把这个数加N遍就好了:

def square(a):
    result = 0
    for i in range(0,a):
        result += a
    return result

但是这个解显然只对整数有效,并且效率低下,我试了一下100000000,一分钟过去了还的不到结果,然后强制终止的时候,python崩溃了……

在CareerCup网站上有个人给出了位操作写的乘法,我用python重写了一遍:

def multiply(a,b):
    product = 0
    while(a>0):
        if ((a&1) != 0):
            product += b
        a = a >> 1
        b = b << 1
    return product

这个方法用到了我不太熟悉的位操作,于是趁这个机会把bitwise和shifting又温习了一遍。

位操作只的是对一个数的每一位进行操作,具体运算符是AND(&)、OR(|)和XOR(^)。以&为例。2&3的位操作其实是在对比2的二进制0010和3的二进制0011的每一位,如果两者都是1,则结果数的这一位也是1,否则为零。所以2&3的结果就是0010,十进制下的2。值得注意的是XOR操作,它的规则是如果用来比较的两位数字一样,则结果为0,否则为1。

而shifting操作则是在数的二进制形式上进行位移。“>>”是右位移,2 >> 1是将0010向右位移一位变成0001,即十进制中的1,由于二进制数除以10、100、1000的运算得到的商,等价于这个二进制数右移1、2、3位,所以十进制数的右移n位的操作得到的结果其实是这个数除以2^n的商。同理可得左移的效果。

再回头去看上面那个函数,(a&1)的结果跟a二进制数的最后一位有关,若a的最后一位是1,这个表达式的结果是1,若a的最后一位是0,结果为0。

a*b的算法应该是,把b同a的每一位相乘,然后再把这个结果相加。比如14*16=16*4+16*10。上面的这个算法,则是将这个过程转化在二进制下进行。

初始化乘积product为0。然后检查a的二进制数的最右边的一位,如果为1,则加一个b到product,然后把a向右位移,同时将b向左位移一位(相当于b*2)。然后再判断新的a的最后一位,如果是1,那么则要把上一个b*2的结果加到积里面,如果不是,则跳过加法这一步,然后重复向右位移a和b*2的操作。

为什么b要不停的做左位移,也就是十进制里乘以2的操作?因为换成二进制后,a每次右位移,都是把高一位的数变成了最后一位,直到位移n步出来的结果最右位是1的时候,才会将这个1和b相乘,但是这时并不是个位1与b相乘,而是1*(10)^n的积与b相乘(这里的10是二进制10,也就是十进制2)。所以为了保证位数的正确,所以每次右移a之后都要将b左移。

以0101*0010为例,先用1乘以0010等到0010,然后将0101右移得到010,它的最右位是0,那么再右移,得到01,再用这个1乘以0010,但是这时的1其实在初始a值(0101)的右起第三位,所以应该是100乘以0010。最后的结果就是0010+0010*100=1000。

这样一个乘法写出来后,平方算法也就自然而然的出来了。

但是这样的方法虽然效率比我自己想的高,但是仍然没有解决非整数的问题。一个比较无赖的方法是:

def square_2(a):
    return a/(1.0/a)

这是满足题目条件的,既没有用到“*”,也没有用到“^”。而且在python里,效率貌似还行……

最后,在看python文档的时候发现了一个叫做BNF的东西,是一种对程序语法的描述性语言,应该是大部分人都知道的东西吧,我也算补了一下课。