《算法零基础100讲》(第46讲) 位运算 (异或) 入门

本文主要是介绍《算法零基础100讲》(第46讲) 位运算 (异或) 入门，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• • 写在前面
  • • 异或
    • 简单应用
  • 课后习题
  • • 136. 只出现一次的数字
    • 190. 颠倒二进制位
    • 461. 汉明距离

写在前面

异或

先来一个异或的真值表

从上面这张表，我们其实可以挖掘出不少性质。

1. 相同两个数的异或值一定是0
2. 任何数和0异或值一定是0
3. 异或值可以用来找两个数字的二进制位中不相同的位

简单应用

异或最经典的应用就是用于交换两个变量的值。其实也是利用了相同两个数异或和等于0的性质。代码如下：

a=a^b;
b=a^b;
a=a^b;

课后习题

136. 只出现一次的数字

直接利用两个数异或和为0的性质

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int sum=0;
        for(auto t:nums) sum^=t;
        return sum;
    }
};

190. 颠倒二进制位

一个数从后往前看二进制位是多少，一个数一直往前推一位并把这一位加上

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

461. 汉明距离

两个数异或和中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;
    }
};

这篇关于《算法零基础100讲》(第46讲) 位运算 (异或) 入门的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！