LeetCode|LeetCode总结，位运算总结 LeetCode解题报告|OJ

对于位运算面试问题，其实我觉得是最不好处理的一类问题，原因在于他的技巧性和规律性太强，往往需要根据若干种基本运算规则（见下面）及其组合达到特定目的运算，难就难在技巧性。本文罗列了几种常见的位运算面试问题。

一，位运算基础知识 C++中位运算基本符号：~|&^<<>> !
其中！和 ~ 是不同的。
基本的位操作符有与、或、非，异或、同或、取反、左移、右移这8种，它们的运算规则如下所示：

与运算 -----&
或运算 -----|
取反-----~//~0=1
异或-----^//异则为真，0^1=1,1^1=0,0^0=0
同或-----~(^)// C++中并无该符号，他是先异或后求反的组合结果，与异或结果相反
左移------< 右移------>>
非------!
这一系列基本的运算可以组合出很多其他功能的运算。
以下是基本运算的示例。

位运算	或 “\|”	与 “&”	非 “~”	异或 “^”
操作数1	01010101	11010101	10101010	10000001
操作数2	00101010	10101010	(无)	01111111
也能算结果	01111111	10000000	01010101	11111110

以下内容转载自morewindows
下面对位操作的一些常见应用作个总结，有判断奇偶、交换两数、变换符号及求绝对值。这些小技巧应用易记，应当熟练掌握。
1．判断奇偶
只需根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if ((a & 0x0001) == 0)代替if (a % 2 == 0)来判断a是不是偶数。
下面程序将输出0到100之间的所有奇数。

for (i = 0; i < 100; ++i) if (i & 1) printf("%d ", i); putchar('\n');

2．交换两数
一般的写法是：

void Swap(int &a, int &b) { if (a != b) { int c = a; a = b; b = c; } }

可以用位操作来实现交换两数而不用第三方变量：

