1009. Complement of Base 10 Integer

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer n, return its complement.

Example 1:

Input: n = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Constraints:

• 0 <= n < 109

注意： 题目中的设定的补码和计算机科学中的补码不是一个概念。

这是一道Easy难度的问题，一个通常的解是非常容易写出来的：我们大可以把入参转换成二进制，然后每一位取补码顺便转换回十进制。有一个坑是 n=0 时需自行判断。

var bitwiseComplement = function(n) {
    if (n === 0) return 1
    let rst = count = 0
    
    while(Math.floor(n / 2)) {
        const b = 1 - n % 2
        if (b === 1) { rst += Math.pow(2, count) }
        n = Math.floor(n / 2)
        count++
    }
    
    return rst
};

但是这个题目显然更想考验一下位运算。搜索资料后，得出下解：以101为例，我们可以将它与111与或，即得到补码。

var bitwiseComplement = function(n) {
    if (n === 0) return 1

    let a = 1
    
    while (a <= n) {
        a = a << 1
    }
    
    return (a - 1) ^ n
};

位运算理论上是很快的，但是得出的 Runtime 却是最慢的那一批……有些不解。

---

本日遇到另一个位运算技巧，在这里记录(1022)：

If you work with decimal representation, the conversion of 1->2 into 12 is easy. You start from curr_number = 1, then shift one register to the left and add the next digit: curr_number = 1 * 10 + 2 = 12.

If you work with binaries 1 -> 1 -> 3, it's the same. You start from curr_number = 1, then shift one register to the left and add the next digit: curr_number = (1 << 1) | 1 = 3.

---

421. Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

• 1 <= nums.length <= 2 * 105
• 0 <= nums[i] <= 231 - 1

对我来说这是一道很难的问题，也是目前位置我遇到的最难的 Medium 问题。解完之后明显感到我对位运算的熟练度提高了……

暴力解法是很容易想到的：简单地让数组里的值两两与或，记住出现过的最大值即可。理所当然地，这会造成超时。

这一题的通用解法有两个，都不容易想到。我们一个个看。

解法一：与或的性质

与或有一个神奇的性质：

如果我们有a ^ b = c ，可得a ^ c = b。# 交换律

这一解法基于该性质。

基本思路是：我们将32位从最高位到最低位遍历，如果两个数某一位的bit值不相等，则该位XOR结果为1。那么，这两个数XOR的值必然比这XOR结果为0的两个数大。由于我们是从高位到低位遍历，先遍历的权重更大。所以我们可以一位一位地计算出最大值。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function(nums) {
    // rst 是最终返回的结果，也就是最大值。它是从高位到低位算出来的。
    // mask 是掩码
    let rst = 0, mask = 0
    // 32位，从高位到地位依次判断
    for (let i=31; i>=0; i--) {
        const cache = new Set()
        // 掩码会把数组里，比i低的位抹成0，这意味着我们不关心比i低的位
        // 注意我们是怎么算出掩码的：假设i=3, 我们有 mask = ...1110000, 新的掩码为：
        // ...1110000 | ...0001000 = ...1111000
        mask = mask | 1 << i
        // 将 rst 上的第 i+1 位变成1，赋值给 wish
        const wish = rst | 1 << i

        nums.forEach(n => {
          	// 把数组里的每一个数的i之后的位抹成0，缓存。
            cache.add(n & mask)
        })
        
        for (c of cache.values()) {
          	// 这是最难懂的部分。根据定理，如果我们有 c^wish = x，那么一定有 c^x=wish
            // 也就是说存在两个数XOR可以使得i以上的位和wish相同
            // 有人可能会想：如何保证这两个数和上一轮的两个数相同呢？
            // 答案是不用保证，由于抹掉的是i以及i以下的位，所以只看i以上的位的话，rst就是最大值
            // 当遍历完成，i===0，自然就是问题的解。
            // 一开始可能会有好几组数可以 XOR 成rst
            // 但是到最后一定只有一个
            if (cache.has(c ^ wish)) {
                rst = wish
                break
            }
        }
    }
    return rst
};

解法二：树

即使我们知道解法1中XOR的性质，得出1的解法依然是非常困难的。那么比较通常的做法是什么呢？

我们可以用一颗字典树来表示所有的32位二进制数。这颗树的高度就是位树，如果这一位有两个值就代表这两个数XOR在这一位上为1. 有了这颗树之后，计算XOR值只需要O(32)。

于是，我们可以快速计算出每个值最大的XOR值，然后返回其中的最大值。这需要 O(32n)。我们发现生成树需要同样的复杂度，于是省略赋值等步骤后（考虑到常数项很小，其实不能省略），大约为O(2*32n).

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function(nums) {
    let Trie = new Node(), rst = 0
    
    function Node() {
        this.val = new Map()
    }
    // 生成树
    nums.forEach(n => {
        let crt = Trie
        for (let i=31; i>=0; i--) {
            // current bit
            const cb = n >> i & 1
            if (!crt.val.has(cb))
                crt.val.set(cb, new Node())
            
            crt = crt.val.get(cb)
        }
    })
    
    nums.forEach(n => {
        let crtMax = 0, crtNode = Trie
        for(let i=31; i>=0; i--) {
            const crtBit = n >> i & 1
            
            if (crtNode.val.has(1 - crtBit)) {
                crtMax = crtMax << 1 | 1
                // 如果该位XOR结果为1，那么进对应的子树。到最后，树对应的数字就是和当前遍历项XOR结果最大的数
                crtNode = crtNode.val.get(1 - crtBit)
            } else {
                crtMax = crtMax << 1 | 0
                crtNode = crtNode.val.get(crtBit)
            }
        }
        rst = Math.max(rst, crtMax)
    })

    return rst
};

---

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

这一题有一个非常规解法，用到XOR的交换律，以及另一个性质

a XOR a = 0

// XOR is commutative, means- 1^2^1 = 1^1^2 (since a^a =0 hence 2 will be left)
var singleNumber = function(nums) {
    let res = nums[0];
    for(let i = 1; i < nums.length; i++){
        res = res ^ nums[i]
    }
    return res;
};