您的位置:首页 > 财经 > 金融 > 【C++算法】位运算

【C++算法】位运算

2024/11/9 8:37:04 来源:https://blog.csdn.net/dab112/article/details/142041954  浏览:    关键词:【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)

 判断字符是否唯一

  • 题目链接

判断字符是否唯一icon-default.png?t=O83Ahttps://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;}
};

 俩整数之和

  • 题目链接

俩整数之和icon-default.png?t=O83Ahttps://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

  • 题目链接

只出现一次的数字IIicon-default.png?t=O83Ahttps://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;}
};

消失的俩个数字

  • 题目链接

消失的俩个数字icon-default.png?t=O83Ahttps://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;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com