位运算
基础
1. & 运算符 : 有 0 就是 0
2. | 运算符 : 有 1 就是 1
3. ^ 运算符 : 相同为0 相异为1 and 无进位相加
位运算的优选级
不用在意优先级,能加括号就加括号给一个数 n ,确定它的二进制位中第 x 位是 0 还是 1?
规定: 题中所说的第x位指:int 在32位机器下4个字节32位,从右向左依次增加,从0位开始,即 第 0 位 到第 31 位.
(n >> x) & 1
- 将一个数 n 的二进制位表示的第 x 位修改为 1
n |= (1 << x)
- 将一个数 n 的二进制表示的 第 x 位修改为 0
n &= ~(1 << x)
- 提取一个数 n 二进制表示中最右侧的1
n & -n;
-n : 将最右侧的1左边的区域全部变为相反数，右边的1的数不变（本来就是0）
0 1 1 0 1 0 1 0 0 0
~ 1 0 0 1 0 1 0 1 1 1
+1 1 0 0 1 0 1 1 0 0 0
n: 0 1 1 0 1 0 1 0 0 0
------------------------
0 0 0 0 0 0 1 0 0 0
- 干掉一个数( n )二进制表示中最右侧的1
n &= (n -1)
- 异或(^)运算的运算律
1. a ^ 0 = a;
2. a ^ a = 0; 消消乐
3. a ^ b ^ c = a ^ (b ^ c) 符合交换律和结合律
异或
无进位相加解释:
1 0 1 1 0 1 0
0 0 1 0 1 0 1
1 0 1 0 0 0 0
-------------
0 0 1 1 1 1 1 --> 两个 1 会消消乐(本质就是1的抵消), 即无进位相加
题目练习
思路一:依次判断每个位是否为1,为 1 ans++;
class Solution {
public:
int hammingWeight(int n) {
int ans = 0;
int sum = 32;
for(int i = 0; i < 32; i++)
{
if((n >> i) & 1)
{
ans++;
}
}
return ans;
}
};
思路二:依次消除最低位的 1, 消除一次 ans++;
class Solution {
public:
int hammingWeight(int n) {
int ans = 0;
while(n)
{
n &= (n -1);
ans++;
}
return ans;
}
};
思路:依次消除最低位的 1, 消除一次 count++; 对每个数字统计一次即可
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans;
for(int i = 0; i <= n; i++)
{
int count = 0;
int temp = i;
while(temp)
{
temp &= (temp - 1);
count++;
}
ans.push_back(count);
}
return ans;
}
};
//思路:先异或(相同为0相异为1)后统计1的个数
class Solution {
public:
int hammingDistance(int x, int y) {
x ^= y;
int ans = 0;
while(x)
{
x &= (x -1);
++ans;
}
return ans;
}
};
//思路:利用异或运算规律:
// 1. a ^ a = 0;
// 2. a ^ 0 = a
// 3. 交换律和结合律
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for(int iter : nums)
{
ans ^= iter;
}
return ans;
}
};
//思路:利用异或的规律,将所有数据异或一次,结果一定是只出现一次的两个元素异或后的结果,然后利用异或的相同为 0 相异为 1,并用最低位 1 来区分两个只出现一次的元素,划分为两个集合(此时每个集合中只有一个数出现一次,其他数都出现了两次),分别异或即可得到结果
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
unsigned int xor_all = 0;
//为什么使用unsigned int ？
//使用int可能会导致溢出
//unsigned int 自动会进行模运算,保证结果始终在unsigned int 表示范围内
//int: (-2^31 到 2^31 - 1)
//unsigned int: (0 ~ 2^32 -1)
for(int iter : nums)
{
xor_all ^= iter;
}
//获取异或结果的最低位为 1 的位
int lowbit = xor_all & (-xor_all);
vector<int> ans(2);
for(int x : nums)
{
if((x & lowbit) == 0)
{
ans[1] ^= x;
}
else
{
ans[0] ^= x;
}
}
return ans;
}
};
思路:使用hash表统计每个字符出现的次数,然后遍历hash表即可
class Solution {
public:
bool isUnique(string astr) {
unordered_map<char,int> hash;
for(int i = 0; i < astr.size(); i++)
{
hash[astr[i]]++;
}
for(auto iter : hash)
{
if(iter.second > 1)
{
return false;
}
}
return true;
}
};
class Solution {
public:
bool isUnique(string astr) {
//利用位图思想来解决问题
if(astr.size() > 26)
{
return false;
}
int bitmap = 0;
for(char c : astr)
{
int n = c - 'a';
//判断字符是否已经出现过
if(bitmap & (1 << n))
{
return false;
}
else
{
bitmap |= (1 << n);
}
}
return true;
}
};
//利用异或的规则:将0~n的数字和 nums中的数字都异或一次结果即为没有出现的那个数,其他数都出现了两次
class Solution {
public:
int missingNumber(vector<int>& nums) {
unsigned int xor_all = 0;
int n = nums.size();
for(int i = 0; i <= n; i++)
{
xor_all ^= i;
}
for(int x : nums)
{
xor_all ^= x;
}
return xor_all;
}
};
//思路:先使用无进位相加,计算进位,无进位相加直到进位为0
class Solution {
public:
int getSum(int a, int b) {
while(b != 0)
{
int x = a ^ b;//计算无进位相加
int carry = ( a & b) << 1; ;//计算进位
a = x;
b = carry;
}
return a;
}
};
//思路:统计每个数字第i位的和sum, sum %= 3 即可判断只出现一次的数字第i位
//3n 0 + 0 = 0 %=3 == 0
//3n 0 + 1 = 1 %=3 == 1
//3n 1 + 1 = 3n + 1 %3 == 1
//3n 1 + 0 = 3n %=3 == 1 -->此方法可推广到n,即除某个元素只出现一次外,其他元素都出现了n次,%=n 即可判断只出现一次的数字的第i位
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for(int i = 0; i < 32; i++)
{
int sum = 0;
for(int x : nums)
{
if(x & (1 << i))
{
++sum;
}
}
sum %= 3;
if(sum == 1)
{
ans |= (1 << i);
}
}
return ans;
}
};
//思路:将所有数字全部异或,转换为题目只出现了一次的数字3
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
unsigned int xor_all = 0;
int n = nums.size();
for(int x : nums)
{
xor_all ^= x;
}
for(int i = 1; i <= n+2; i++)
{
xor_all ^= i;
}
//计算最低位为1的位
int lowbit = xor_all & (-xor_all);
vector<int> ans(2);
for(int x : nums)
{
if((lowbit & x) == 0)
{
ans[0] ^= x;
}
else
{
ans[1] ^= x;
}
}
for(int i = 1; i <= n+2; i++)
{
if((lowbit & i) == 0)
{
ans[0] ^= i;
}
else
{
ans[1] ^= i;
}
}
return ans;
}
};
结束!