【位运算】位运算常用技巧总结

目录

前言

一.常见的小问题

1.给定一个数n,确定它的二进制表示中的第x位是0还是1

2.给定一个数n，将它的二进制表示中的第x位修改成1

3.给定一个数n，将它的二进制表示中的第x位修改成0

4.给定一个数n，提取它的二进制表示中最右侧的1（即将其它位置位0）

5.给定一个数n，去掉它的二进制表示中最右侧的1

 6.异或运算的规则

二.典型例题

---

前言

位运算是一类常考的题型，关于位运算的操作符有以下几种:

按位取反（~）

左移操作符（<<）

右移操作符（>>）

按位与（&）

按位或 （|）

按位异或（^）

重点要区分&，|和^这几个操作符，按位与是有0则0，按位或是有1则1

按位异或相同为0，相异为1。也可以记成“无进位相加”，例如1+1=2， 因为是二进制所以变成0，但是不进位。

接下来介绍怎么利用这些操作符来解决常见的问题

一.常见的小问题

1.给定一个数n,确定它的二进制表示中的第x位是0还是1

首先声明，默认最低位是第0位。

方法：将n右移x位，与1做按位与操作，若结果为1，则n的第x位是1，若结果是0，则第x位是0

说明：右移操作是为了将第x位移到最低位，方便与1的最低位按位与，而1的其它位全是0，有0则0，故其它位的结果肯定是0，而最低位的结果则取决于x位是0还是1

代码操作：(n >> x) & 1 

2.给定一个数n，将它的二进制表示中的第x位修改成1

方法：将1左移x位，再与n按位或

说明：将1左移x位是为了对n的第x位进行“定向打击”，1的第x位是1，其余位是0。按位或的特点是有1则1，故结果的第x位肯定是1，其它位取决于n的其它位是0还是1,和原来相比不会变化

代码操作：n = (1 << x) | n

3.给定一个数n，将它的二进制表示中的第x位修改成0

方法：将1左移x位，按位取反，再与n按位与

说明：按位与的特点是有0则0，故结果的第x位肯定是0，其它位取决于n的其它位是0还是1，和原来相比不会发生变化

代码操作：n = (~(1 >> x) ) & n

4.给定一个数n，提取它的二进制表示中最右侧的1（即将其它位置位0）

方法：n & -n 

说明：由n向-n转变，先将n按位取反，然后加1，这样使得n最右侧的1，左边区域全变成相反，右边区域全变成0，而按位与的特点是有0则0，故只有最右侧的1异或的结果是1，其余全是0。

5.给定一个数n，去掉它的二进制表示中最右侧的1

方法：n & (n - 1)

说明：由n到n-1，最右侧1的左边区域不变，右边区域（包括1）全部变成相反，按位与的特点是有0则0，故最右侧的1肯定会变成0，其余位不变

 6.异或运算的规则

a ^ 0 = a

a ^ a = 0

a ^ b ^ c = a ^ c ^ b 

二.典型例题

接下来有几道例题，大家可以先尝试做一做，答案放在下面了

位1的个数

class Solution {
public:int hammingWeight(uint32_t n) {int ret = 0;for (int i = 0; i <= 31; i++){if (((n >> i) & 1) == 1){ret++;}}return ret;}
};

比特位计数

class Solution {
public:vector<int> countBits(int n) {//x&(x-1)将x的最右侧的1变成0vector<int> v(n + 1);for (int i = 0; i <= n; i++){int x = i;int count = 0;while (x){count++;x = x & (x - 1);}v[i] = count;}return v;}
};

汉明距离

class Solution {
public:int hammingDistance(int x, int y) {int n = x ^ y;//统计有多少个1int ret = 0;while (n){ret++;n = n & (n - 1);}return ret;}
};

只出现一次的数字

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for (int i = 0; i < nums.size(); i++){ret ^= nums[i];}return ret;}
};

只出现一次的数字iii

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {//目标：将两个单身狗分开，相同的数不拆散，再将两组分别异或//方法：根据两个单身狗任意一个不同的比特位来进行分组int n = 0;for (auto e : nums){n ^= e;}//找到比特位是1的位置--两个单身狗这一位不同int pos = 0;for (int i = 0; i <= 31; i++){if (((n >> i) & 1) == 1) {pos = i;break;}}//根据这一位置的值将所有数分成两组异或int ret1 = 0, ret2 = 0;for (auto e : nums){if (((e >> pos) & 1) == 0){ret1 ^= e;}else{ret2 ^= e;}}return {ret1, ret2};//隐式类型转换}
};