【C++算法】位运算
位运算基础知识
1.基础运算符
<< : 左移
>> : 右移
~ : 取反
& : 按位与，有0就是0
I : 按位或，有1就是1
^ : 按位异或，（1）相同为0，相异为1（2）无进位相加
2.运算的优先级——>能假括号就加括号
3.给一个数n，确定它的二进制表示中的第x位是0还是1？
n : 0 1 1 0 1 0 1 0 0 1
下标：9 8 7 6 5 4 3 2 1 0
表达式：(n >> x) & 1
4.将一个数n的二进制表示的第x位修改成1
0 1 1 0 1 0 1 0 1 1
0 1 1 0 1 1 1 0 1 1
表达式：n |= (1 << x)
5.将一个数n的二进制表示的第x位修改位0
0 1 1 0 1 0 1 0 1 1
0 1 1 0 1 0 0 0 1 1
按位与 & ： 1 1 1 1 1 1 0 1 1 1
表达式：n &= (~(1<<x))
6.位图的思想
7.提取一个数(n)二进制表示中最右侧的1——>lowbit
0 1 1 1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0 0
表达式：n & -n
-n : 按位取反 + 1
-n的本质就是将最右侧的 1 左边的区域全部取反
8.干掉一个数(n)二进制表示中最右侧的1
0 1 1 0 1 0 1 0 0
0 1 1 0 1 0 0 0 0
表达式：n & (n-1)
n-1的本质就是将最右侧的1右边的值和自己取反
9.异或(^)运算符的特性
a ^ 0 = a
a ^ a = 0(消消乐)
a ^ b ^ c = a ^ (b ^ c)
判断字符是否唯一
-
题目链接
判断字符是否唯一
https://leetcode.cn/problems/is-unique-lcci/description/
-
算法原理
-
代码步骤
class Solution {
public:bool isUnique(string astr) {// 鸽巢原理if(astr.size() > 26) return false;int bigmap = 0;for(auto ch : astr){int i = ch - 'a';// 下标为i位置处是否出现过if((bigmap >> i) & 1){return false;}bigmap |= (1 << i);}return true;}
};丢失的数字
-
题目链接
丢失的数字
-
算法原理
-
代码步骤
class Solution {
public:int missingNumber(vector<int>& nums) {int tmp = 0;int n = nums.size();for(auto x : nums){tmp ^= x;}for(int i = 0; i <= n; i++){tmp ^= i;}return tmp;}
};俩整数之和
-
题目链接
俩整数之和https://leetcode.cn/problems/sum-of-two-integers/description/
-
算法原理
-
代码步骤
class Solution {
public:int getSum(int a, int b) {while(b != 0){int x = a ^ b;int y = (a & b) << 1;a = x;b = y;}return a;}
};只出现一次的数字II
-
题目链接
只出现一次的数字IIhttps://leetcode.cn/problems/single-number-ii/description/
-
算法原理
-
代码步骤
class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i < 32; i++){int sum = 0;for(auto ch : nums){if((ch >> i) & 1 == 1) sum++;}if(sum % 3 == 1){ret |= 1 << i;}}return ret;}
};消失的俩个数字
-
题目链接
消失的俩个数字https://leetcode.cn/problems/missing-two-lcci/
-
算法原理
-
代码步骤
class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int n = nums.size();int tmp = 0;for(auto x : nums){tmp ^= x;}for(int i = 1; i <= n + 2; i++){tmp ^= i;}int diff = 0;while(1){if((tmp >> diff) & 1 == 1){break;}diff++;}int a = 0, b = 0;for(auto x : nums){if((x >> diff) & 1 == 1){a ^= x;}else{b ^= x;}}for(int i = 1; i <= n + 2; i++){if((i >> diff) & 1 == 1){a ^= i;}else{b ^= i;}}return {a, b};}
};找单身狗
-
题目链接
-
算法原理
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。
例如：
有数组的元素是：1，2，3，4，5，1，2，3，4，6
只有5和6只出现1次，要找出5和6.
-
代码步骤
//单身狗2
#include<stdio.h>
void Find(int arr[], int sz, int* single_dog)
{//找到数组中不同数字二进制位的不同处//若某个二进制位有不同，则异或之后为1int i = 0;int ret = 0;for (i = 0; i < sz; i++){ret ^= arr[i];}//在32位二进制位上找到异或之后为1的地方，找到一处即可int pos = 0;for (i = 0; i < 32; i++){if (((ret >> i) & 1) == 1){break;}else{++pos;}}//将数组中二进制位在此处的为1或0的分开//分开后将二进制位在此处的为1的全部异或//将二进制位在此处的为0的全部异或for (i = 0; i < sz; i++){if (((arr[i] >> pos) & 1) == 1){single_dog[0] ^= arr[i];}else{single_dog[1] ^= arr[i];}}
}int main(void)
{int arr[] = { 1,2,3,4,5,1,2,3,4,6 };int sz = sizeof(arr) / sizeof(arr[0]);int single_dog[2] = { 0 };Find(arr, sz,single_dog);printf("%d %d", single_dog[0], single_dog[1]);return 0;
}