位运算 – shelterofly

3315.构造最小位运算数组II

目标

给你一个长度为 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] <= 10^9
nums[i] 是一个质数。

思路

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

参考 3314.构造最小位运算数组I，数值范围变成了 10^9，纯暴力方法不可行。

考虑 x + 1 对 x bit 位的影响，加 1 会将 x 最右侧的 0 变为 1，同时将 0 右侧的连续 1 变为 0。 x | x + 1 实际上就是将 x 的最右侧的 0 变为 1。现在已知 num = x | x + 1，需要反过来找到最小的 x。根据前面的分析，num 最低位一定是连续的 1，要使 x 最小，只需将连续 1 的最高位置为 0 即可。

代码


/**
 * @date 2026-01-21 9:03
 */
public class MinBitwiseArray3315 {

    public int[] minBitwiseArray(List<Integer> nums) {
        int n = nums.size();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int num = nums.get(i);
            int j = 0;
            while ((1 & (num >> j)) == 1) {
                j++;
            }
            if (j == 0) {
                res[i] = -1;
            } else {
                res[i] = (num ^ (1 << (j - 1)));
            }
        }
        return res;
    }
}

性能

3314.构造最小位运算数组I

目标

给你一个长度为 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;
    }
}

性能

1018.可被5整除的二进制前缀

目标

给定一个二进制数组 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;
    }

}

性能

1930.长度为3的不同回文子序列

目标

给你一个字符串 s ，返回 s 中长度为 3 的不同回文子序列的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文是正着读和反着读一样的字符串。

子序列是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，"ace" 是 "abcde" 的一个子序列。

示例 1：

输入：s = "aabca"
输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)

示例 2：

输入：s = "adc"
输出：0
解释："adc" 不存在长度为 3 的回文子序列。

示例 3：

输入：s = "bbcbaba"
输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)

说明：

3 <= s.length <= 10^5
s 仅由小写英文字母组成

思路

求长度为 3 的不同回文子序列个数。

枚举中间元素，同时枚举 a - z 作为左右两侧的字母，判断是否前后都存在。

对字母计数，在枚举过程中记录前面出现字母的次数，结合总次数可以快速判断后面是否存在相同的字母。注意，如果前面出现的字母与枚举的中间字母相同需要将次数减 1。

代码


/**
 * @date 2025-11-21 8:44
 */
public class CountPalindromicSubsequence1930 {

    public int countPalindromicSubsequence_v1(String s) {
        int[] total = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            total[c - 'a']++;
        }
        boolean[][] visited = new boolean[26][26];
        int[] prefix = new int[26];
        int res = 0;
        for (char c : chars) {
            prefix[c - 'a']++;
            for (int j = 0; j < 26; j++) {
                if (!visited[j][c - 'a'] && total[j] > prefix[j] && ((j == c - 'a' && prefix[j] > 1) || j != c - 'a' && prefix[j] > 0)) {
                    visited[j][c - 'a'] = true;
                    res++;
                }
            }
        }
        return res;
    }

}

性能

3289.数字小镇中的捣蛋鬼

目标

数字小镇 Digitville 中，存在一个数字列表 nums，其中包含从 0 到 n - 1 的整数。每个数字本应只出现一次，然而，有两个顽皮的数字额外多出现了一次，使得列表变得比正常情况下更长。

为了恢复 Digitville 的和平，作为小镇中的名侦探，请你找出这两个顽皮的数字。

返回一个长度为 2 的数组，包含这两个数字（顺序任意）。

示例 1：

输入： nums = [0,1,1,0]
输出： [0,1]
解释：
数字 0 和 1 分别在数组中出现了两次。

示例 2：

输入： nums = [0,3,2,1,3,2]
输出： [2,3]
解释:
数字 2 和 3 分别在数组中出现了两次。

示例 3：

输入： nums = [7,1,5,4,3,4,6,0,9,5,8,2]
输出： [4,5]
解释:
数字 4 和 5 分别在数组中出现了两次。

说明：

2 <= n <= 100
nums.length == n + 2
0 <= nums[i] < n
输入保证 nums 中恰好包含两个重复的元素。

思路

长度为 n + 2 的数组，其元素由 0 1 2 …… n - 1 n 个数字以及该范围内的两个任意数字组成，找出这两个重复数字。

简单的做法是对每个元素计数，找出出现次数为 2 的元素。但是空间复杂度为 O(n)。

进阶的做法是使用位运算得到这两个重复数字的异或值，这两个数字至少有一个 bit 位不同，根据该 bit 位分组，最终得到这两个数字。

代码


/**
 * @date 2025-10-31 9:05
 */
public class GetSneakyNumbers3289 {

