案例

二进制求和（简单）

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"
输出："100"

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

提示：

• 1 <= a.length, b.length <= 104
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

解题思路

整体思路是将两个字符串较短的用 0 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。

本题解中大致思路与上述一致，但由于字符串操作原因，不确定最后的结果是否会多出一位进位，所以会有 2 种处理方式：

• 第一种，在进行计算时直接拼接字符串，会得到一个反向字符，需要最后再进行翻转
• 第二种，按照位置给结果字符赋值，最后如果有进位，则在前方进行字符串拼接添加进位

时间复杂度：O(n)

位运算

var addBinary = function(a, b) {
    let ans = "";  // 存储最终结果的字符串
    let ca = 0;    // 进位标志，初始为0

    // 从两个二进制数的最低位开始，逐位相加
    for(let i = a.length - 1, j = b.length - 1; i >= 0 || j >= 0; i--, j--) {
        let sum = ca;  // 当前位的和，初始为进位值

        // 将当前位的二进制数转换为十进制数，并加到sum上
        // 如果已经超出了某个数的长度，则视为0
        sum += i >= 0 ? parseInt(a[i]) : 0;
        sum += j >= 0 ? parseInt(b[j]) : 0;

        // 将sum的个位数添加到结果中，作为当前位的和
        ans += sum % 2;

        // 计算新的进位值
        ca = Math.floor(sum / 2);
    }

    // 如果最后还有进位，则将其添加到结果的开头
    ans += ca == 1 ? ca : "";

    // 由于是从低位到高位计算的，所以需要反转结果字符串
    return ans.split('').reverse().join('');
};

一行

var addBinary = function (a, b) {
    return ((BigInt('0b' + a) + BigInt('0b' + b)).toString(2))
};

颠倒二进制位（简）

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

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：

• 输入是一个长度为 32 的二进制字符串

进阶: 如果多次调用这个函数，你将如何优化你的算法？

解题思路

1. 初始化结果变量：let ret = 0;。ret用来存储反转后的结果。
2. 循环处理每一位：for (let i = 0; i < 32; i++) { ... }。这个循环会执行32次，每次处理一个二进制位。
3. 左移结果：ret <<= 1;。这行代码将ret左移一位，为即将添加的新位腾出空间。
4. 添加新位：ret += (n & 1);。这行代码将n的当前最低位（通过与1进行位与操作得到）加到ret的末尾。
5. 右移原数字：n >>= 1;。这行代码将n右移一位，以便在下一次循环中处理下一个位。
6. 返回结果：return ret >>> 0;。最后，返回反转后的结果，并确保它是一个无符号的32位整数。

// 定义一个函数reverseBits，接受一个参数n
function reverseBits(n) {
    // 初始化结果变量ret为0
    let ret = 0;
    
    // 循环32次，对应32位数字
    for (let i = 0; i < 32; i++) {
        // 将ret左移一位，为下一个位腾出空间
        ret <<= 1;
        
        // 将n的最低位加到ret上
        ret += (n & 1);
        
        // 将n右移一位，以便处理下一个位
        n >>= 1;
    }
    
    // 返回ret，并确保结果是一个无符号的32位整数
    return ret >>> 0;
}

位1的个数（简）

编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。

提示：

• 1 <= n <= 231 - 1

进阶：

• 如果多次调用这个函数，你将如何优化你的算法？

解题思路

逐位判断

根据 与运算 定义，设二进制数字 n ，则有：

• 若 n&1=0 ，则 n 二进制 最右一位 为 0 。
• 若 n&1=1 ，则 n 二进制 最右一位 为 1 。

根据以上特点，考虑以下循环判断 ：

1. 判断 n 最右一位是否为 1 ，根据结果计数。
2. 将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用无符号右移操作）。

算法流程：

1. 初始化数量统计变量 res=0 。
2. 循环逐位判断： 当 n=0 时跳出。
   1. res += n & 1 ： 若 n&1=1 ，则统计数 res 加一。
   2. n >>= 1 ： 将二进制数字 n 无符号右移一位（ Java 中无符号右移为 ">>>" ） 。
3. 返回统计数量 res 。

巧用 n&(n−1)

(n−1) 作用： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。

n&(n−1) 作用： 二进制数字 n 最右边的 1 变成 0 ，其余不变。

Picture1.png

1. 初始化数量统计变量 res 。
2. 循环消去最右边的 1 ：当 n=0 时跳出。
   1. res += 1 ： 统计变量加 1 。
   2. n &= n - 1 ： 消去数字 n 最右边的 1 。
