算法中的与、异或运算

2023-01-06 177

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 算法中的与、异或运算

与运算

认识&

& 按位与操作，按二进制位进行"与"运算。运算规则：（有 0 则为 0）

0 & 0 = 0;
0 & 1 = 0;
1 & 0 = 0;
1 & 1 = 1;

-x的含义与 x & (-x)

-x 的值，其实就是在x的值的基础上进行按位取反(~x)之后在增加1所得，即x & -x == x & (~x + 1)

x为偶数

x = 0000 0100 1110   // 假设x为偶数，比如0000 0100 1110
～x = 1111 1011 0001 // 取反后就是1111 1011 0001   
～x+1 = 1111 1011 0001 + 1 = 1111 1011 0010   // 再加1就等于1111 1011 0010
x & (~x + 1) = 0000 0000 0010        //x & (-x)的结果就是0000 0000 0010
复制代码

x为奇数

x = 0000 0100 1111    // 假设x为奇数，比如 0000 0100 1111
～x = 1111 1011 0000  // 取反后为1111 1011 0000
～x+1 = 1111 1011 0001 //由于～x的值一定是偶数，因此加1时必不会产生进位
x & (~x + 1) = 0000 0000 0001  // x & (~x + 1)结果就是 0000 0000 0001，最后一位必定为1，其他位必定为0
复制代码

结论：

x为偶数，x & (-x)的二进制表达式只会有一位保留为1

x为奇数，x & (-x)的二进制表达式最后一位必定为1，其它为0

x为0时，x & (-x)的二进制表达式为0x & (-x) 一般是用来获取某个二进制数的最低位的1所对应的值

异或运算

运算符号为：⊕（代码中就是^）。

如果a、b两个值不相同，则异或结果为1；如果值相同，则为0 用1表示真，0表示假，则异或运算法则为：0⊕0=0，0⊕1=1，1⊕0=1，1⊕1=0。

异或运算也被常称为不进位加法： 10110⊕00111=10001

性质

满足交换律、结合律
0⊕a=a、a⊕a=0 (注意1⊕a!=a)

异或运算在计算机中的应用

举个🌰——交换值：

int a = 甲
int b = 乙
a=a⊕b;   //a=甲⊕乙，b=乙
b=a⊕b;   //a=甲⊕乙，b=甲⊕乙⊕乙=甲⊕0=甲
a=a⊕b;   //a=甲⊕乙⊕甲=0⊕乙=乙，b=甲
复制代码

注意：能用这个方式的前提是，a与b所指向的是不同的内存。

LeetCode中奇妙的异或运算

LeetCode-136. 只出现一次的数字

var singleNumber = function(nums) {
    let xor = 0;
    for(let i =0;i<nums.length;i++){
        console.log(i)
        xor^=nums[i]
    }
    console.log(1^87, 0^87)
    return xor
};
复制代码

题目变形

给定一个非空整数数组，除了某个元素只出现奇数次以外，其余每个元素均出现偶数次。找出那个只出现了奇数次的元素。要求时间复杂度为O(N)O(N)O(N)，空间复杂度为O(1)O(1)O(1)

思路：0逐个对数组中的元素进行异或，最后剩下的数就是只出现奇数次的元素（由于出现偶数次的数异或后就是0）

LeetCode-260. 只出现一次的数字 III

var singleNumber = function(nums) {
    let eor = 0;
    for(let i=0;i<nums.length;i++){
        eor^=nums[i]
    }
    let rightOne = eor & -eor;
    let type1 = 0;
    let type2 = 0;
    for(const num of nums){
        if(num & rightOne){
            type1 ^= num
        }else{
            type2 ^= num
        }
    }
   return([type1, type2])
};
复制代码

题目变形

给定一个非空整数数组，有两个元素出现奇数次，其余每个元素均出现偶数次。找出只出现了奇数次的元素。要求时间复杂度为O(N)O(N)O(N)，空间复杂度为O(1)O(1)O(1)

思路：假设出现奇数次的两个元素是x和y，那么0逐个对数组中的元素进行异或的结果为eor（eor=x^y，且eor不为0，eor必然有一个位置上为1，假设这个位置为k，那么在k位，x和y不相同）；找到eor中为1的某一位，假设为第k位，按k是否为1将所有元素分为两组，这样的话，x和y分别位于不同组中；不同组中对子元素进行异或，最后结果分别就是x和y

难点：如何找到eor中最右为1的位置