剑指Offer JavaScript-位运算专题

二进制中1的个数

1. 题目

2. 思路

3. 代码实现

/**
 * @param {Number} n
 */
function numberOf1(n) {
    let count = 0,
        flag = 1;

    while (flag) {
        if (flag & n) {
            ++count;
        }

        flag = flag << 1;
    }

    return count;
}

/**
 * 测试代码
 */

console.log(numberOf1(3));

二进制中1的个数进阶版

1. 优化做法

/**
 * @param {Number} n
 */
function numberOf1(n) {
    let count = 0;

    while (n) {
        ++count;
        n = n & (n - 1);
    }

    return count;
}

/**
 * 测试代码
 */

console.log(numberOf1(3));

2. 如何判断 2 的整次方

/**
 * 判断是否是2的整次方
 * @param {Number} n
 */
function is2Power(n) {
    if (n <= 0) {
        throw new Error("Unvalid param");
    }

    return !(n & (n - 1));
}

console.log(is2Power(128));

3. 求多少个不同的二进制位

1. m 和 n 进行异或操作，不同的位都变成了 1

2. 利用前面的思路统计 1 的个数

/**
 * 求解二进制表示中有多少位不相同
 * @param {Number} a
 * @param {Number} b
 */
function getDiffBytes(a, b) {
    let count = 0,
        n = a ^ b;

    while (n) {
        ++count;
        n = n & (n - 1);
    }

    return count;
}

/**
 * 测试代码
 */

console.log(getDiffBytes(1, 1));
console.log(getDiffBytes(3, 1));

数组中只出现一次的数字

1. 题目描述

2. 思路分析

1. 全部异或，最终结果是 2 个数字异或结果

2. 找到结果中第一个 1 出现的位数

3. 按照此位是不是 1，将原数据分成 2 组

4. 组内分别异或

3. 代码实现

/**
 * 找到num二进制表示中第一个1的位
 *
 * @param {Number} num
 */
function findFirstBitIsOne(num) {
    let indexBit = 0,
        flag = 1;
    while (flag && (flag & num) === 0) {
        ++indexBit;
        flag = flag << 1;
    }
    return indexBit;
}

/**
 * 判断num的第index二进制位是否为1
 *
 * @param {Number} num
 * @param {Number} index
 */
function checkIndexBitIsOne(num, index) {
    num = num >> index;
    return !!(num & 1);
}

/**
 * 主函数
 *
 * @param {Array} nums
 */
function findNumsAppearOnce(nums) {
    if (!nums) {
        return null;
    }

    let orResult = 0;
    for (let num of nums) {
        orResult ^= num;
    }

    let indexOfOne = findFirstBitIsOne(orResult);
    let num1 = 0,
        num2 = 0;
    for (let num of nums) {
        if (checkIndexBitIsOne(num, indexOfOne)) {
            num1 ^= num;
        } else {
            num2 ^= num;
        }
    }

    return [num1, num2];
}

/**
 * 测试
 */

console.log(findNumsAppearOnce([2, 4, 3, 6, 3, 2, 5, 5]));

4. 拓展阅读

$ 1 << 32 # 1

$ 1 << 31 # -2147483648
$ -2147483648 << 1 # 0