标签： 位运算

目标

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

示例 1：

输入：arr = [0,1,2,3,4,5,6,7,8]
输出：[0,1,2,4,8,3,5,6,7]
解释：[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]

示例 2：

输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
输出：[1,2,4,8,16,32,64,128,256,512,1024]
解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。

示例 3：

输入：arr = [10000,10000]
输出：[10000,10000]

示例 4：

输入：arr = [2,3,5,7,11,13,17,19]
输出：[2,3,5,17,7,11,13,19]

示例 5：

输入：arr = [10,100,1000,10000]
输出：[10,100,10000,1000]

说明：

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^4

思路

将数组 arr 中的元素按照 bitCount 升序排列，如果相等根据元素值升序排列。

代码

/**
 * @date 2026-02-25 8:42
 */
public class SortByBits1356 {

    public int[] sortByBits(int[] arr) {
        return Arrays.stream(arr)
                .boxed()
                .sorted(Comparator.comparing(Integer::bitCount).thenComparing(Integer::intValue))
                .mapToInt(Integer::intValue)
                .toArray();
    }

}

性能

目标

给定一个正整数 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;
    }
}

性能