所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
位运算题目的使用情形：
（1）要求时间复杂度不变情况下，减小内存使用（例如：不准使用hash）。
（2）不允许使用加减乘除运算。
具体题目
29.Divide Two Integers
题意：计算两整数相除，不能使用乘除和mod
解：使用位运算。
技巧一：判断两个int型数a和b是否异号： （a < 0）^ (b < 0)。如果结果是true，那么说明异或的前后半部分异号，说明二者异号，也就是说a和b异号，反之，如果是false，那么a和b同号。
技巧二：左移取代乘法 a «= 1 <=> a *= 2; 现在只需要将除数不断的乘二，然后不断与被除数相比较，直到超过被除数之前的一个数x。期间记录乘二了多少次加到结果里。然后用被除数减去x作为新的被除数，循环，直到被除数小于除数。 注意溢出条件下（除数为0，或者被除数是INT_MIN，除数是－1）直接返回INT_MAX。
401. Binary Watch
题意：给出二进制表上灯亮个数n，求出所有可能的时间表示。
解：此题一个巧妙的解法就是：位运算。对于所有可能的时间(12 * 60种)可能进行遍历，如果该时间包含n个二进制1，那么就符合要求。
技巧三：使用位运算计算一个整数中二进制1的个数 判断整数n二进制表示的最后一位是否为1的方法：(n & 1) == 1。 求整数所有1的个数的方法就是：计算完最后一位是否为1后，将整数右移一位，即n »= 1。 推广：判断整数n二进制表示的第i位是否为1的方法：（n & (1 « i)）!= 0。
技巧四：使用sprintf来格式化输出：
char buffer[5];
sprintf(buffer, “%d:%02d”, h, m);
string str = buffer;
将格式化字符串写入buffer，然后赋给string型。
136. Single Number
题意：不准使用hash，找出数组中一个只出现一次的数（其它的均出现两次）。
解：
技巧五：一个数，两次异或同一个数后，不变。 a^b = c, c^b = a
技巧六：一个数与0异或，还是其本身。 a^0 = a, 0^a = a 这样，对于整个数组，只需要全部与0进行异或，最终结果就是那个只出现一次的数。
476. Number Complement
题意：求数的补数，例如5是101，那么他的补数是010，2。
解：c++中，可以使用～来按位取反，似乎对一个整数按位取反即可，但是32位int的5的表示不止是101，而是29个0加上101。如果直接使用～，那么前面的29个0是也要反转的。 那么方法就是只反转最后的101，然后前面保持不变。方法之一就是： 构造一个mask数：高位部分（num数中1出现的最高位往上）全0，低位部分全1，然后mask与完全反转的num按位与即可。理解：如果num是负数，高位部分都是1。例如-5，那么这里的高位部分就不是前29位了。 构造mask的方法：使用一个全1的数（使用～0或者INT_MIN）与num进行按位与操作，如果结果大于0，那么将全1的数左移，直到高位部分全1，低位部分全0，之后在将该数按位取反即可得到mask。
461. Hamming Distance
题意：汉明距离就是二进制之间的差异的个数。
解：先将两个数异或，那么结果的数中的1代表了二者之间的不同的位数，0代表了二者之间相等的数。之后的解法就是技巧三。
190. Reverse Bits
题意：反转一个int型值。
解：想办法构造一个新的值（result）。 对原来的值x，取出最后一位，当作新值result的第一位。如何做到： （1）取x的第最后一位，参考技巧三， （2）构造一个值y，y最后一位和x的最后一位一样，其余全为0 （3）result初始值为全0，然后将y与result进行按位或。 这样，result的最后一位和原来的值x最后一位相同。然后将result左移一位，让最后一位向高位移动。 每次循环取出第i位，然后，result也不断移动，保证最后一位被赋予最新值。
371. Sum of Two Integers
题意：不使用加操作实现两整数之和。
解：此题解法有多种，最简单的方法： 例如a+b：从最低位开始，一个一个的取a和b的该位的数lower_a和lower_b。该位取0还是1，取决于lower_a，lower_b，carry中为1的数量是奇数还是偶数，若是奇数则为1，若为偶数则为0。
技巧七：判断若干个1位bit数中1的个数是奇数还是偶数：所有的数相异或。 求下一位的carry，是在上一位的carry，上一位的lower_a和lower_b三个数中，如果至少有两个数等于1，那么就为1，否则就为0。
技巧八：判断三个数是否存在至少两个数等于1 carry = (carry & lower_a) | (carry & lower_b) | (lower_a & lower_b) 三个数两两相按位与，如果不足两个数等于1，那么不存在结果为1的情况，反之，一定出现。 最终要把每位的结果拼接到全0的数：
技巧九：修改一个全0数的第i位的bit num |= bit « i
技巧十：设置一个数的第i位的bit
思路：先将一个数的第i位的bit清零，然后使用技巧九 清零第i位的bit： num &= ~(1 « i)
89. Gray Code
题意: 给出格雷码的比特数，求全0开始向后的连续的所有格雷码。
解：首先明白什么是格雷码是什么。格雷码是提高传输步进（例如传3后在传4）的时候的稳定性而对数字进行重新编码。每个编码之间差异只为1个bit。例如原来的先传3，在传4，即011到100，会发生三个bit位的翻转，而重新编码之后，用010来表示3，110来表示4，之间差距只为1个bit。 所以此题解法要利用普通二进制转化为格雷码的一个公式：格雷码 ＝ 二进制码 ^ (二进制码／2)。 所以，以求3位的所有格雷码为例，从0开始，每次加1，直到8（也就是1000，也就是1 « 3）,利用公式，计算格雷码，即可。
268. Missing Number
题意:求大小为n的数组中缺失的0-n之间的一个数字。
解：方法一：利用本来的和，然后减去每个数字。 方法二：二分搜索，不过只适用于数组是排序的，能用当然比其他方法好。是logn时间的 方法三：异或操作。利用技巧5，然后巧妙的在循环过程中，和下标异或一次，然后在和该下标的所在值异或一次。这样最终结果就是不能清零的那个缺失数。res初始化为数组的大小，因为下标中不存在该数。
技巧十一： 判断一个数是不是2的n次方。 num & (num - 1) == 0 ？ 是 ：不是 理解：一个数如果是2的n次方，那么它减1后除了最高位为0，以外全是1。以8为例，1000&0111 == 0000 注意2的0次方是个例外情况。
318. Maximum Product of Word Lengths
题意：给出单词数组，求其中最长的两个单词的积，但是这两个单词不能包含相同的字符。
解：：此题如果使用暴力解，设单词长度是L，数组大小是S，时间复杂度为O(S^2 * S * L)。因为每个单词与剩余单词比较是否有相同单词要消耗S*L的时间。所以此题关键是优化这个比较时间，使用的方法是bit操作，一开始就把每个单词转换成一个对应的整数，整数转成二进制后，每一位10代表该单词26个字母出现与否。这样只要比较两个对应整数相与是不是等于0就可以了，这样时间复杂度下降到了O(S^2 + S * L)。
289. Game of Life
题意：mxn棋盘，每个位置只有0或1，表示死的，或者活的，现在指定如下规律： （1）一个位置如果周围邻居（上下左右对角线都算邻居）少于2个，那么会死亡 （2）一个位置如果周围邻居多于3个，那么死亡，由于竞争 （3）一个位置，如果周围恰好有3个邻居，那么会复活，由于繁殖 （4）一个位置，如果周围邻居是2个或3个，而且自己是活着的，那么会继续生存到下一代 现在给出一个初始的棋盘，要我们求的是下一代的状况。要求不使用额外空间，而且要注意一代的更新是同时发生的。
解：此题关键是不能使用额外空间，怎么做到呢？观察题目给出的参数就是int，而int里面的值只有0或者1，所以这就给了很大的空间来进行改造。这样，使用两位来表示，第0位表示原来的0或1状态，第1位表示应该变化的情况，所以，第一遍扫描整个矩阵时候，对于一个位置，我们先把该位置所有邻居状态的第0位取出来得出原来状态，然后就可以知道当前位置应该是什么状态了，修改当前的第1位。然后进行第二遍扫描，这次看的就是第1位了，把数字真正的修改为0或1。
393. UTF-8 Validation
题意：给出整数数组，每个数字代表了utf-8编码中的一个字节，验证整数数组能不能是合法的utf8。
解：首先说明一下什么是utf-8，utf-8是变长字符集，他和Unicode的关系是：utf-8只是Unicode的一种实现方式，Unicode只是单纯的给字符编了码，但是没有固定成某种长度的字节。utf-8是变长的，左手边第一个字节可以看出具体有几个字节，如果是0开头，那么代表只有一个字节，如果是1开头，那么要看一开始有几个1，那就是几个字节，后面跟的几个字节都是以10开头。 先判断第一个字节，然后就知道后面需要看几个字节，也就是说根据第一个字节来影响全局变量，使得后面的处理发生变化。
给一个数x，求2^k，k代表x的二进制形式有多少个连续的0结尾： 可以使用右移操作做判断，不过循环消耗logn的时间，因为循环次数的期望就是logn。 可以直接使用O（1）的位运算操作：x & (-x), 其中x >= 0。
