标签： 位运算

目标

给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。

如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。

示例 1：

输入：n = 22
输出：2
解释：22 的二进制是 "10110" 。
在 22 的二进制表示中，有三个 1，组成两对相邻的 1 。
第一对相邻的 1 中，两个 1 之间的距离为 2 。
第二对相邻的 1 中，两个 1 之间的距离为 1 。
答案取两个距离之中最大的，也就是 2 。

示例 2：

输入：n = 8
输出：0
解释：8 的二进制是 "1000" 。
在 8 的二进制表示中没有相邻的两个 1，所以返回 0 。

示例 3：

输入：n = 5
输出：2
解释：5 的二进制是 "101" 。

说明：

• 1 <= n <= 10^9

思路

判断正整数二进制表示中两个 1 之间 0 的个数，返回其长度 +1，如果不存在返回 0。

根据题意模拟，先去掉右侧的尾零，然后记录 1 前面连续 0 的个数，取最大值即可。

代码

/**
 * @date 2026-02-24 15:03
 */
public class BinaryGap868 {

    public int binaryGap(int n) {
        int res = 0;
        while (n > 0) {
            while (n > 0 && (n & 1) == 0) {
                n >>= 1;
            }
            if (n == 0) {
                break;
            }
            n >>= 1;
            int cnt = 0;
            while (n > 0 && (n & 1) == 0) {
                n >>= 1;
                cnt++;
            }
            if (n > 0) {
                res = Math.max(res, cnt + 1);
            }
        }
        return res;
    }

}

性能

目标

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2：

输入：n = 7
输出：false
解释：7 的二进制表示是：111.

示例 3：

输入：n = 11
输出：false
解释：11 的二进制表示是：1011.

说明：

• 1 <= n <= 2^31 - 1

思路

判断给定 num 的二进制表示是否是 0、1 交替出现的。

将 num 右移 1 位得到 mask，如果是 0、1 交替出现，那么 (mask & num) == 0 && (mask | num) == (1L << l) - 1，其中 l 是 num 的二进制长度。判断 x 是否全是 1，也可以使用 ((x + 1) & x) == 0。

代码

/**
 * @date 2026-02-24 16:40
 */
public class HasAlternatingBits693 {

    public boolean hasAlternatingBits_v1(int n) {
        int mask = n >> 1;
        int or = mask | n;
        return (mask & n) == 0 && ((or + 1) & or) == 0;
    }

}

性能

目标

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

示例 1：

输入：n = 43261596
输出：964176192
解释：
整数       二进制
43261596  00000010100101000001111010011100
964176192 00111001011110000010100101000000

示例 2：

输入：n = 2147483644
输出：1073741822
解释：
整数        二进制
2147483644 01111111111111111111111111111100
1073741822 00111111111111111111111111111110

说明：

• 0 <= n <= 2^31 - 2
• n 为偶数

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

思路

颠倒 32 位有符号整数的二进制表示，返回其表示的数字。

题目限定 n 是正偶数，颠倒之后的最高位为 0，仍是非负数。模拟颠倒的过程，提前记录前导零的个数 lz，最后将结果左移 lz。

代码

/**
 * @date 2024-06-08 22:28
 */
public class ReverseBits190 {

    public int reverseBits_new(int n) {
        int res = 0;
        int lz = Integer.numberOfLeadingZeros(n);
        while (n > 0) {
            int b = n & 1;
            res = (res << 1) | b;
            n >>= 1;
        }
        return res << lz;
    }

}

性能

目标

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

示例 1：

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

示例 2：

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

说明：

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

思路

对二进制字符串求和，将结果以二进制字符串的形式返回。

代码

/**
 * @date 2024-05-25 21:50
 */
public class AddBinary67 {

