标签： 位运算

目标

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

示例 1：

输入：5
输出：2
解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。

示例 2：

输入：7
输出：0
解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。

示例 3：

输入：10
输出：5
解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。

说明：

• 0 <= N < 10^9

思路

已知非负整数 N，求其二进制表示（不含前导零）取反后所表示的十进制数字。

如果直接 ~N 会对前导零取反，只需得到有效位的长度，然后与对应长度的二进制连续 1 异或即可。

代码

/**
 * @date 2026-03-11 8:47
 */
public class BitwiseComplement1009 {

    public int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
        int l = 32 - Integer.numberOfLeadingZeros(n);
        return ((1 << l) - 1) ^ n;
    }

}

性能

目标

给你一个整数数组 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;
    }

}

性能