标签： 位运算

3226.使两个整数相等的位更改次数

目标

给你两个正整数 n 和 k。

你可以选择 n 的 二进制表示 中任意一个值为 1 的位，并将其改为 0。

返回使得 n 等于 k 所需要的更改次数。如果无法实现，返回 -1。

示例 1：

输入： n = 13, k = 4
输出： 2
解释：
最初，n 和 k 的二进制表示分别为 n = (1101)2 和 k = (0100)2，
我们可以改变 n 的第一位和第四位。结果整数为 n = (0100)2 = k。

示例 2：

输入： n = 21, k = 21
输出： 0
解释：
n 和 k 已经相等，因此不需要更改。

示例 3：

输入： n = 14, k = 13
输出： -1
解释：
无法使 n 等于 k。

说明：

  • 1 <= n, k <= 10^6

思路

有两个整数 n 和 k，每次操作可以将 n 的二进制位从 1 改为 0，求使 n 等于 k 所需的操作次数，如果无法实现返回 -1。

注意到这两个整数最大为 10^6，而 2^20 = 1048576，因此最高 bit 位不会超过 20。

依次比较这两个数的第 19 位到第 0 位：

  • 如果相等则跳过
  • 如果 n 的 bit 位为 0 则返回 -1，因为这时 k 对应位置的 bit 位为 1，无法通过操作使之相等
  • 否则累加操作次数

官网题解提供了另一种解法，将每个 bit 为 1 的位置视为一个元素，如果可以通过操作将 n 变为 k， 说明 k 的 bit 1 的集合是 n 的 bit 1 集合的子集。因此 n & k = k，这时我们需要统计 n 与 k bit 位不同的个数，直接使用异或运算统计 bit 1 的个数即可。

return (n & k) == k ? Integer.bitCount(n ^ k) : -1;。

代码


/**
 * @date 2024-11-02 5:00
 */
public class MinChanges3226 {

    public int minChanges(int n, int k) {
        int res = 0;
        for (int i = 19; i >= 0; i--) {
            int bitn = n & 1 << i;
            int bitk = k & 1 << i;
            if (bitn == bitk) {
                continue;
            }
            if (bitn == 0) {
                return -1;
            } else {
                res++;
            }
        }
        return res;
    }
}

性能

3211.生成不含相邻零的二进制字符串

目标

给你一个正整数 n。

如果一个二进制字符串 x 的所有长度为 2 的 子字符串 中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。

返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。

示例 1：

输入： n = 3
输出： ["010","011","101","110","111"]
解释：
长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。

示例 2：

输入： n = 1
输出： ["0","1"]
解释：
长度为 1 的有效字符串有："0" 和 "1"。

说明：

  • 1 <= n <= 18

思路

示例2让人困惑，字符串 0 并没有长度为 2 的子字符串，更别提包含至少一个 1 了，但它是有效字符串。

还是按照题目名称来做吧，生成长度为 n，不含相邻零的二进制字符串。直接回溯即可。

官网题解还提出了一种位运算的解法，主要思想就是将 二进制字符串 视为 数字的二进制表示，问题转化为 0 ~ 2^n - 1 的数字中不含相邻零的个数。由于超出 n 的位数不在我们的考虑范围，为了简化处理，可以直接将数字的低 n 位取反，x ^ ((1 << n) - 1))。1 << n 从 0 开始计向左移 n 位，再减 1，得到低 n 位全为 1 的数字，对它取异或相当于低 n 位取反。问题转换为 数字中是否存在连续的 1。针对每一个数字，无需遍历每一位，直接使用 x & (x >> 1) 是否等于 0 来判断是否含有相邻的 1。相当于将每一位与它前面的位相与，如果存在相邻的 1 就会存在某个位相与的结果为 1 使最终结果不为 0。

代码


/**
 * @date 2024-10-29 0:23
 */
public class ValidStrings3211 {
    List<String> res;
    char[] path;
    int n;

    public List<String> validStrings(int n) {
        res = new ArrayList<>();
        path = new char[n];
        this.n = n;
        backTracing('1', 0);
        return res;
    }

    public void backTracing(char prev, int i) {
        if (i == n) {
            res.add(new String(path));
            return;
        }
        path[i] = '1';
        int next = i + 1;
        backTracing('1', next);
        if (prev != '0') {
            path[i] = '0';
            backTracing('0', next);
        }
    }
}

性能

2917.找出数组中的K-or值

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

nums 中的 K-or 是一个满足以下条件的非负整数：

只有在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值才是 1 。

返回 nums 的 K-or 值。

注意 ：对于整数 x ，如果 (2^i AND x) == 2^i ，则 x 中的第 i 位值为 1 ，其中 AND 为按位与运算符。

示例 1：

输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：nums[0]、nums[2]、nums[4] 和 nums[5] 的第 0 位的值为 1 。
nums[0] 和 nums[5] 的第 1 位的值为 1 。
nums[0]、nums[1] 和 nums[5] 的第 2 位的值为 1 。
nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。
只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。因此，答案为 2^0 + 2^3 = 9 。

示例 2：

输入：nums = [2,12,1,11,4,5], k = 6
输出：0
解释：因为 k == 6 == nums.length ，所以数组的 6-or 等于其中所有元素按位与运算的结果。因此，答案为 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0 。

示例 3：

输入：nums = [10,8,5,9,11,6,8], k = 1
输出：15
解释：因为 k == 1 ，数组的 1-or 等于其中所有元素按位或运算的结果。因此，答案为 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15 。

说明：

  • 1 <= nums.length <= 50
  • 0 <= nums[i] < 2^31
  • 1 <= k <= nums.length

思路

这个目标看起来有些难以理解，其实简单来说就是要我们返回一个int类型的数字，这个数字的每一bit是由数组元素相应bit的值共同决定的。如果数组中在该bit位上为1的元素个数超过k，那么就将结果值的相应bit位置1，否则置0。

现在问题转化为累加数组元素在某一bit位的值，然后与k比较来确定输出结果相应bit的值。可以使用移位运算来判断数字在某一特定bit的值是否为1，例如：数字7的低四位为 0111，想要判断第4个bit（从右边开始数）是否为1，可以将其右移3位，然后与1按位与即可。因为我们要判断的bit位经过右移变成了第一位，并且数字1只有第一位为1，其余位为0。

代码

/**
 * @date 2024-03-06 0:26
 */
public class FindKOr {

    public int findKOr_v1(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < 31; i++) {
            int counter = 0;
            for (int num : nums) {
               // 判断可以省去，提高效率
//                if ((num >> i & 1) == 1) {
//                    counter++;
//                }
                counter += num >> i & 1;
            }
            if (counter >= k) {
                res |= 1 << i;
            }
        }
        return res;
    }
}

性能