有不少人对位运算感到陌生，一是因为我们不习惯用二进制的形式来进行计算，二是我们遇到的题目较少，并且很不熟练。可能我们遇到数组、链表等常见数据结构类的问题时做起来很顺利，哪怕是中等或者困难的题目也能完成，但是遇到关于位运算的简单题目却无从下手，下面我将分析几道leetcode上面的几道简单且经典的位运算题目，供大家做参考。
在分析题目之前，我先带大家熟悉下位运算的几种常见符号。
&：按位与运算。同1为1，否则为0。例：0&0=0；0&1=0；1&0=0；1&1=1；
|： 按位或运算。有1为1， 没1为0。 例：0|0=0；? 0|1=1；? 1|0=1； 1|1=1;
^： 按位异或运算。相异为1，相同为0。例：0^0=0;? 0^1=1;? 1^0=1; 1^1=0;
~：取反运算。 ~1=0；~0=1;
<<：左移运算符。左边的二进制位丢弃，右边补0。例：1011 左移一位后变为 10110；左移几位? ? ? ? ? ? 就是乘2^n次方。
>>：右移运算符。正数左补0，负数左补1，右边丢弃。例：1011 右移一位后变为101，最后一位? ? ? ? ? 丢弃；右移几位就是除2^n次方。
（1）给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回false 。如果存在一个整数 x 使得?n =?2^x?，则认为 n 是 2 的幂次方。
?通过分析题目，我们首先发现可以让n这个数一直除2，直到最后看是否等于1或者等于0，这不就是递归吗，我们可以很容易的写出递归的代码，代码如下：
class Solution {
public:
bool isPowerOfTwo ( int n )
{
//递归终止条件，如果n=1则返回true，2^0=1;
if ( n == 1 )
return true;
if ( n == 0 )
return false;
//如果n为偶数的话，则递归遍历
if ( n % 2 == 0 )
return isPowerOfTwo ( n / 2 );
//否则是奇数，返回false
else
return false;
}
};但我们怎么利用位运算来解决本道题呢，我们通过举例发现：8的二进制形式为1000，而7的二进制形式为0111，如果题目输入的n是8的情况时，显然是返回true的。我们套用上面的按位运算，发现当8和7进行按位与运算时，最终答案竟然是0。再带入其他数字，例如16的二进制数为10000，而15的二进制数为01111，两者按位与运算同样是0。所以可以得出规律，二的倍数和二的倍数减一的按位与运算结果为0，我们得到如下代码。
class Solution {
public:
bool isPowerOfTwo ( int n )
{
//如果n为1时返回true
if ( n == 1 )
return true;
if ( n < 1 )
return false;
//返回n&n-1的结果，如果为0则为true，否则返回false
//特别提示：&的优先级要小于==的优先级，所以&的两边要加上括号
return ( n & ( n - 1 ) == 0;
}
};（2）编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数
此题同样要使用二进制位运算来解题，下面给出第一种写法：可以发现当让n&（n-1）时，n的最低位的1会变为0，我们利用这个特性，可以让n不停的和n-1进行与运算，直到n为0，下面给出我们的代码：
class Solution {
public:
int hammingWeight ( uint32_t n )
{
//用res来记录为1的个数
int res = 0;
//当n不为0时，一直循环
while ( n )
{
//将n的最低位的1变为0，同时res加1
n = n & ( n - 1 );
res++;
}
return res;
}
};?我们也可以每次找到最低位的1以后，再将二进制代码右移一位，即删除掉那个1，然后依次循环上述过程，找到所有的1，下面给出代码：
class Solution {
public:
int hammingWeight ( uint32_t n )
{
//用res来记录为1的个数
int res = 0;
//因为n是32位，所以需要循环32次，每次左移一位
for ( int i = 0; i < 32; i++ )
{
//如果最后一位和1相与的结果是1，则说明最后一位为1，res+1
if ( ( n & 1 ) == 1 )
res++;
//无论最低为是否为1都需右移一位
n >>= 1;
}
return res;
}
};(3)给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
我看到这题，第一时间想到的是哈希表法，但是题目规定了时间复杂度为线性的，所以我们只能考虑位运算来解决。
回顾异或运算，我们发现异或运算有三个特性：
1、异或运算满足结合律和交换律。例：a^b^c=c^b^a=a^(b^c)；
2、任何数和自身进行异或运算都为0。例：1111^1111=0；
3、任何数和0做异或运算，结果为任何数。例：1111^0=1111；
通过以上的三条特性，我们发现当异或两个相同的数时，答案正好为0，而0和其他数异或正好为其他数，这正好满足题目所给的条件。我们举例子说明：如数组元素为 [2,2,1,1,5],对数组元素依次进行异或运算，2^2^1^1^5=0^5=5；正好等于数组中单着的那个数，我们写出如下代码：
class Solution {
public:
int singleNumber ( vector < int > & nums )
{
//用c来记作返回结果
int c = 0;
//遍历数组所有元素，并且每个进行^运算
for ( auto x : nums )
{
//按位异或每个元素
c ^= x;
}
return c;
}
};?关于位运算的题目，掌握了几种方法，以后遇见就不会觉得难，而不知道这几种方法的做题确实是做不出来，所以二进制的题目还是要多进行积累。