    public String addBinary_new(String a, String b) {
        int al = a.length();
        int bl = b.length();
        int n = Math.max(a.length(), b.length());
        int i = 1;
        StringBuilder sb = new StringBuilder();
        // 进位
        int j = 0;
        while (i <= n) {
            int av = 0;
            // 计算从右侧起第 i 个位置的下标
            int ai = al - i;
            if (ai >= 0) {
                av = a.charAt(ai) - '0';
            }
            int bv = 0;
            int bi = bl - i;
            if (bi >= 0) {
                bv = b.charAt(bi) - '0';
            }
            int sum = av + bv + j;
            if (sum > 1) {
                sb.append(sum - 2);
                j = 1;
            } else {
                sb.append(sum);
                j = 0;
            }
            i++;
        }
        if (j == 1) {
            sb.append(j);
        }
        return sb.reverse().toString();
    }

}

性能

目标

给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下 条件 均成立：

• ans[i] OR (ans[i] + 1) == nums[i]

除此以外，你需要 最小化 结果数组里每一个 ans[i] 。

如果没法找到符合 条件 的 ans[i] ，那么 ans[i] = -1 。

质数 指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。

示例 1：

输入：nums = [2,3,5,7]
输出：[-1,1,4,3]
解释：
对于 i = 0 ，不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ，所以 ans[0] = -1 。
对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ，因为 1 OR (1 + 1) = 3 。
对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ，因为 4 OR (4 + 1) = 5 。
对于 i = 3 ，满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ，因为 3 OR (3 + 1) = 7 。

示例 2：

输入：nums = [11,13,31]
输出：[9,12,15]
解释：
对于 i = 0 ，满足 ans[0] OR (ans[0] + 1) = 11 的最小 ans[0] 为 9 ，因为 9 OR (9 + 1) = 11 。
对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 13 的最小 ans[1] 为 12 ，因为 12 OR (12 + 1) = 13 。
对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 31 的最小 ans[2] 为 15 ，因为 15 OR (15 + 1) = 31 。

说明：

• 1 <= nums.length <= 100
• 2 <= nums[i] <= 1000
• nums[i] 是一个质数。

思路

有一个长度为 n 的质数列表 nums，针对质数 nums.get(i)，找到最小的值 res[i] 满足 (res[i] | res[i] + 1) == nums.get(i)。

针对每一个质数，直接枚举所有可能的值，判断是否满足条件。

代码

/**
 * @date 2026-01-20 0:15
 */
public class MinBitwiseArray3314 {

    public int[] minBitwiseArray(List<Integer> nums) {
        int n = nums.size();
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for (int i = 0; i < n; i++) {
            int num = nums.get(i);
            for (int j = 0; j < num; j++) {
                if ((j | (j + 1)) == num){
                    res[i] = j;
                    break;
                }
            }
        }
        return res;
    }
}

性能

目标

给定一个二进制数组 nums ( 索引从0开始 )。

我们将 xi 定义为其二进制表示形式为子数组 nums[0..i] (从最高有效位到最低有效位)。

• 例如，如果 nums =[1,0,1] ，那么 x0 = 1, x1 = 2, 和 x2 = 5。

返回布尔值列表 answer，只有当 xi 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。

示例 1：

输入：nums = [0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为 true 。

示例 2：

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

说明：

• 1 <= nums.length <= 10^5
• nums[i] 仅为 0 或 1

思路

有一个二进制数组 nums，定义 xi 为二进制表示为 子数组 [0, i] 的数字，判断 x0 ~ x_(n-1) 能否被 5 整除。

模拟存在的问题是左移多次会溢出。假设 num = k * 5 + mod，左移 1 位相当于乘以 2，2 * num = k * 10 + 2 * mod，能否被 5 整除只需考虑 2 * mod | nums[i]。

代码

/**
 * @date 2025-11-24 8:52
 */
public class PrefixesDivBy5_1018 {

    public List<Boolean> prefixesDivBy5_v1(int[] nums) {
        List<Boolean> res = new ArrayList<>();
        int mod = 0;
        for (int num : nums) {
            mod = (mod << 1) % 5 + num;
            res.add(mod % 5 == 0);
        }
        return res;
    }

}

性能