leetcode习题分类汇总- Bit Manipulation篇

Single Number-数组中其他数均出现两次,求唯一出现一次的数字

思路:0^0=0,0^1=1 0异或任何数=任何数,1^0=1,1^1=0 1异或任何数-任何数取反,任何数异或自己=把自己置0






### Number of 1 Bits-数值二进制1的个数

思路:
&:双目运算符,运算时均把运算数转换为二进制再做比较,规则:当相同的位上均为1时结果为1,否则结 果为0.如:1010&1101,转为二进制:
// 10001001101&1111110010比较结果为:1000000转为十进制: 64所以1010&1101=64;





### Single Number II-数组中其他数均出现三次,求唯一出现一次的数字

思路:
这个题有类似于single number的解法,即通过位运算,一遍扫描得到结果。还是读书的时候见过,大概是两个变量,相互做异或、补之类的运算,早不记得详情了。

现在的解法是比较普通的。因为题目已经说了,除了一个数字以外,其他的都出现了3次,如果我们把那个特殊的数剔除,并把剩下的数于每一位来加和的话,每一位上1出现的次数必然都是3的倍数。所以,解法就在这里,将每一位数字分解到32个bit上,统计每一个bit上1出现的次数。最后对于每一个bit上1出现的个数对3取模,剩下的就是结果。



### Reverse Bits-把数字按二进制位倒转并输出

思路:遍历把低位的1,0不断加到result中去



### Bitwise AND of Numbers Range-

给定范围[m, n],其中 0 <= m <= n <= 2147483647,返回范围内所有整数的按位与,包括边界。

例如,给定范围[5, 7], 你应该返回4。

思路:
仔细观察我们可以得出,最后的数是该数字范围内所有的数的左边共同1的部分,如果上面那个例子不太明显,我们再来看一个范围[26, 30],它们的二进制如下:

11010  
11011  
11100  
11101  
11110

发现了规律后,我们只要写代码找到左边公共1的部分即可,我们可以从建立一个32位都是1的mask,然后每次向左移一位,比较m和n是否相同,不同再继续左移一位,直至相同,然后把m和mask相与就是最终结果

总结:考察位运算操作符,这部分经常忘记,面试前要再复习下。