leetcode-位运算题型

C++ 中的位运算符主要用于对整数的二进制表示进行操作。这些操作效率高，常用于嵌入式开发、图形学、算法优化等场景。以下是 C++ 中的几种常见位运算符及一些常用的二进制操作：

1. 位运算符

1.1 按位与 &

按位与操作符 & 会将两个整数的每一位进行 与操作。只有当对应位都是 1 时，结果才为 1。

int a = 6; // 二进制: 110 
int b = 3; // 二进制: 011 
int result = a & b; // 结果为 2 (二进制: 010)

1.2 按位或 |

按位或操作符 | 会将两个整数的每一位进行 或操作。只要有一个对应位是 1，结果就为 1。

int a = 6;  // 二进制: 110
int b = 3;  // 二进制: 011
int result = a | b;  // 结果为 7 (二进制: 111)

1.3 按位异或 ^

按位异或操作符 ^ 会将两个整数的每一位进行 异或操作。当对应位不同，结果为 1；相同则为 0。

int a = 6;  // 二进制: 110
int b = 3;  // 二进制: 011
int result = a ^ b;  // 结果为 5 (二进制: 101)

1.4 按位取反 ~

按位取反操作符 ~ 会将数的每一位取反（0 变成 1，1 变成 0）。

int a = 6;  // 二进制: 0000 0110
int result = ~a;  // 结果为 -7 (二进制: 1111 1001)

1.5 左移 <<

左移操作符 << 会将数的所有位向左移动指定的位数，右侧补 0。左移相当于乘以 2。

int a = 3;  // 二进制: 11
int result = a << 2;  // 结果为 12 (二进制: 1100)

1.6 右移 >>

右移操作符 >> 会将数的所有位向右移动指定的位数。对正数，右侧补 0；对负数，视编译器和机器的实现。

int a = 12;  // 二进制: 1100
int result = a >> 2;  // 结果为 3 (二进制: 11)

2. 常用的二进制操作

2.1 判断奇偶性

如果一个数的最低位为 1，则为奇数；最低位为 0，则为偶数。

bool isOdd = (num & 1) == 1;

2.2 计算整数的二进制中 1 的个数（位计数）

int countOnes(int num) {int count = 0;while (num) {count += num & 1;num >>= 1;}return count;
}

或者更高效的方法（利用 num & (num - 1) 清除最低位的 1）：

int countOnes(int num) {int count = 0;while (num) {num = num & (num - 1);count++;}return count;
}

2.3 判断一个数是否是 2 的幂

一个数若是 2 的幂，那么它的二进制表示中只有一个 1。

bool isPowerOfTwo(int num) {return num > 0 && (num & (num - 1)) == 0;
}

2.4 将第 `k` 位设置为 1

num |= (1 << k);

2.5 将第 `k` 位设置为 0

num &= ~(1 << k);

2.6 检查第 `k` 位是否为 1

bool isKthBitSet = (num & (1 << k)) != 0;

3.题目

136. 只出现一次的数字

137. 只出现一次的数字 II

哈希法

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_map<int, int> hash;for(int i=0; i< nums.size(); i++){if(hash.find(nums[i]) == hash.end()){hash[nums[i]]++;}else if(hash[nums[i]] == 2){hash.erase(nums[i]);}else{hash[nums[i]]++;}}int ans;for(auto [i,j] : hash){ans = i;}return ans;}
};