【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;
}