移位运算(部分笔试题)

一、x=a/2;等价于x=a>>1;右移则幂次变小
x=a*2;等价于x=a<<1;左移则幂次变大

乘法和移位运算谁更快？按道理来说移位更快，但是现在的编译器都对这个做优化了。
扩展：x*=16，也就是左移4位！x<<=4;

二、分段(2段，left&right，初始时 left = 0,right = n-1,center = (left+right)/2):
1、奇数，如1，2，3.=>(left,center),(center+1,right)=>(1,2),(3)
或者，=>(left,center-1),(center,right)=>(1),(2,3)

2、偶数，如1，2=>(left,center),(center+1,right)=>(1),(2)
或者，=>(left,center-1),(center,right)=>wrong!

小结：最好采用(left,center),(center+1,right)这种分法！

三、如何判断一个数是否为2的N次方
最简单的方法是判断x&(x-1)是否为0.why？
如果是2的n次幂，则此数用二进制表示时只有一位是1，其它都是0。减1后，此位变成0，后面的位变成1，所以按位与后结果是0；
如果不是2的n次幂，则此数用二进制表示时有多位是1。减1后，只有最后一个1变成0，前面的 1还是1，所以按位与后结果不是0。
如果给出一个不大的数，如9998判断它是不是2的n次方？我们知道2的n次方增长很快，所以不要被这个数吓着了。已知 2¹⁰=1024，2¹¹=2048，2¹²=4096，2¹³=8192 ，所以可以断定该数不是2的n次方！

四、再议x&(x-1）！

有这样一段小程序，求当x=9999时，函数的返回值是多少？
int get(int x){
int count=0;
while(x){
count++;
x=x&(x-1);
}
return count;
}

于是我们必须要知道对于x来说M=x&(x-1)的值到底是多少？
可惜笔试的时候没做出来，郁闷。转自http://hi.baidu.com/zengzhaonong/blog/item/7fb884509ee30c61853524c2.html
正如文章作者说的，每次x&(x-1)都会将其对应的二进制数中的最右端的1变为0。所以这个函数也就是在算这个二进制数中有多少个1。
如何快速地得到如9999，这样大的数对应的二进制数？
2¹⁰=1024，2¹¹=2048，2¹²=4096，2¹³=8192 ，于是我们可以将9999=8192+1024+512+256+15
然后加起来
10000000000000
10000000000
1000000000
100000000
+ 1111
---------------------
10011100001111
所以有8个1，所以最后得到的返回值为8！

五、快速得到一个数的7倍！，参考http://job.51cto.com/art/201008/218251_1.htm

考察点：乘法较慢，改用移位和加减
做法：(x<<3)-x，左移3位后变为原来的8倍