异或^相关技巧以及经典题目
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
本文对异或(^)操作常见的一些技巧进行了介绍和解释, 对异或常用的一些面试题进行了讲解
异或
^
异或的规则:
二进制位相同为0 不同为1
我们来举个例子
大家也可以试着举个例子自己算一下
可以用另一种方式来理解异或运算符,就是**无进位相加**
不同的位结果为1 , 就是 0 1 = 1, 如果是1 1 就是 0 ,无进位相加,还是比较好理解的
异或的相关规律
这里的n, m, j代表任意整数
- n ^ 0 = n
- n ^ n = 0
- (n ^ m) ^ j = n ^ ( m ^ j)
n ^ 0 =n,这个很好解释,0的二进制位都是0, 所以和n异或,无进位相加, 还是n本身
n ^ n = 0, 这个也好解释, 每个二进制位都相同, 所以异或的结果就是0
异或运算满足交换律和结合律这也是很好理解的, 可以举个例子来试一下
异或常见的题
1.如何不适用额外变量交换两个数
大家经常会碰到交换两个数的场景, 比如冒泡排序…
我们一般都是借助一个临时变量进行交换,典型的三杯水法
那如何不使用额外变量交换两个数呢?
有朋友会说,通过加法, 我们来试试
那使用异或该怎么做呢?
这样使用异或也会存在其他的问题,比如如果要交换的两个值是相同的,那么异或就会把值刷成0
大家酌情使用,使用的时候千万要注意
只出现一次的数字
找出出现一次的数, 时间复杂度O(N),空间复杂度O(1)
如果不会使用异或,我能想到的方法一个是排序, 另一个是哈希.但是都不达标
那如何使用异或来做呢,其实非常简单
数组中数字出现的次数
看到这个题不知道大家有啥想法,和上一道题很像,只不过从一个数变成了两个数,那么该怎么做呢?
当然使用排序和哈希表还是可以做的,我们来看看异或怎么做
前两题变形题
一个数组中有一个数出现K次,其他数都出现了M次,M>1,K < M, 求找到出现K次的数字
要求:额外空间复杂度O(1),时间复杂度O(N)
这道题一看就头大了,这该怎么解呢?
大家肯定再想异或怎么解,其实这道题和异或没啥关系, 只不过和前几道题很像,所以放在这里了
我们来分析一下
//保证有一个数出现K次,其他数都出现了M次,M>1,K < M
int KTimesNumber(vector<int>& nums, int k, int m)
{
vector<int> counts;
counts.resize(32, 0);
//填充counts数组
for (auto& e : nums)
{
for (int i = 0; i < 32; ++i)
{
counts[i] += (1 << i) & e;
}
}
int ans = 0;
//拆分
for (int i = 0; i < 32; ++i)
{
//如果e % m != 0 说明我们要找的那个数这个位为1
if (counts[i] % m)
{
ans |= (1 << i);
}
}
return ans;
}
我们来测试一下
这样测试是不准的,我们要用对数器来测试
使用对数器测试结果
//保证有一个数出现K次,其他数都出现了M次,M>1,K < M
int KTimesNumber(vector<int>& nums, int k, int m)
{
vector<int> counts;
counts.resize(32, 0);
//填充counts数组
for (auto& e : nums)
{
for (int i = 0; i < 32; ++i)
{
counts[i] += (1 & (e >> i));
}
}
int ans = 0;
//拆分
for (int i = 0; i < 32; ++i)
{
//如果e % m != 0 说明我们要找的那个数这个位为1
if (counts[i] % m)
{
ans |= (1 << i);
}
}
return ans;
}
//使用map来统计词频-->作为暴力方法
int test(vector<int>& nums, int k, int m)
{
map<int, int> countMap;
for (auto& e : nums)
{
countMap[e]++;
}
for (auto& e : countMap)
{
if (e.second == k)
return e.first;
}
return INT_MIN;
}
//得到一个随机的vector
vector<int>& getRandomVector(int k, int m)
{
vector<int>* v = new vector<int>;
//有childKinds种数
int childKinds = rand() % 10 + 2;
v->resize((childKinds - 1) * m + k);
set<int> s;
//先设置出现k次
int i = 0;
int kKindsNum = rand() % 100 - rand() % 100;
s.insert(kKindsNum);
while (k--)
{
v->operator[](i++) = kKindsNum;
}
//种类--
childKinds--;
while (childKinds)
{
//生成随机数
int tmp = 0;
do
{
tmp = rand() % 100 - rand() % 100;
} while (s.find(tmp) != s.end());
s.insert(tmp);
//设置m次
for (int j = 0; j < m; ++j)
{
v->operator[](i++) = tmp;
}
childKinds--;
}
//把vector中数据打乱次序
for (i = 0; i < v->size(); ++i)
{
int j = rand() % v->size();
swap(v->operator[](i), v->operator[](j));
}
return *v;
}
int main()
{
srand(time(nullptr));
//次数
int times = 20;
int cou = 0;
//数组最大长度
cout << "测试开始" << endl;
for (int i = 0; i < times; i++)
{
int k = rand() % 5 + 1;
int m = rand() % 5 + 2;
//要保证k < m
if (k >= m)
{
k = m - 1;
}
vector<int>& v = getRandomVector(k , m);
如果测试结果不同
if (test(v, k, m) != KTimesNumber(v, k, m))
{
cout << "error" << endl;
for (auto& e : v)
{
cout << e << ",";
}
cout << endl;
delete &v;
break;
}
cou++;
delete &v;
}
cout << "测试结束" << endl;
return 0;
}
大家可以自己测试一下
总结
异或运算的奥妙非常多,大家可以在日常中经常练习,有什么疑问可以一起交流,