位操作基础

发表于 | 分类于

位操作基础

异或操作基础

  • 如果我们对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位
    a ⊕ 0 = a

  • 如果我们对相同的二进制位做 XOR 运算，返回的结果是 0
    a ⊕ a = 0

  • XOR 满足交换律和结合律
    a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

异或运算符优先级

  • 位操作符是低于比较运算符(===)的，因此(a &b ) === c

二进制转10进制

1
2
3
4
5
6
7
8
9
10
11
12
let str = '01010'
let mask = 1;
let i = 0;
let num = 0;
while(i<str.length){
    let cur = str.charAt(i);
    if(cur === '1'){
        num = num + mask;
    }
    mask<<=1;
    i++;
}

左移

1
2
3
let h = 1; //000001->1
h<<=1;     //000010->2
h<<=1;     //000100->4

测试number二进制中某位是否是1

number与1(1),2(2),8(3),16(4),32(5)按位与，为0则该位是0，否则是1

两个number某个二进位是否相等

直接与001,010,100,1000,10000…进行按位与操作即可，因为其它位全是0，只看1所在位

  • 以比较第1位为例
    2和5的二进制第1位是相同的，2和4的第一位不相同
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    1(001)
    2 & 1 = 1
    010->2
    001->1


    5 & 1 = 1
    101->5
    001->1

    4 & 1 = 0
    100->4
    001->1

找到Number二进制不为0的最低位

结果是100

1
2
3
4
5
6
7
var num = 6; //110
var x = 1;//001
//  100才符合
while((x & num) === 0){
    //左移，001->010->100->1000...
    x<<=1;
}

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
解: 参考上边的交换律，所以我们只需要将所有的数进行 XOR 操作，得到那个唯一的数字。

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let a = 0;
    for(let i = 0; i<nums.length;i++){
        a = a^nums[i];
    }
    return a;
};

不用加减乘除做加法

数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @return {number[]}
 * 目标是找到a,b
 */
var singleNumbers = function(nums) {
    let x;
    for(let i=0;i<nums.length;i++){
        x^=nums[i];
    }
    //找到 x = a ^ b
    let div = 1; //001
    while((x & div) === 0){//直到找到不是0的位
        div<<=1; //左移1位 001->010->100
    }

    let a = 0, b = 0;
    for(let i=0;i<nums.length;i++){
        //说明位不同，每个数和div 按位与，等于0表示
        if((nums[i] & div) === 0){
            a ^= nums[i];
        } else {
            b ^= nums[i];
        }
    }
    return [a,b];

};