先来一个异或的真值表
x | y | x^y |
---|---|---|
0 | 0 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 0 |
从上面这张表,我们其实可以挖掘出不少性质。
- 相同两个数的异或值一定是0
- 任何数和0异或值一定是0
- 异或值可以用来找两个数字的二进制位中不相同的位
异或最经典的应用就是用于交换两个变量的值。其实也是利用了相同两个数异或和等于0的性质。代码如下:
a=a^b; b=a^b; a=a^b;
直接利用两个数异或和为0的性质
class Solution { public: int singleNumber(vector<int>& nums) { int sum=0; for(auto t:nums) sum^=t; return sum; } };
一个数从后往前看二进制位是多少,一个数一直往前推一位并把这一位加上
class Solution { public: uint32_t reverseBits(uint32_t n) { uint32_t ans=0; for(int i=0;i<32;i++) { ans=(ans<<1)|(n&1); n>>=1; } return ans; } };
两个数异或和中1的个数即二进制位中不同的数目
class Solution { public: int lowbit(int x) { return x&-x; } int hammingDistance(int x, int y) { int t=x^y,cnt=0; while(t) { t^=lowbit(t); cnt++; } return cnt; } };