Skip to content

Latest commit

 

History

History
159 lines (131 loc) · 3.85 KB

二进制.md

File metadata and controls

159 lines (131 loc) · 3.85 KB

二进制

JS二进制基础知识： 二进制

136.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

输入: [2,2,1] 输出: 1

4 ^ 1 ^ 2 ^ 1 ^ 2 = 4

思路：a === a ^ b ^ b

var singleNumber = function(nums) {
    let res = 0;
    for(let num of nums){
        res ^= num;
    }
    return res;
};
137.只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

输入: [2,2,3,2] 输出: 3

var singleNumber = function(nums) {
    let seenOnce = 0, seenTwice = 0;
    for(let num of nums){
        seenOnce = ~seenTwice & (seenOnce ^ num);
        seenTwice = ~seenOnce & (seenTwice ^ num);
    }
    return seenOnce;
};
260. 只出现一次的数字 III
/* 
* 执行用时：560 ms, 在所有 JavaScript 提交中击败了8.67%的用户 😂，indexof这么耗时
* 内存消耗：38.4 MB, 在所有 JavaScript 提交中击败了91.67%的用户
*/
var singleNumber = function (nums) {
    const res = []
    nums.forEach(num => {
        if (nums.indexOf(num) === nums.lastIndexOf(num)) {
            res.push(num)
        }
    })
    return res
};
var singleNumber = function (nums) {
    let ret = 0;
    for (let n of nums) {
        ret ^= n;
    }
    let div = 1;
    while ((div & ret) === 0) {
        div <<= 1;
    }
    let a = 0, b = 0;
    for (let n of nums) {
        if ((div & n) !== 0) {
            a ^= n;
        } else {
            b ^= n;
        }
    }
    return [a, b];
}
191. 位1的个数
var hammingWeight = function(n) {
    let res = 0
    while(n){
        n = n & (n-1)
        res++
    }
    return res
};
338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

var countBits = function (num) {
    const res = []
    for (let i = 0; i <= num; i++) {
        let n = i
        let times = 0
        while (n) {
            n = n & (n - 1)
            times++
        }
        res.push(times)
    }
    return res
};
190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

var reverseBits = function (n) {
    let rev = 0;
    for (let i = 0; i < 32 && n > 0; ++i) {
        rev |= (n & 1) << (31 - i);
        n >>>= 1;
    }
    return rev >>> 0;
};
201. 数字范围按位与

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

var rangeBitwiseAnd = function (left, right) {
    let count = 0
    while (left !== right) {
        left >>= 1
        right >>= 1
        count++
    }
    return left << count
};

总结

玄

练习