高效代码之按位操作（一）

不管程序猿喜不喜欢写代码，只要写了，就应该想办法让自己的程序尽量高效。懂得一些按位计算的技巧，可以很有效的提高程序速度。今天我们就开始介绍一些能够使程序加速的小窍门。

（以下例子均假设int型变量长度是4字节，即32个bit）

1求最大int

int的存储规则是第一个bit为符号位，后面31个bit存值，所以最大的int应该长成这个样子：0111….111（一个0后面跟31个1）。有好几种办法可以快速生成这个最大int：可以手算一下，把31个1组成的二进制数转换成10进制的2147483647（所以要记着带计算器~），也可以直接声明按照二进制输入，然后按31次“1”（好累），也可以按照下面两种按位操作生成：

int maxInt = ~(1 << 31);

int maxInt = (1 << 31) - 1;

两种方法都先把1左移到最右端，生成1000…000（31个0），然后第一种方法按位取反，第二种利用了模运算的特点，减去1，相当于按位取反了。对计算机硬件电路来说，按位取反比做减法更直接，更高效。

2乘，除2的幂

提到乘除，第一反应肯定是想到Number=Number*n这样的式子，简单方便。不过它虽然正确，但效率却不高，计算机需要做好几步分析才能得到最终结果。这里有个特殊情况，由于计算机是二进制存储数据，所以乘除2的n次方的时候特别方便，实际上只需要左移或者右移n位就可以了。

Number=Number<<n;//乘

Number=Number>>n;//除

多说一句，如果乘或者除的数不是2的次方怎么办？简单，把因子拆分成若干2的次方的和，单独移位后再把结果加在一起（实际上计算机就是这么做的）。

3交换两个整数值

凡是写过任何一个排序算法的程序猿，都一定干过交换两个数的值的操作，标准的流程是这样的：

temporary=a;

a=b;

b= temporary;

每次写这种代码的时候我都很不爽，虽然正确，但为了交换ab的值，却一定要用一个额外的变量temporary来做中转站。这种感觉就像是自己家的事情非得要经过外人才能做成一样。下面是强迫症程序猿的福音，不需要额外空间就完成交换：

a=a ^ b;

b=b ^ a;

a=a ^ b;

乍一看可能比较别扭，不容易理解这三句话是怎么工作的。先解释b：第二句是给b赋值的，把第一句带入，就成了b_new=b_old^ (a_old ^ b_old )= a_old ^ ( b_old ^ b_old)=a_old ^ 0= a_old；再解释a: a_new= (a_old ^ b_old )^a_old=0^b_old=b_old.怎么样，不需要中间变量就完成了交换，有意思吧？

4检查一个数是否是2的幂

这是一个把按位操作的优势展现的淋漓尽致的例子。可能有人第一反应会是这个样子的算法：

int a=1;

for(int i=1;i<31;i++)

{

a=a*2;

if(Number==a)

returntrue;

}

return false;

这个方法虽然正确，但要循环多次，一遍又一遍的检查是否是2的幂，效率比较低。看看按位操作会怎么做：

int a=~Number;

a=a^Number;

a=!a;

return a==0;

怎么样，简单吧，只要三步操作。至于是什么原因么，今天卖个关子，明天再解释~~

~~~~~~~~~~~~~~~~~更新线~~~~~~~~~~~~~~~~~~~

感谢Nibnat的提醒，最后一个例子写错了，正确的操作应该是下面的样子，晚上写一篇日子解释一下。

return (Number & ( Number - 1 ))==0;