面试经典150题——位运算

1、二进制求和

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

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

提示：

• 1 <= a.length, b.length <= 10⁴
• a 和 b 仅由字符 ‘0’ 或 ‘1’ 组成
• 字符串如果不是 “0” ，就不含前导零

1.3 解题代码

class Solution {
    public String addBinary(String a, String b) {
        int m = a.length();
        int n = b.length();
        int i = m - 1;
        int j = n - 1;
        StringBuffer sb = new StringBuffer();
        int carry = 0;
        while(i >= 0 && j >=0){
            int num1 = a.charAt(i) - '0';
            int num2 = b.charAt(j) - '0';
            int num = (num1 + num2 + carry) % 2;
            carry = (num1 + num2 + carry) / 2;
            sb.append(num);
            --i;
            --j;
        }
        while(i >= 0){
            int num1 = a.charAt(i) - '0';
            int num = (num1 + carry) % 2;
            carry = (num1 + carry) / 2;
            sb.append(num);
            --i;
        }
        while(j >= 0){
            int num2 = b.charAt(j) - '0';
            int num = (num2 + carry) % 2;
            carry = (num2 + carry) / 2;
            sb.append(num);
            --j;
        }
        if(carry == 1){
            sb.append('1');
        }
        sb.reverse();
    return sb.toString();
    }
}

1.4 解题思路

1. 二进制加法，采用模拟的思路，逐位相加，考虑进位即可。

2、颠倒二进制位

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

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

提示：

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

提示：

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

2.3 解题代码

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for(int i = 0; i < 32; ++i){
            res += (((n >> i) & 1) << (31 - i));
        }
        return res;
    }
}

2.4 解题思路

1. 使用位运算直接反转，比如第0位的放置到第31位上去。

3、位1的个数

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中设置位(set bit 指在某数的二进制表示中值为 1 的二进制位)的个数（也被称为汉明重量）。

提示：

• 1 <= n <= 2³¹ - 1

3.3 解题代码

class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n > 0){
            n &= (n - 1);
            res++;
        }
        return res;
    }
}

3.4 解题思路

1. 公式化题目，每次用n 与 n - 1做位运算，则能去除掉最低位的1.

4、只出现一次的数字

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

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

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

提示：

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

4.3 解题代码

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < nums.length; ++i){
            res ^= nums[i];
        }
        return res;
    }
}

4.4 解题思路

1. 亦或运算解决问题。

5、只出现一次的数字 II

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

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

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

提示：

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

5.3 解题代码

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < 32; ++i){
            int ans = 0;
            for(int j = 0; j < nums.length; ++j){
                ans += (nums[j] >> i) & 1;
            }
            ans %= 3;
            if(ans > 0){
                res ^= (1 << i);
            }
        }
        return res;
    }
}

5.4 解题思路

1. 使用位运算，计算所有的数在某一位的1的个数，如果是3的倍数，则那个只出现一次的数字在该为为0，否则的话在该位为1。

6、数字范围按位与

6.1 题目链接

点击跳转到题目位置

6.2 题目描述

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

提示：

• 0 <= left <= right <= 2³¹ - 1

6.3 解题代码

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while(left < right){
            left >>= 1;
            right >>= 1;
            ++shift;
        }
        return left << shift;
    }
}

6.4 解题思路

1. 寻找left和right的二进制位的相等前缀即可。