人类有十个手指，所以我们的算数都是10 进制的，而计算机的世界里，所有事物都只由0和1呈现出来，所以数字也只能用2进制表示。因为2进制的表示方式，在计算机里对于数字的运算，除了现实中常用的“加减乘除”，更多了“与非或”这些位运算。
在进行数学运算的过程中，我们经常会总结出一些技巧方法，而这些方法其实跟进制有很大的关系。比如小学老师就告诉我们：检查一个整数能否被3整除，只要派定各个数位上的数字加起来是否能被3；判定一个整数是否能被5整除，只要看最后一位是不是0或5。而这些规律却不能适用到2进制表示的数字上。
不过利用2进制的特殊性，我们也能从位运算上找到很多的技巧。比如一个常见的面试问题：
有一组数包含了1到100的整数，且每个整数只出现一次且随机出现于数组中，现在有一个数被从中删除，请找出被删除的数。
如果放在小学，数学老师就会说我们可以这样解答：高斯告诉我们从1一直加到100的和是5050，那么只要把数组中的数字相加其结果肯定小于5050，然后只要两数相减得到的就是被删除的那个数了。
可惜计算机老师说：计算机里32位的整数只能表示-2147483648到2147483647。即使用长整形也会存在溢出的情况。所以如果数组不是100位而是更大的数，加法就不能解答了。好在像Java都有BigInteger，完全不用担心数字会很大。
如若在程序员的面试过程中我们用数学方式回答，可怕面试官并不会喜欢。常用的位运算有：与、或、非、异或。其实只要用“与/非”或者“或/非”都可以表示出另外两种运算符，但是程序里却包含了这4种，特别是异或。异或运算非常有趣：任何数与自己异或都将得到0，任何数与0异或依然是自身，任何数与一个数异或两次也依然是自身（因为相同数可以通过结合律先异或变成0）。
所以上边的问题，我们只要把1到100每个数都异或一遍，再把数组中的数也异或一遍，就会是的存在的数出现两次而变成了0，而被删除的数则依然留着。
[codesyntax lang=”cpp” lines=”normal”]
/**
* @param a Array with N-1 ditinct elements, each element is in range [1, N]
* @param N range for searching with
* @return The miss number in array
*/
int findMissNumber(int a[], int N) {
int xorNum = N;
for (int i = 0; i < N-1; ++i) {
xorNum ^= (i+1)^a[i];
}
return xorNum;
}
[/codesyntax]
“异或”特点在体现在人身上就是个极品的表现了：你要敢跟我一样，我就什么都不给你，你要是跟我不一样，我偏要留下点什么。相对来说，“与”运算就显得温柔多了，必须两情相愿才会有结果。
下边这个面试题就是利用“与”运算和2进制数特点来得到一个很特别的解法的：
给一个整数，找出该数以比特表示时有多少位是1？
这问题不再用现实的10进制表述，而直接使用2进制，所以这个问题就不能问数学老师了。最简单的方式就是一位一位找过去，整数一般也就32或者64位所以不会很慢。但是极客总喜欢把事情做到极致，通过“与”运算，有多少位1就只要找那么多次即可：
[codesyntax lang=”cpp” lines=”normal”]
int bitsCount(int n) {
int count = 0;
while(n != 0) {
count ++;
n &= (n-1);
}
return count;
}
[/codesyntax]
当n减1的操作会让n排在最后的一位1被借位而变成0，而该1后边的0曽全部变成了1。之后的“与”操作就使得前面的1保留而排在最后的1被消除。重复多次，就能知道有多少位1了。多么简单而又奇妙。假如是10进制数要求有多少位是1，就只能一位位算了，毕竟每一位不是0，也可能是2到9。
那么给出一个32位的整数，我们该怎么知道有多少位是0呢？
根据上边的题目，进一步问：
给一个32位整数，已知2进制表示时只有一位是1，也就是说它是2的次方数，求找出是第几位为1？
这问题用数学表示就是 2n= x，x已知，求n。于是高中数学老师就会开始带入逆函数：log22n=log2x，得到n = log2x。不错，可惜一般面试的时候肯定会说：不能使用math库求解。最直接的方法还是一位一位的去找，直到出现1为止。
在之前《二分查找法的实现和应用(进阶篇)》里有讲到正整数找平方根可以用二分法做，其实对于这个1的问题，我们也可以使用二分法。因为它只有32位，所以在最多经过5步后我们就可以得到结果：
[codesyntax lang=”cpp” lines=”normal”]
int findBit(int n) {
int i = 1; // low bit
int j = 32; // hight bit
int k = (i+j)/2; // middle bit
int calls = 0;
while (i < j) {
++calls;
if (n >> (k-1) == 1) {
break;
}
if ((n >> k) == 0) { // 1 is not in higher bits
j = k;
} else {
i = k+1;
}
k = (i+j)/2;
}
// printf("Calls: %d\n", calls);
return k;
}
int main(int argc, char const *argv[]) {
for (int i = 0; i<32; ++i) {
printf("%d\n", findBit(1<<i));
}
return 0;
}
[/codesyntax]
但是可以看到里面的判定语句很多，程序到达判断语句的时候就需要时间来决定下一步要如何执行，虽然二分用更少的步骤，但是可能在某些硬件上还是一位一位查找更快，因为后者的判定更少一些。该整数只有32位，所以返回值其实只要6个比特位就可以表示就可以表示，如果比特位以0为基位计算，最高位算作31，那么结果只要5个比特就可以表示了。
接着，问题就转换为求5个比特位每一位的是0还是1。可以知道如果1在高16位是，返回值的第5位一定是1；而对于 高16位或低16位，只要1在其中的高8位，那么返回值的的第4位一定是1；递推到最后，如果1出现在偶数位上（以0为基准计算），那么最后一位就是1了。所以，我们可以用位运算来求得结果如下：
[codesyntax lang=”cpp” lines=”normal”]
int findBit2(int n) {
unsigned int b4 = 0xFFFF0000;
unsigned int b3 = 0xFF00FF00;
unsigned int b2 = 0xF0F0F0F0;
unsigned int b1 = 0xCCCCCCCC;
unsigned int b0 = 0xAAAAAAAA;
int pos = ((b4&n) > 0? 1<<4:0)
| ((b3&n) > 0? 1<<3:0)
| ((b2&n) > 0? 1<<2:0)
| ((b1&n) > 0? 1<<1:0)
| ((b0&n) > 0? 1<<0:0);
return pos+1;
}
int main(int argc, char const *argv[]) {
for (int i = 0; i<32; ++i) {
printf("%d\n", findBit2(1<<i));
}
return 0;
}
[/codesyntax]
其实使用位运算的解法也是利用了二分的思想，32位的整形最多需要5步二分查找，上边的解法就是把这5步展开同时进行。如果是64位整形，则只要展开6步即可。
之前说过判断条件会带慢程序运行效率，上边每个分步的3元条件运算符也都存在判定，似乎也差不多。不过我一个EE专业出身的同事Mathew提醒说：这些都可以在硬件上做设计让门电路并发执行，而且每一位的运算结果都可以直接通过与门电路设置到相应结果的比特位上，不需要或门参与。
软件做到最后瓶颈都落在了硬件上。但另一方面，也反应出运算符操作和硬件的紧密联系，所以相对来说，位运算总是会比算数运算要快一些。不过在平时那些微小小数据量上，这些差异还是不需要太多在意的。