[算法]位运算

AND

231. 2 的幂

n > 0 && (n & (n - 1)) == 0;

342. 4的幂

(4).toString(2)
  "100"
 &1010
  ----
     0
(16).toString(2)
  "10000"
 &101010
  ------
       0
(4 ** 3).toString(2)
  "1000000"
 &10101010
  --------
         0
(4 ** 4).toString(2)
  "100000000"
 &1010101010
  ----------
           0

唯一的 1 出现在第 4 个二进制位上，因此 n 是 4 的幂。
偶数二进制位都是 0，所有奇数二进制位都是 1
mask=(10101010101010101010101010101010)2
表示成 16 进制的形式mask=(AAAAAAAA)16

n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;

OR

XOR

相同为0， 不同为1

面试题 16.01. 交换数字

function swapNumbers(numbers: number[]): number[] {
    numbers[0] ^= numbers[1];
    numbers[1] ^= numbers[0];
    numbers[0] ^= numbers[1];
    return numbers;
};

136. 只出现一次的数字

某个元素只出现一次以外，其余每个元素均出现两次
case 1: [2,2,1] => 1
res cur res ^ cur
0 2 2
2 2 0
0 1 1
case 2: [4,1,2,1,2] => 4
res cur res ^ cur
0 4 4
4 1 5
5 2 7
7 1 6
6 2 4

var singleNumber = function(nums) {
    let res = 0;
    for (let i of nums) {
        res ^= i;
    }
    return res;
};

面试题 17.04. 消失的数字

case 1： [3,0,1] => 2
case 2: [9,6,4,2,3,5,7,0,1] => 8

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

137. 只出现一次的数字 II

某个元素只出现一次以外，其余每个元素均出现三次

var singleNumber = function(nums) {
    let res1 = 0;
    let res2 = 0;
    for (let i of nums) {
        res1 = ~res2 & (res1 ^ i);
        res2 = ~res1 & (res2 ^ i);
    }
    return res1;
};

剑指 Offer 56 - I. 数组中数字出现的次数（260. 只出现一次的数字 III）

除两个数字之外，其他数字都出现了两次
关键： 分组
case 1: [1,2,1,3,2,5] => [3,5]
x ^ y 分组界限
6 2
[ 2, 3, 2 ] [ 1, 1, 5 ]

case 2： [1,2,10,4,1,4,3,3] => [10,2]
x ^ y 分组界限
8 8
[ 10 ] [1, 2, 4, 1, 4, 3, 3]

var singleNumber = function(nums) {
    let xor = 0;
    for(let num of nums) {
        xor ^= num;
    }
    let divide = 1;
    while((divide & xor) == 0) {
        divide <<= 1;
    }
    let res1 = 0, res2 = 0;
    for (let num of nums) {
        if (divide & num) {
            res1 ^= num;
        } else {
            res2 ^= num;
        }
    }
    return [res1, res2];
};

剑指 Offer 56 - II. 数组中数字出现的次数 II

除一个数字只出现一次之外，其他数字都出现了三次
🔑 统计所有数字的各二进制位中11的出现次数，并对3求余

var singleNumber = function(nums) {
    let bits = new Array(32).fill(0);
    for (let num of nums) {
        for (let i=0; i<32; i++) {
            bits[i] += num & 1;
            num >>= 1;
        }
    }
    let res = 0;
    for (let i=31; i>=0; i--) {
        res <<= 1;
        res += bits[i] % 3;
    }
    return res;
};

645. 错误的集合

集合 s 包含从 1 到 n 的整数 , 集合 丢失了一个数字 并且 有一个数字重复
case 1: [1,2,2,4] => [2,3]
case 2: [1,1] => [1,2]
意图：

1. [1,2,2,4] 合并 [1,2,3,4] ， 全部异或后剩余 x ^ y = [2, 3]
2. 分组方式， 分离出2， 3
3. 确定重复元素和缺少元素

   var findErrorNums = function(nums) {
    let xor = 0;
    for (let num of nums) {
        xor ^= num;
    }
    for (let i=1; i<=nums.length; i++) {
        xor ^= i;
    }
    let divide = 1;
    while ((xor & divide) == 0) {
        divide <<= 1;
    }
    let res1 = 0, res2 = 0;
    for (let num of nums) {
        if (divide & num) {
            res1 ^= num;
        } else {
            res2 ^= num;
        }
    }
    for (let i=1; i<=nums.length; i++) {
        if (divide & i) {
            res1 ^= i;
        } else {
            res2 ^= i;
        }
    }
    return nums.includes(res1) ? [res1, res2] : [res2, res1];
   };2
   

   NOT

~是二进制的按位取反，
~~可以理解为是取整的简写

case 1: [2,2,3,2] => 3
res1 res2 cur
0 0
2 0 2
0 2 2
1 0 3
3 0 2

case 2: [0,1,0,1,0,1,99] => 9

0 0 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
99 0 99

移位

左移位

0b0<<1
0

0b1<<1
2  // 1  ->  10

剑指 Offer 65. 不用加减乘除做加法

var add = function(a, b) {
    let c;
    while (b != 0) {
        c = (a & b) << 1;
        a ^= b;
        b = c;
    }
    return a;
};

面试题 01.01. 判定字符是否唯一

分析： 用长度为26的数组标记a-z
再分析： 为节约内存，采用长度为26的二进制标记a-z
左移运算符 1 << move_bit 则可以得到对应下标为1
（1向左移n位，例如3， 得到100， 即三位数二进制数， 最高位为1）

[0, 1, 2, 3, 4, 5].forEach((d) => {
  console.log(d.toString(2), (1 << d).toString(2));
});

  0      1
  1     10
 10    100
 11   1000
100  10000
101 100000

solution

var isUnique = function(astr) {
    let mark = 0;
    const base = 'a'.charCodeAt();
    for (let char of astr) {
        let moveBit = char.charCodeAt() - base;
        if (mark & (1 << moveBit)) return false;
        mark |= (1 << moveBit);
    }
    return true;
};

右移位

0b1>>1
0

复合运算

采用二进制进行标记

(1 << 0).toString(2) // 标记倒数第0位， 索引从0开始
'1'

(1 << 1).toString(2) // 标记倒数第1位
'10'

(1 << 1).toString(2) // 标记倒数第2位
'10'

(1 << 2).toString(2) // 标记倒数第3位
'100'

(1 << 3).toString(2) // 标记倒数第4位
'1000'

1763. 最长的美好子字符串

395. 至少有 K 个重复字符的最长子串