Question

位运算是把数字用二进制表示之后，对每一位上0或者1的运算。二进制及其位运算是现代计算机学科的基石，很多底层的技术都离不开位运算，因此位运算相关的题目也经常出现在面试中。由于我们在日常生活中习惯了十进制，很多人看到二进制及位运算都觉得很难适应。

理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者1。比如十进制的2转化为二进制之后是10，而十进制的10转换成二进制之后是1010。在程序员圈子里有一个流传了很久的笑话，说世界上有10种人，一种人知道二进制，而另一种人不知道二进制……

除了二进制，我们还可以把数字表示成其他进制，比如表示时间分秒的六十进制等。针对不太熟悉的进制，已经出现了不少很有意思的面试题。比如：

在Excel 2003中，用A表示第1列，B表示第2列……Z表示第26列，AA表示第27列，AB表示第28列……以此类推。请写出一个函数，输入用字母表示的列号编码，输出它是第几列。

这是一道很新颖的关于进制的题目，其本质是把十进制数字用A～Z表示成二十六进制。如果想到这一点，解决这个问题就不难了。

其实二进制的位运算并不是很难掌握，因为位运算总共只有五种运算：与、或、异或、左移和右移。与、或和异或运算的规律我们可以用表2.1总结如下：

表2.1　与、或、异或的运算规律

左移运算符m<<n表示把m左移n位。左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0。比如：

00001010<<2=00101000

10001010<<3=01010000

右移运算符m>>n表示把m右移n位。右移n位的时候，最右边的n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值，则用0填补最左边的n位。如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数，则右移之后在最左边补n个0；如果数字原先是负数，则右移之后在最左边补n个1。下面是对两个8位有符号数作右移的例子：

00001010>>2=00000010

10001010>>3=11110001

面试题10二进制中1的个数就是直接考查位运算的例子，而面试题40数组中只出现一次的数字、面试题47不用加减乘除做加法等都是根据位运算的特点来解决问题。