3. 返回统计数量 res 。

逐位判断

var hammingWeight = function (n) {
    let res = 0;
    // 循环消去最右边的 1 ：当 n=0 时跳出。
    while (n) {
        res += (n & 1);
        // 将二进制数字 n 无符号右移一位，相当于除以2并取整
        n >>= 1;
    }
    return res
};

巧用 n&(n−1)

var hammingWeight = function (n) {
    let res = 0;
    // 循环消去最右边的 1 ：当 n=0 时跳出。
    while(n) {
        // 统计变量加 1 
        res += 1;
        // 消去数字 n 最右边的 1
        n &= n - 1
    }
    return res
};

只出现一次的数字（简）

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

解题思路

按位异或运算符 ^ 有一个重要的性质：对于任何数 x，有 x ^ x = 0 和 x ^ 0 = x。此外，按位异或运算满足交换律和结合律。

算法流程：

1. 初始化变量 i 为 0。由于任何数与 0 异或的结果都是它本身，所以这不会影响数组中其他元素的异或结果。
2. 遍历数组 nums 中的每个元素 j。
3. 在每次迭代中，将 i 与当前元素 j 进行按位异或运算，并将结果赋值给 i。
4. 由于数组中除了一个元素只出现一次外，其他元素都出现两次，所以成对的元素在异或运算后会相互抵消，最终 i 的值将是那个只出现一次的元素。

位运算

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

hash 表

var singleNumber = function (nums) {
    let map = new Map();
    for (let i of nums) {
        if (map.has(i)) {
            map.set(i, false);
        } else {
            map.set(i, true);
        }
    }
    for (let i of map) {
        if (i[1]) return i[0]
    }
};

只出现一次的数字 II（中）

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99 

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

解题思路

1. 初始化变量：创建两个变量 a 和 b，都初始化为0。这两个变量用于存储关于数组中数字位信息的状态。
2. 遍历数组：遍历数组中的每个数字。
3. 更新变量：对于每个数字 x，执行以下操作：
   • 更新 b：将 b 与 x 进行异或操作，然后与 a 的按位取反进行与操作。这一步是为了保留那些在 b 中只出现一次的位。
   • 更新 a：将 a 与 x 进行异或操作，然后与 b 的按位取反进行与操作。这一步是为了保留那些在 a 中只出现三次的位。
4. 返回结果：遍历完成后，返回变量 b 的值。由于 b 保留了那些只出现一次的位，所以它就是我们要找的那个只出现一次的数字。

这个算法的核心在于利用异或操作和位操作的特性来区分只出现一次的位和出现三次的位。通过这种方式，我们可以有效地找到那个只出现一次的数字。

var singleNumber = function (nums) {
    let a = 0, b = 0; // 初始化两个变量 a 和 b，用于存储位信息

    for (const x of nums) { // 遍历数组中的每个数字
        b = (b ^ x) & ~a; // b 更新为 b 和 x 的异或结果，并与 a 的按位取反进行与操作
        // 这一步是为了保留那些在 b 中只出现一次的位

        a = (a ^ x) & ~b; // a 更新为 a 和 x 的异或结果，并与 b 的按位取反进行与操作
        // 这一步是为了保留那些在 a 中只出现三次的位
    }

    return b; // 返回 b，它包含了那些只出现一次的位
    // 因为其他数字都出现了三次，它们的位在 b 中会被抵消
};

数字范围按位与(中)

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

示例 1：

输入：left = 5, right = 7
输出：4

示例 2：

输入：left = 0, right = 0
输出：0

示例 3：

输入：left = 1, right = 2147483647
输出：0 

提示：

• 0 <= left <= right <= 231 - 1

解题思路

对于任何整数 n，n 和 n-1 的按位与操作会清除 n 的二进制表示中最右边的1。通过不断执行这个操作，我们可以清除 right 的所有位，直到它不再大于 left。

当循环结束时，right 的值就是从 left 到 right 的所有数按位与操作的结果。这是因为：

• 在循环过程中，我们一直在清除 right 的二进制表示中最右边的1，直到 right 不再大于 left。
• 当 right 不再大于 left 时，right 的每一位都是 left 到 right 范围内所有数的共同位（即这些位在所有数中都是1）。
• 由于 left 可能比 right 大，因此我们需要再次检查 left 和 right 是否相等。如果不相等，说明 right 已经小于 left，我们无法得到准确的按位与结果，此时应该返回0。

var rangeBitwiseAnd = function (left, right) {
    while (left < right) {
        right &= (right - 1)
    }
    return right
};