关于运算符^问题

Question

题目描述

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

相关代码

var missingNumber = function(nums) {
    var res = nums.length;
    
    for(var i = 0; i < nums.length; i++){
        res = res^(i ^ nums[i]);
    }
    
    return res;
};

看到一位大神的答案，但是不太理解 res = res^(i ^ nums[i]);的意思，查了^的解释，调试了程序，还是不太明白是怎么对比出来的，麻烦解答一下，谢谢

Answer 1

Bitwise_Operators#(按位异或)

var missingNumber = function(nums) {
    var res = nums.length;
    
    for(var i = 0; i < nums.length; i++){
        res = res^(i ^ nums[i]);
    }
    
    return res;
};

首先异或不需要管顺序。
假设数组为连续[1,2...,n]数组，则nums.length必然与数组当中的某个值相等，即n^nums.length为0，因为x^0为x，所以若数据连续，则必然有n-1与上诉过程相同逻辑。

反正就是消消乐的意思，假设nums为[1,2,3]则最后的结果为length异或每个值异或下标，也就是3^1^2^3^0^1^2。

PS:个人不建议使用这样的代码

Answer 2

主要是两个性质：

1. 异或满足交换律；
2. 两个 bits 异或，若相同则为 0；若相异则为 1。

简化下问题，比如给定数组[0, 1, 2, 3, 5]，它是少一个 4 的，现在我们要把 4 找出来。

(0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5) ^ (0 ^ 1 ^ 2 ^ 3 ^ 5) =
(0 ^ 0) ^ (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (5 ^ 5) ^ 4 =
0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 4 =
4

就像上面一位朋友说的，消消乐，这个说法形象。

单单针对这道题（老题目了）来说，这个解法应该是最佳的。

在实际项目中，位运算不是不能用，反而是建议你多用，但前提是你，会用，用对，且必须要有注释，没有这三个，还是老实本分点比较好。

基本的位运算，参考https://subetter.com/articles...。

牛逼一点的，参考书籍《算法心得 高效算法的奥秘》，此书已快绝版，且异常烧脑。