大家好，欢迎来到IT知识分享网。
一、位运算符及其优先级
我们知道，计算机中的数在内存中都是以二进制形式进行存储的 ，而位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。
注意：参与位运算的对象只能是整型数据(int, unsigned, char)，不能为实型
异或运算符的运算律
- 异或0：a^0 = a;
- 消消乐：a^a = 0;
- 交换律和结合律：a^b^c = a^c^b; a^b^c = a^(b^c);
位运算符的优先级
优先级需要弄清楚，如果不太清楚可以加小括号确保是想要的运算顺序，这里只是相对优先级，即只是和一些常用的算术运算符做比较。
二、位运算的应用
2.1 判断位
给一个数n，确定它的二进制表示中的第x位是0还是1
算法：(n>>x)&1
原理：按位与的运算规则——有0则0，遇1不变
举例：判断第3位
- //n
00011001 //n>>3
00000001 //&1
00000001 //结果
2.2 打开位
将一个数n二进制表示的第x位修改成1
算法：n |= (1<<x)
原理：按位或的运算规则——有1则1，遇0不变
举例：打开第4位
- //目标
00010000 //1<<4
//|= 得结果
2.3 关闭位
将一个数n二进制表示的第x位修改成0
算法：n &= ~(1<<x)
原理：按位与的运算规则——有0则0，遇1不变
举例：关闭第7位
- //目标
//1<<7
0 //~(1<<7)
0 //&= 得结果
2.4 转置位
将一个数n二进制表示的第x位转置（0变1，1变0）
算法：n ^= (1<<x)
原理：按位异或的运算规则——0变1，1变0
举例：转置第4位
- //目标
00010000 //1<<4
//^= 得结果
2.5 位图
定义和特性：位图是一种数据结构，它由一个二进制位数组或者比特数组组成，每个位（bit）只能存储 0 或 1。位图通常被用来表示大量整数的集合，通过位的状态来表示该整数是否出现在集合中。位图支持高效的位操作（如按位与、按位或、按位异或等），适合用于高效地存储和操作大量的布尔型数据。
实现方式：位图可以被实现为一个数组，其中每个元素都是一个字节，而每个字节又包含8个位。对于很大的位图，可以使用多个数组进行分段存储。位图通常不仅仅用于表示整数的集合，还可以用于标记某个特定值是否存在。
详细内容请阅读文章：【高阶数据结构】哈希的其他应用 {位图的介绍及实现，位图的组合应用；布隆过滤器的介绍及实现，布隆过滤器的应用；哈希切分}-CSDN博客
2.6 get lowbit
提取一个数n二进制表示中最低位的1
算法：n==INT_MIN? INT_MIN:n&-n
原理：-n（按位取反再加1）将最低位的1左边的位（不包括logbit位）全部转置，左边转置后按位与得0，右边相同位按位与不变。
举例：
- //目标
00 //-n
00001000 //& 得结果
提示：需要特殊处理INT_MIN()因为-INT_MIN按位取反再加1的操作会发生溢出，而实际上INT_MIN本身就是最低位的1。
2.7 close lowbit
关闭一个数n二进制表示中最低位的1
算法：n & (n-1)
原理：n-1 将最低位的1右边的位（包括logbit位）全部转置，左边相同位按位与不变，右边转置后按位与得0。
举例：
- //目标
//n-1
//& 得结果
2.8 其他
- 位运算实现乘除法：将a左移一位实现*2，将a右移一位实现/2。
- a < < n ≡ a ∗ 2^n
- a > > n ≡ a / 2^n
- 统计二进制数中有多少个1：
int func(int x){ int count=0; while (x) { count++; x=x&(x-1); //将lowbit关闭 } return count; } - 字符的大小写转换：对应大小写字母ASSIC码的二进制数只有第5位不同（大写为0，小写为1），因此可以通过操作第5位实现大小的相互转换
- 字符小写转大写：
ch&=~32;
- 字符大写转小写：
ch|=32; - 字符大小写互换：
ch^=32;
- 字符小写转大写：
- 交换两变量的值：
a=a^b; b=a^b; a=a^b;（异或运算符的运算律：结合律、消消乐）
三、相关编程题
3.1 位1的个数
题目链接
191. 位1的个数 – 力扣（LeetCode）
题目描述
算法原理
不断的close lowbit，每关闭一个1count就++，直到将所有的1都关闭，量的值变为0。
编写代码
class Solution {
public: int hammingWeight(int n) {
int count = 0; while(n>0) {
n &= (n-1); ++count; } return count; } }; 3.2 比特位计数
题目链接
338. 比特位计数 – 力扣（LeetCode）
题目描述
算法原理
同上 close lowbit
编写代码
class Solution {
public: vector<int> countBits(int n) {
vector<int> ans(n+1, 0); for(int i = 0; i <= n; ++i) {
int count = 0; int k = i; while(k>0) {
++count; k &= k-1; } ans[i] = count; } return ans; } }; 3.3 汉明距离
题目链接
461. 汉明距离 – 力扣（LeetCode）
题目描述
算法原理
异或运算：相异为1，相同为0。tmp = x^y将x和y二进制表示中不同的位置置为1，相同的位置置为0。再统计tmp中位1的个数即可，原理同上 close lowbit
编写代码
class Solution {
public: int hammingDistance(int x, int y) {
int tmp = x ^ y; int count = 0; while(tmp>0) {
++count; tmp &= tmp-1; } return count; } }; 3.4 只出现一次的数字
题目链接
136. 只出现一次的数字 – 力扣（LeetCode）
题目描述
算法原理
异或运算的运算律：消消乐
编写代码
class Solution {
public: int singleNumber(vector<int>& nums) {
int ret = 0; for(auto e : nums) {
ret ^= e; } return ret; } }; 3.5 只出现一次的数Ⅲ
题目链接
260. 只出现一次的数字 III – 力扣（LeetCode）
题目描述
算法原理
- 将所有的数按位异或到tmp，最终其实就是只出现一次的两个数的异或结果，即将两个数不同的位置置为1。
- get lowbit将tmp的最低位1取出（还是存入tmp）。注意有符号数需要特殊处理INT_MIN（符号位为1，其他位为0），有符号数取反的位操作是：符号位不变，其他位取反再+1。INT_MIN取反会溢出。实际上INT_MIN的lowbit就是它本身。
- 再次遍历数组，判断所有数的tmp位（异或结果的最低位1），将只出现一次的两个数分到不同的组中进行异或，最终就能分别得到这两个数了。
编写代码
class Solution {
public: vector<int> singleNumber(vector<int>& nums) {
int tmp = 0; for(auto e : nums) {
tmp ^= e; } tmp = tmp==INT_MIN? tmp:tmp&(-tmp); //get lowbit vector<int> ret(2, 0); for(auto e : nums) {
if(e & tmp) {
ret[0] ^= e; } else {
ret[1] ^= e; } } return ret; } }; 3.6 判定字符是否唯一
题目链接
面试题 01.01. 判定字符是否唯一 – 力扣（LeetCode）
题目描述
算法原理
编写代码
//用一个int数据充当位图 class Solution {
public: bool isUnique(string astr) {
// 利用鸽巢原理进行优化 if(astr.size() > 26) return false; // 用位图判断一个字符是否在集合中 int bitmap = 0; for(auto e : astr) {
int tmp = 1 << (e-'a'); if(!(bitmap & tmp)) {
bitmap |= tmp; } else {
return false; } } return true; } }; //用STL的bitset数据结构 class Solution {
public: bool isUnique(string astr) {
if(astr.size() > 26) return false; bitset<26> bs; for(auto e : astr) {
int x = e - 'a'; //位图的第x位 if(!bs.test(x)) {
bs.set(x); } else {
return false; } } return true; } }; 3.7 丢失的数字
题目链接
268. 丢失的数字 – 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public: int missingNumber(vector<int>& nums) {
int ret = 0; int i = 0; for(; i < nums.size(); ++i) {
ret ^= nums[i]; ret ^= i; } ret ^= i; return ret; } }; 3.8 两整数之和
题目链接
371. 两整数之和 – 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public: int getSum(int a, int b) {
int bitsum = a ^ b; //无进位相加的结果 int bitcarry = (a & b)<<1; //进位的结果 while(bitcarry != 0) //当不再有进位时退出循环 {
a = bitsum; b = bitcarry; bitsum = a ^ b; bitcarry = (a & b)<<1; } return bitsum; } }; 3.9 只出现一次的数字Ⅱ
题目链接
137. 只出现一次的数字 II – 力扣（LeetCode）
题目描述
算法原理
依次确定每一个二进制位
为了方便叙述，我们称「只出现了一次的元素」为「答案」。
由于数组中的元素都在 int（即 32 位整数）范围内，因此我们可以依次计算答案的每一个二进制位是 0 还是 1。
具体地，考虑答案的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。因此：
答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
这样一来，对于数组中的每一个元素 x，我们使用位运算 (x >> i) & 1得到 x 的第 i 个二进制位，并将它们相加再对 3 取余，得到的结果一定为 0 或 1，即为答案的第 i 个二进制位。
编写代码
class Solution {
public: int singleNumber(vector<int>& nums) {
int ret = 0; for(size_t i = 0; i < 32; ++i) {
int bitsum = 0; for(auto e : nums) {
bitsum+=(e>>i)&1; } bitsum %= 3; ret |= (bitsum<<i); } return ret; } }; 3.10 消失的两个数字
题目链接
面试题 17.19. 消失的两个数字 – 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public: vector<int> missingTwo(vector<int>& nums) {
int tmp = 0; //异或到一起 for(auto e : nums) tmp ^= e; //原数组 for(int i = 1; i<=nums.size()+2; ++i) tmp ^= i; //全数组 //此时的tmp种存放的是消失的两个数字的异或结果 int lowbit = tmp==INT_MIN? tmp:tmp&(-tmp); vector<int> ret(2, 0); //划分成两类异或 for(auto e : nums) //原数组 if(e & lowbit) ret[0] ^= e; else ret[1] ^= e; for(int i = 1; i<=nums.size()+2; ++i) //全数组 if(i & lowbit) ret[0] ^= i; else ret[1] ^= i; return ret; } }; 免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/122017.html
