数据结构-位运算总结

位运算总结：

1.求位1的个数

191. 位1的个数 - 力扣（LeetCode）

有两种写法：

1.是把该数不断的去与0x1相与，得到该数的最后一位的值，然后判断他是不是1，再把该数更新一下整体往后移动一位也就是右移一位。

class Solution {
public:int hammingWeight(int n) {int res = 0;while(n){if(n&0x1)   res++;n = n>>1;}return res;}
};

2.如下有两个重要点：

• 当一个数被减1时，它最右边的那个值为1的bit将变为0，同时其右边的所有的bit都会变成1。
• 每次执行x&（x-1）的作用是把ⅹ对应的二进制数中的最后一位1去掉。因此，循环执行这个操作直到ⅹ等于0的时候，循环的次数就是x对应的二进制数中1的个数。

举例分析：9的二进制表示为1001,8的二进制表示为1000，两者执行&操作之后结果为1000，此时1000再与0111（7的二进制位）执行&操作之后结果为0，得到最终1的个数为0。

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

2.求二进制中0的个数

就是一直在数后面加1，直到这个数他越界等于-1就行了。循环在 n + 1 不为 0 时继续执行。这意味着一旦 n 变为 -1（即 1111 1111 1111 1111 1111 1111 1111 1111），n+1 就会等于 0，循环退出。

class Solution {
public:int CountZeroBit(int n) {int res = 0;while(n+1){res++;n |= (n+1);}return res;}
};

核心操作：n |= (n + 1)：按位或操作将 n 和 n+1 进行或操作，这实际上是将 n 二进制表示中最低位的 0 变为 1。这是因为 n+1 会将最低的 0 位置为 1，而所有更低位的 1 位置为 0，所以与 n 进行或操作后，会将 n 中最低的 0 位置为 1。

3.二进制求和

67. 二进制求和 - 力扣（LeetCode）

模拟，逢二进一，先反转数字，从尾巴开始遍历，然后两对应数字逢二进一，我们提前设置一个carry变量用来存储之前的数据给本位的进位，然后加上本位的数据，在判断本位的数据是否有大于2的然后考虑是否进位，最后再判断最后一个数据是否是有进位，如果有在插入一个，没有的话就反转，输出就行。

class Solution {
public:string addBinary(string a, string b) {string res;reverse(a.begin(),a.end());reverse(b.begin(),b.end());int  n = max(a.size(),b.size());int carry = 0;for(int i=0;i<n;i++){carry+= i<a.size()?(a.at(i)=='1') : 0;carry+= i<b.size()?(b.at(i)=='1') : 0;res.push_back((carry%2)? '1':'0');carry /= 2;}if(carry){res.push_back('1');}reverse(res.begin(),res.end());return res;}
};

4.颠倒二进制位

190. 颠倒二进制位 - 力扣（LeetCode）

将 n 视作一个长为 32 的二进制串，从低位往高位枚举 n 的每一位，将其倒序添加到翻转结果 rev 中

class Solution {
public:uint32_t reverseBits(uint32_t n) {uint32_t rev = 0;for (int i = 0; i < 32 && n > 0; ++i) {rev |= (n & 1) << (31 - i);n >>= 1;}return rev;}
};