    public int[] getSneakyNumbers(int[] nums) {
        int n = nums.length;
        int[] cnt = new int[n];
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            cnt[num]++;
            if (cnt[num] == 2){
                list.add(num);
            }
        }
        int[] res = new int[2];
        for (int i = 0; i < 2; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

性能

3370.仅含置位位的最小整数

目标

给你一个正整数 n。

返回大于等于 n 且二进制表示仅包含置位位的最小整数 x 。

置位位指的是二进制表示中值为 1 的位。

示例 1：

输入： n = 5
输出： 7
解释：
7 的二进制表示是 "111"。

示例 2：

输入： n = 10
输出： 15
解释：
15 的二进制表示是 "1111"。

示例 3：

输入： n = 3
输出： 3
解释：
3 的二进制表示是 "11"。

说明：

1 <= n <= 1000

思路

返回大于等于 n 并且所有 bit 位均为 1 的最小整数。

代码


/**
 * @date 2025-10-29 8:40
 */
public class SmallestNumber3370 {

    public int smallestNumber(int n) {
        int l = 32 - Integer.numberOfLeadingZeros(n);
        return (1 << l) - 1;
    }

}

性能

3541.找到频率最高的元音和辅音

目标

给你一个由小写英文字母（'a' 到 'z'）组成的字符串 s。你的任务是找出出现频率最高的元音（'a'、'e'、'i'、'o'、'u' 中的一个）和出现频率最高的辅音（除元音以外的所有字母），并返回这两个频率之和。

注意：如果有多个元音或辅音具有相同的最高频率，可以任选其中一个。如果字符串中没有元音或没有辅音，则其频率视为 0。

一个字母 x 的频率是它在字符串中出现的次数。

示例 1：

输入: s = "successes"
输出: 6
解释:
元音有：'u' 出现 1 次，'e' 出现 2 次。最大元音频率 = 2。
辅音有：'s' 出现 4 次，'c' 出现 2 次。最大辅音频率 = 4。
输出为 2 + 4 = 6。

示例 2：

输入: s = "aeiaeia"
输出: 3
解释:
元音有：'a' 出现 3 次，'e' 出现 2 次，'i' 出现 2 次。最大元音频率 = 3。
s 中没有辅音。因此，最大辅音频率 = 0。
输出为 3 + 0 = 3。

说明:

1 <= s.length <= 100
s 只包含小写英文字母

思路

计算字符串中辅音字母与元音字母的最高频率之和。

代码


/**
 * @date 2025-09-13 22:46
 */
public class MaxFreqSum3541 {

    public int maxFreqSum(String s) {
        int[] cnt = new int[26];
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                cnt[i]--;
                min = Math.min(min, cnt[i]);
            } else {
                cnt[i]++;
                max = Math.max(max, cnt[i]);
            }
        }
        return Math.max(0, max) - Math.min(0, min);
    }
}

性能

2749.得到整数零需要执行的最少操作数

目标

给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2^i + num2 。

请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。

如果无法使 num1 等于 0 ，返回 -1 。

示例 1：

输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：
- 选择 i = 2 ，并从 3 减去 2^2 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
- 选择 i = 2 ，并从 1 减去 2^2 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
- 选择 i = 0 ，并从 -1 减去 2^0 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。

示例 2：

输入：num1 = 5, num2 = 7
输出：-1
解释：可以证明，执行操作无法使 5 等于 0 。

说明：

1 <= num1 <= 10^9
-10^9 <= num2 <= 10^9

思路

已知整数 num1 和 num2，每次操作需要从 0 ~ 60 选一个整数 i，并将 num1 -= 2^i + num2，返回将 num1 变为 0 的最小操作次数，如果无法完成返回 -1。

假设最少需要操作 k 次，那么 num1 - k * num2 = 2^i1 + 2^i2 + …… + 2^ik，其中 ik 表示第 k 次选择的 i。

问题转换为 num1 - k * num2 能否用 k 个 2 的幂表示。

二进制中 1 的个数就是最少的 k 的个数，它自身的值就是最多可以拆分的个数，也就是说 num = num1 - k * num2 的二进制表示中 1 的个数应小于等于 k 并且 num >= k。

代码


/**
 * @date 2025-09-05 8:46
 */
public class MakeTheIntegerZero2749 {

    public int makeTheIntegerZero(int num1, int num2) {
        for (int i = 0; i < 61; i++) {
            long num = num1 - (long) i * num2;
            if (num <= 0) {
                return -1;
            } else if (Long.bitCount(num) <= i && num >= i) {
                return i;
            }
        }
        return -1;
    }

}

性能

342.4的幂

目标

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4^x

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

说明：

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

进阶：你能不使用循环或者递归来完成本题吗？

思路

判断一个整数是否是 4 的幂。

参考 231.2的幂。

负数的二进制表示中前导零的个数为 0，而 4 的幂的前导零个数为奇数，恰好排除掉了负数。

代码


/**
 * @date 2025-08-15 8:43
 */
public class IsPowerOfFour342 {

    public boolean isPowerOfFour(int n) {
        return (n & (n - 1)) == 0 && Integer.numberOfLeadingZeros(n) % 2 == 1;
    }

}

性能

231.2的幂

目标

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

提示：

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

进阶：你能够不使用循环/递归解决此问题吗？

思路

判断数字是不是 2 的幂。

提前预处理 2 的幂。

进阶做法是判断 n & (n - 1) == 0。

代码


/**
 * @date 2025-08-09 20:33
 */
public class IsPowerOfTwo231 {

    static Set<Integer> set = new HashSet<>();

    static {
        for (int i = 0; i < 31; i++) {
            set.add(1 << i);
        }
    }

    public boolean isPowerOfTwo(int n) {
        return set.contains(n);
    }

}

2026 年 1 月
一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31