位运算是什么？

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

实际运用

1.找出数组中只出现过一次的数

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

题目的关键点是，其他数都出现了两次，这时可以想到异或的妙用。

a^a = 0;
a^0 = a;
a^b^a = a^a^b = 0^b = b;

通过前两条特性，以及最后的异或交换律，我们只需要将数组的每个元素依次异或，最后的结果就是只出现一次的那个数了。

如果是其他元素出现过三次，只有一个数出现过一次，该怎么做呢？

稍微转变下思路，

2. 位1的个数

要如何求出一个整数的二进制下，其中有多少个1呢？

设整数为n，进行n&(n-1)

起初我也不清楚这是什么意思，不如举个例子好了。

假设n=1101 n-1=1100 n&(n-1)=1100

也就是将n这个数，去掉了最末尾的1了。

如果n=10110 n-1=10101 n&(n-1)=10100,也还是一样的意思。

通过不断的循环，做了几次这样的操作，就能知道n有几个1了。

代码：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int result =0;
        while(n)
        {
            n=n&(n-1);
            result++;
        }
        return result;
    }
};

引申一下，判断一个数是不是2的幂次方，要怎么做呢？

2的幂次方，都只有一个1，比如4（100），8（1000），也是同样的解法了。

3. 将2进制数颠倒

颠倒给定的 32 位无符号整数的二进制位.

要怎么做呢？其实就是再申请一个变量。

uint32_t reverseBits(uint32_t n) {
        int res =0 ;
        for(int i=0;i<32;i++)
        {
            res = res<<1;
            res += n&1;
            n=n>>1;
        }
        return res;
    }

每次将这个变量左移1位，空出最后一位来存放数据，也实现了先入的数往前移动的操作。 比如1«1 = 10；

之后，通过n&1的操作，得到n的最后一位。

比如n=1101 n&1=1。

n=n»1, 1101就变成110了，之后再与1，则会得到0.

循环32次，就能实现颠倒了。

4.

没有4了，位运算其实是一个比较小的知识点，有多余的时间不如去学习一下更常用的知识，比如二分查找，动态规划，数据结构等等，能够理解上面的3道例题，以及下列公式的话，也算是基本了解了。

• 位移操作 » 和«

对于二进制数来说，左移一位就是在末尾增加了一个0，右移则是抹掉最后一位数。转换成具体的数字来看： 2=0b10 2«1 = 0b100; 2=0b10 2»1 = 0b1; 将结果转成二进制来看，不难得出的是，位移1格就相当于乘以2或者除以2。位移多次，也就是乘以或除以2的次方。

• 异或操作

老生常谈的A^A=0 A^0=A 以及异或的交换律，知道这样也就足够了。

如果说要比较冷门的知识，那就是通过异或操作，来交换两个变量的值了。 a=a^b; b=a^b; a=a^b;

• 提取末尾的1

n&(n-1)，运算后结果就是去掉最末的1，变成0。

公式表