void Swap(int &a, int &b) { if (a != b) { a ^= b; //a=(a^b) b ^= a; //b=(b^a)=(b^a^b)=(b^b^a)=a a ^= b; //a=(a^b)=(a^b^a) } }

可以这样理解：
第一步a^=b 即a=(a^b);
第二步b^=a 即b=b^(a^b)，由于^运算满足交换律，b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。
第三步 a^=b 就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a会被赋上b的值。

3．变换符号
变换符号就是正数变成负数，负数变成正数。
如对于-11和11，可以通过下面的变换方法将-11变成11
1111 0101(二进制) –取反-> 0000 1010(二进制) –加1-> 0000 1011(二进制)
同样可以这样的将11变成-11
0000 1011(二进制) –取反-> 0000 0100(二进制) –加1-> 1111 0101(二进制)
因此变换符号只需要取反后加1即可。完整代码如下：

#include int SignReversal(int a) { return ~a + 1; } int main() { int a = 7, b = -12345; printf("%d%d\n", SignReversal(a), SignReversal(b)); return 0; }

4．求绝对值
位操作也可以用来求绝对值，对于负数可以通过对其取反后加1来得到正数。对-6可以这样：
1111 1010(二进制) –取反->0000 0101(二进制) -加1-> 0000 0110(二进制)
来得到6。
因此先移位来取符号位，int i = a >> 31;
要注意如果a为正数，i等于0，为负数，i等于-1。
然后对i进行判断——如果i等于0，直接返回。否之，返回~a+1。完整代码如下：

int my_abs(int a) { int i = a >> 31; return i == 0 ? a : (~a + 1); }

现在再分析下。对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。所以可以对上面代码优化下：

int my_abs(int a) { int i = a >> 31; return ((a ^ i) - i); }

注意这种方法没用任何判断表达式，而且有些笔面试题就要求这样做，因此建议读者记住该方法（^_^讲解过后应该是比较好记了）。

二，自己简单归类的： 1， 136 / 137 / 260 Single Number（I / II / III），
与此题类似 268. Missing Number

题目翻译：
给定一个整数数组，每个元素会出现两次，但是除了一个。找到这个数。
分析：
异或，异则真，同则假。XOR (^)
异或的性质1：交换律a ^ b = b ^ a，性质2：0 ^ a = a。
所有元素依次异或，最终结果就是出现一次的数

2， 190. Reverse Bits

题目翻译：
逆反32位无符号整数位。
例如，给定的输入43261596（以二进制表示为000000 10100101000001111010011100），返回964176192（以二进制表示为00111001011110000010100101000000）。
更进一步：
如果这个函数被调用多次，你会如何优化呢？

分析：典型的位运算
逆反，则需要将低位变成高位，所以迭代开始就需要我们先取出末尾，然后将原来的低位结果*2，再加上当前位
，最后原数需要右移一维，见代码，一目了然：

class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t result=0; uint32_t num=n; for(int i=0; i<32 ; i++) { int endbit=num & 0x0001; //取末尾位 result= (result << 1) + endbit; //逆置,往左移动，为什么一定要加个括号呢？ num=num >> 1; //往右移动一位 } return result; } };

3， 191. Number of 1 Bits

题目翻译：
写一个函数，将一个无符号整数并返回数字“1”位有（也被称为汉明重量）。
例如，32位整数“11”具有二进制表示0000000000000000000000000000 1011，所以函数应该返回3。

分析：
首先这个数是正整数，题目说的很清楚
每次循环减少该数n二进制最右边的1 ---》n=n&n-1
比如有5个1，则循环5次（减少5次）
或者每次判断该数末尾是否为1，是就累加个数，然后就把原数右移。

4， 201. Bitwise AND of Numbers Range

题目翻译：
0 <= m <= n <= 2147483647，求取m到n相与运算的结果。

分析：

m到n之间的数的低位只要不相同，相与就是0，所有数的高位（通过位移实现）相同即可得到结果，但是高位不相同直接就是0。
比如【5，6，7】二进制表示分别为：、
101
110
& 111
显然三数只有第一列是相同的，所以结果显然是100

又比如【1，2，3，4】二进制表示分别为：
001
010
011
& 100
显然所有同一列的位均不相同，结果为0.
那么怎么得到哪些列的1位是相同的？右移运算！所有数同时右移运算后的结果相同，此时就是答案，但是如果谁先被移位为0，显然结果就是0。
通过别人的提示发现，实际m到n之间的所有数相与，只需这m，n两个数计算即可（因为m和n是最难保持一致，如果他们都通过移位保持一致了，那么中间那些数一定也可以保持一致）。

5， 231. Power of Two

题目翻译：
判断一个数是否是2的幂

分析：
思路首先：
如果一个数是2的某个次方，那么他一定不会小于等于0（最多无限接近0）
如果n是2的某个次方，那么他的二进制形式一定是10000......这样的形式
并且n-1的二进制形式一定是01111....，进行与运算一定是00000......0，
即n&n-1即可判断题目。

6， 318. Maximum Product of Word Lengths
将字符与位运算结合的典型例子

题目翻译：
给定一个字符串数组 words找到最大值 length(word[i]) * length(word[j])且这两个词必须不包含共同的字符。你应该认为每个单词只包含小写字母。
如果不存在这样的两个词,返回0。

分析：
根据题目的描述，我们可知，最耗时的地方在于判断两个字符串中是否存在重复的字符。
一提到判断重复字符，脑海中马上浮现哈希大法。
又看到题目要保证字符串均为小写字母，也就说总共26个字母，我们需要26位，一个int足矣。
我们自定义，如果某字符出现，该bit置1，否则置0.（将第i个字符串转化成在1个int里，比如abc,将被转化成0000...0111 ）则比较两个字符串是否有重复字符，就是让这两个标志int 进行与操作，结果为0则表明没有重复字符。
好的，本题的难点已结束。code如下：

7， 338. Counting Bits

题目翻译：
给定一个非负整数Num。每一个数字i均在范围0≤i≤Num，计算每一个i二进制中1的个数，存放在数组中返回。
例子：

num = 5你应该返回[ 0,1,1,2,1,2 ]。
要求:

一个运行时间为O（n * sizeof（integer））的解决方案很容易。但你能在线性时间O（N）解决问题吗？

空间复杂度应该O（N）。

不使用任何内建函数

提示：

你应该充分利用你已经计算出来的结果（赶紧想到动态规划）。

分析：
动态规划

可以从每个数的最低位开始分析，例如1001001 ，它的二进制1的个数等于100100 总二进制个数 + 1 。
即 f = f/2 + (f 的最低位)

8， 371. Sum of Two Integers
题目翻译

计算两个整数A和B相加，但你不允许使用运算符+和-。
例子：
例如，A= 1 和 B = 2, return 3.

分析：

可以很容易地用“异或”和“或”操作模拟实现整数加法运算：对应位数的“异或操作”可得到该位的数值，对应位的“与操作”可得到该位产生的高位进位，如：a=010010，b=100111，计算步骤如下：
第一轮：a^b=110101，(a&b)<<1=000100，由于进位（000100）大于0，
则进入下一轮计算，a=110101，b=000100，a^b=110001，(a&b)<<1=001000，
由于进位大于0，则进入下一轮计算：a=110001，b=001000，a^b=111001，(a&b)<<1=0，
进位为0，终止，计算结果为：111001。

注：本博文为EbowTang原创，后续可能继续更新本文。如果转载，请务必复制本条信息！
原文地址：http://blog.csdn.net/ebowtang/article/details/50526099
原作者博客：http://blog.csdn.net/ebowtang

参考资源：
【LeetCode|LeetCode总结，位运算总结】【1】位操作基础篇之位操作全面总结