LeetCode Go · 位运算（3）

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

2419. 按位与最大的最长子数组

中等1 种解法

标签：位运算、脑筋急转弯、数组

题目、示例与约束

给你一个长度为 n 的整数数组 nums 。

考虑 nums 中进行 按位与（bitwise AND）运算得到的值最大的非空子数组。

换句话说，令 k 是 nums 任意子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 k 的子数组。

返回满足要求的最长子数组的长度。

数组的按位与就是对数组中的所有数字进行按位与运算。

子数组 是数组中的一个连续元素序列。

示例 1：

输入：nums = [1,2,3,3,2,2]
输出：2
解释：
子数组按位与运算的最大值是 3 。
能得到此结果的最长子数组是 [3,3]，所以返回 2 。

示例 2：

输入：nums = [1,2,3,4]
输出：1
解释：
子数组按位与运算的最大值是 4 。 
能得到此结果的最长子数组是 [4]，所以返回 1 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

方法一：脑筋急转弯 · Go 实现

思考

按位与不会使数值变大，故子数组 AND 的最大值只能是数组最大值 $mx$ 。一段子数组的 AND 等于 $mx$ ，当且仅当其中每个元素都是 $mx$ 。

问题化为 $mx$ 的最长连续段。先求最大值，再扫一遍统计其连续出现次数。

由于按位与的操作，不会使得数字变大，因此最大值就是数组中的最大值。

题目可以转换为求最大值在数组中最多连续出现的次数。

我们先遍历数组 $nums$ 找到最大值 $mx$ ，然后再遍历数组一次，找到最大值连续出现的次数，最后返回这个次数即可。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O (1)$ 。

func longestSubarray(nums []int) (ans int) {
	mx := slices.Max(nums)
	cnt := 0
	for _, x := range nums {
		if x == mx {
			cnt++
			ans = max(ans, cnt)
		} else {
			cnt = 0
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2425. 所有数对的异或和

中等1 种解法

标签：位运算、脑筋急转弯、数组

题目、示例与约束

给你两个下标从 0 开始的数组 nums1 和 nums2 ，两个数组都只包含非负整数。请你求出另外一个数组 nums3 ，包含 nums1 和 nums2 中 所有数对 的异或和（nums1 中每个整数都跟 nums2 中每个整数恰好匹配一次）。

请你返回 nums3 中所有整数的 异或和 。

示例 1：

输入：nums1 = [2,1,3], nums2 = [10,2,5,0]
输出：13
解释：
一个可能的 nums3 数组是 [8,0,7,2,11,3,4,1,9,1,6,3] 。
所有这些数字的异或和是 13 ，所以我们返回 13 。

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：0
解释：
所有数对异或和的结果分别为 nums1[0] ^ nums2[0] ，nums1[0] ^ nums2[1] ，nums1[1] ^ nums2[0] 和 nums1[1] ^ nums2[1] 。
所以，一个可能的 nums3 数组是 [2,5,1,6] 。
2 ^ 5 ^ 1 ^ 6 = 0 ，所以我们返回 0 。

提示：

1 <= nums1.length, nums2.length <= 10⁵
0 <= nums1[i], nums2[j] <= 10⁹

方法一：脑筋急转弯 + 位运算 · Go 实现

思考

笛卡尔积有 $m n$ 个异或， $m, n \leq 10^{5}$ 不能枚举。同一数异或偶数次抵消、奇数次保留，故 $n u m s 1 [i]$ 对答案的贡献取决于 $n$ 的奇偶。

若 $n$ 为奇数，则 $n u m s 1$ 的全体异或进入答案；若 $m$ 为奇数，则 $n u m s 2$ 的全体异或进入答案。二者再异或即为配对异或的总结果。

由于数组的每个元素都会与另一个数组的每个元素进行异或，我们知道，同一个数异或两次，结果不变，即 $a \oplus a = 0$ 。因此，我们只需要统计数组的长度，就能知道每个元素与另一个数组的每个元素进行异或的次数。

如果 nums2 数组长度为奇数，那么相当于 nums1 中每个元素都与 nums2 中的每个元素进行了奇数次异或，因此 nums1 数组的最终异或结果即为 nums1 数组的所有元素异或的结果。如果为偶数，那么相当于 nums1 中每个元素都与 nums2 中的每个元素进行了偶数次异或，因此 nums1 数组的最终异或结果为 0。

同理，我们可以得知 nums2 数组的最终异或结果。

最终把两个异或结果再异或一次，即可得到最终结果。

时间复杂度 $O (m + n)$ 。其中 $m$ 和 $n$ 分别为数组 nums1 和 nums2 的长度。

func xorAllNums(nums1 []int, nums2 []int) int {
	ans := 0
	if len(nums2)%2 == 1 {
		for _, v := range nums1 {
			ans ^= v
		}
	}
	if len(nums1)%2 == 1 {
		for _, v := range nums2 {
			ans ^= v
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2433. 找出前缀异或的原始数组

中等1 种解法

标签：位运算、数组

题目、示例与约束

给你一个长度为 n 的整数数组 pref 。找出并返回满足下述条件且长度为 n 的数组 arr ：

pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].

注意 ^ 表示 按位异或（bitwise-xor）运算。

可以证明答案是唯一的。

示例 1：

输入：pref = [5,2,0,3,1]
输出：[5,7,2,3,2]
解释：从数组 [5,7,2,3,2] 可以得到如下结果：
- pref[0] = 5
- pref[1] = 5 ^ 7 = 2
- pref[2] = 5 ^ 7 ^ 2 = 0
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1

示例 2：

输入：pref = [13]
输出：[13]
解释：pref[0] = arr[0] = 13

提示：

1 <= pref.length <= 10⁵
0 <= pref[i] <= 10⁶

方法一：位运算 · Go 实现

思考

$p r e f [i]$ 是 $a r r [0. . i]$ 的异或前缀。异或满足 $p r e f [i] \oplus p r e f [i - 1] = a r r [i]$ （令 $p r e f [- 1] = 0$ ），因此原数组由相邻前缀异或唯一确定。 $n \leq 10^{5}$ ，线性一遍即可。

根据题意，我们有式子一：

p r e f [i] = a r r [0] \oplus a r r [1] \oplus \dots \oplus a r r [i]

所以，也就有式子二：

p r e f [i - 1] = a r r [0] \oplus a r r [1] \oplus \dots \oplus a r r [i - 1]

我们将式子一二进行异或运算，得到：

p r e f [i] \oplus p r e f [i - 1] = a r r [i]

即答案数组的每一项都是前缀异或数组的相邻两项进行异或运算得到的。

时间复杂度 $O (n)$ ，其中 $n$ 为前缀异或数组的长度。忽略答案的空间消耗，空间复杂度 $O (1)$ 。

func findArray(pref []int) []int {
	n := len(pref)
	ans := []int{pref[0]}
	for i := 1; i < n; i++ {
		ans = append(ans, pref[i-1]^pref[i])
	}
	return ans
}

力扣原题 · Doocs 题解来源

2438. 二的幂数组中查询范围内的乘积

中等1 种解法

标签：位运算、数组、前缀和

题目、示例与约束

给你一个正整数 n ，你需要找到一个下标从 0 开始的数组 powers ，它包含最少数目的 2 的幂，且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述，构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [left_i, right_i] ，其中 queries[i] 表示请你求出满足 left_i <= j <= right_i 的所有 powers[j] 的乘积。

请你返回一个数组 answers ，长度与 queries 的长度相同，其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大，请你将每个 answers[i] 都对 10⁹ + 7 取余。

示例 1：

输入：n = 15, queries = [[0,1],[2,2],[0,3]]
输出：[2,4,64]
解释：
对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案：powers[2] = 4 。
第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 10⁹ + 7 取余得到的结果都相同，所以返回 [2,4,64] 。

示例 2：

输入：n = 2, queries = [[0,0]]
输出：[2]
解释：
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 10⁹ + 7 取余后结果相同，所以返回 [2] 。

提示：

1 <= n <= 10⁹
1 <= queries.length <= 10⁵
0 <= start_i <= end_i < powers.length

方法一：位运算 + 模拟 · Go 实现

思考

$n$ 分解为升序的 $2$ 的幂，即其二进制中的各个置位。 $n \leq 10^{9}$ ，用 $n & - n$ 反复取最低位即可得到 $powers$ ，长度不超过 $30$ 。

询问至多 $10^{5}$ 、区间长度至多 $30$ ，对每个 $[l, r]$ 直接连乘取模即可，不必前缀积。

我们可以使用位运算（Lowbit）来得到 $powers$ 数组，然后通过模拟的方式求出每个查询的答案。

首先，对于给定的正整数 $n$ ，我们通过 $n & - n$ 可以快速得到二进制表示中最低位的 $1$ 对应的数值，也就是当前数的最小 $2$ 的幂因子。对 $n$ 反复执行这个操作并减去该值，就能依次得到所有置位的 $2$ 的幂，形成 $powers$ 数组。这个数组是递增的，且长度等于 $n$ 的二进制表示中 $1$ 的个数。

接下来，我们需要处理每个查询。对于当前查询 $(l, r)$ ，我们需要计算

answers [i] = \prod_{j = l}^{r} powers [j]

其中 $answers [i]$ 是第 $i$ 个查询的答案。由于查询的结果可能非常大，我们需要对每个答案取模 $10^{9} + 7$ 。

时间复杂度 $O (m \times \log n)$ ，其中 $m$ 为数组 $queries$ 的长度。忽略答案的空间消耗，空间复杂度 $O (\log n)$ 。

func productQueries(n int, queries [][]int) []int {
	var powers []int
	for n > 0 {
		x := n & -n
		powers = append(powers, x)
		n -= x
	}
	const mod = 1_000_000_007
	ans := make([]int, 0, len(queries))
	for _, q := range queries {
		l, r := q[0], q[1]
		x := 1
		for j := l; j <= r; j++ {
			x = x * powers[j] % mod
		}
		ans = append(ans, x)
	}
	return ans
}

力扣原题 · Doocs 题解来源

2505. 所有子序列和的按位或 🔒

中等1 种解法

标签：位运算、脑筋急转弯、数组、数学、前缀和

题目、示例与约束

给你一个整数数组 nums ，返回对数组中所有可能的 子序列 之和进行按位或运算后得到的值。

数组的 子序列 是从数组中删除零个或多个元素且不改变剩余元素的顺序得到的序列。

示例 1：

输入：nums = [2,1,0,3]
输出：7
解释：所有可能的子序列的和包括：0、1、2、3、4、5、6 。
由于 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 = 7，所以返回 7 。

示例 2：

输入：nums = [0,0,0]
输出：0
解释：0 是唯一可能的子序列的和，所以返回 0 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

方法一：位运算 · Go 实现

思考

子序列和共有 $2^{n}$ 个， $n \leq 10^{5}$ 时不能枚举。所求是这些和的按位或，因此只需判断每一位能否在某个子序列和中出现。

某一位上的 $1$ 既可直接来自原数，也可由更低位成对进位产生。统计各位 $1$ 的个数后自低向高扫描：该位计数非零则或入答案，并把 $⌊ c n t [i] / 2 ⌋$ 累加到下一位，从而刻画全部可能的进位。

我们先用数组 $c n t$ 统计每一位上 $1$ 的个数，然后从低位到高位，如果该位上 $1$ 的个数大于 $0$ ，则将该位所表示的数加入到答案中。然后判断是否可以进位，是则累加到下一位。

时间复杂度 $O (n \times \log M)$ ，其中 $n$ 和 $M$ 分别为数组长度和数组中元素的最大值。

func subsequenceSumOr(nums []int) int64 {
	cnt := make([]int, 64)
	ans := 0
	for _, v := range nums {
		for i := 0; i < 31; i++ {
			if v>>i&1 == 1 {
				cnt[i]++
			}
		}
	}
	for i := 0; i < 63; i++ {
		if cnt[i] > 0 {
			ans |= 1 << i
		}
		cnt[i+1] += cnt[i] / 2
	}
	return int64(ans)
}

力扣原题 · Doocs 题解来源

2506. 统计相似字符串对的数目

简单1 种解法

标签：位运算、数组、哈希表、字符串、计数

题目、示例与约束

给你一个下标从 0 开始的字符串数组 words 。

如果两个字符串由相同的字符组成，则认为这两个字符串相似。

例如，"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成。
然而，"abacba" 和 "bcfd" 不相似，因为它们不是相同字符组成的。

请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= words.length - 1 。

示例 1：

输入：words = ["aba","aabb","abcd","bac","aabc"]
输出：2
解释：共有 2 对满足条件：
- i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。 
- i = 3 且 j = 4 ：words[3] 和 words[4] 只由字符 'a'、'b' 和 'c' 。

示例 2：

输入：words = ["aabb","ab","ba"]
输出：3
解释：共有 3 对满足条件：
- i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。 
- i = 0 且 j = 2 ：words[0] 和 words[2] 只由字符 'a' 和 'b' 组成。 
- i = 1 且 j = 2 ：words[1] 和 words[2] 只由字符 'a' 和 'b' 组成。

示例 3：

输入：words = ["nba","cba","dba"]
输出：0
解释：不存在满足条件的下标对，返回 0 。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成

方法一：哈希表 + 位运算 · Go 实现

思考

两字符串相似当且仅当字母集合相同。两两比较集合在 $n \leq 100$ 时可行，但每次构造集合仍有常数开销，且未利用“相同集合即可配对”这一结构。

字母仅 $26$ 种，可用一个整数位掩码表示集合。遍历时用哈希表统计已出现的掩码个数，当前串与此前同掩码的串都能配对，累加后把自身计入。

对于每个字符串，我们可以将其转换为一个长度为 $26$ 的二进制数，其中第 $i$ 位为 $1$ 表示该字符串中包含第 $i$ 个字母。

如果两个字符串包含相同的字母，则它们的二进制数是相同的，因此，对于每个字符串，我们用哈希表统计其二进制数出现的次数，每一次累加到答案中，再将其二进制数出现的次数加 $1$ 。

时间复杂度 $O (L)$ ，空间复杂度 $O (n)$ 。其中 $L$ 是所有字符串的长度之和，而 $n$ 是字符串的数量。

func similarPairs(words []string) (ans int) {
	cnt := map[int]int{}
	for _, s := range words {
		x := 0
		for _, c := range s {
			x |= 1 << (c - 'a')
		}
		ans += cnt[x]
		cnt[x]++
	}
	return
}

力扣原题 · Doocs 题解来源

2527. 查询数组异或美丽值

中等1 种解法

标签：位运算、数组、数学

题目、示例与约束

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

三个下标 i ，j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。

一个数组的 异或美丽值 是数组中所有满足 0 <= i, j, k < n 的三元组 (i, j, k) 的 有效值 的异或结果。

请你返回 nums 的异或美丽值。

注意：

val1 | val2 是 val1 和 val2 的按位或。
val1 & val2 是 val1 和 val2 的按位与。

示例 1：

输入：nums = [1,4]
输出：5
解释：
三元组和它们对应的有效值如下：
- (0,0,0) 有效值为 ((1 | 1) & 1) = 1
- (0,0,1) 有效值为 ((1 | 1) & 4) = 0
- (0,1,0) 有效值为 ((1 | 4) & 1) = 1
- (0,1,1) 有效值为 ((1 | 4) & 4) = 4
- (1,0,0) 有效值为 ((4 | 1) & 1) = 1
- (1,0,1) 有效值为 ((4 | 1) & 4) = 4
- (1,1,0) 有效值为 ((4 | 4) & 1) = 0
- (1,1,1) 有效值为 ((4 | 4) & 4) = 4 
数组的异或美丽值为所有有效值的按位异或 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5 。

示例 2：

输入：nums = [15,45,20,2,34,35,5,44,32,30]
输出：34
解释：数组的异或美丽值为 34 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

方法一：位运算 · Go 实现

思考

三重循环枚举 $(i, j, k)$ 并异或 $(nums [i] ∣ nums [j]) & nums [k]$ ，在 $n \leq 10^{5}$ 下不可行。异或满足交换律，成对相同的项会抵消。

$i \neq j$ 时 $(i, j, k)$ 与 $(j, i, k)$ 贡献相同，异或为 $0$ 。 $i = j$ 且 $i \neq k$ 时 $(nums [i] & nums [k])$ 与对换后的项再次抵消。剩下 $i = j = k$ ，答案即全体元素的异或。

我们首先考虑 $i$ 与 $j$ 不相等的情况，此时 ((nums[i] | nums[j]) & nums[k]) 与 ((nums[j] | nums[i]) & nums[k]) 的结果是相同的，两者的异或结果为 $0$ 。

因此，我们只需要考虑 $i$ 与 $j$ 相等的情况。此时 ((nums[i] | nums[j]) & nums[k]) = (nums[i] & nums[k])，如果 $i \neq k$ ，那么与 nums[k] & nums[i] 的结果是相同的，这些值的异或结果为 $0$ 。

因此，我们最终只需要考虑 $i = j = k$ 的情况，那么答案就是所有 $n u m s [i]$ 的异或结果。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为数组的长度。

func xorBeauty(nums []int) (ans int) {
	for _, x := range nums {
		ans ^= x
	}
	return
}

力扣原题 · Doocs 题解来源

2546. 执行逐位运算使字符串相等

中等1 种解法

标签：位运算、字符串

题目、示例与约束

给你两个下标从 0 开始的二元字符串 s 和 target ，两个字符串的长度均为 n 。你可以对 s 执行下述操作任意次：

选择两个不同的下标 i 和 j ，其中 0 <= i, j < n 。
同时，将 s[i] 替换为 (s[i] OR s[j]) ，s[j] 替换为 (s[i] XOR s[j]) 。

例如，如果 s = "0110" ，你可以选择 i = 0 和 j = 2，然后同时将 s[0] 替换为 (s[0] OR s[2] = 0 OR 1 = 1)，并将 s[2] 替换为 (s[0] XOR s[2] = 0 XOR 1 = 1)，最终得到 s = "1110" 。

如果可以使 s 等于 target ，返回 true ，否则，返回 false 。

示例 1：

输入：s = "1010", target = "0110"
输出：true
解释：可以执行下述操作：
- 选择 i = 2 和 j = 0 ，得到 s = "0010".
- 选择 i = 2 和 j = 1 ，得到 s = "0110".
可以使 s 等于 target ，返回 true 。

示例 2：

输入：s = "11", target = "00"
输出：false
解释：执行任意次操作都无法使 s 等于 target 。

提示：

n == s.length == target.length
2 <= n <= 10⁵
s 和 target 仅由数字 0 和 1 组成

方法一：脑筋急转弯 · Go 实现

思考

允许的操作为 $s [i] \lor s [j]$ 与 $s [i] \oplus s [j]$ 写回其中一位。 $0$ 与 $0$ 无法变出 $1$ ，而只要存在一个 $1$ ，就可以把它复制到任意位置或与另一位异或成 $0$ 。

因此 $s$ 与 $target$ 能互相转化，当且仅当二者同时含 $1$ 或同时不含 $1$ 。

我们注意到 $1$ 其实是数字转换的“工具”，因此只要两个字符串中都有 $1$ 或者都没有 $1$ ，那么就可以通过操作使得两个字符串相等。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串的长度。空间复杂度 $O (1)$ 。

func makeStringsEqual(s string, target string) bool {
	return strings.Contains(s, "1") == strings.Contains(target, "1")
}

力扣原题 · Doocs 题解来源

2564. 子字符串异或查询

中等1 种解法

标签：位运算、数组、哈希表、字符串

题目、示例与约束

给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [first_i, second_i] 。

对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 first_i 按位异或 得到 second_i ，换言之，val ^ first_i == second_i 。

第 i 个查询的答案是子字符串 [left_i, right_i] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为 [-1, -1] 。如果有多个答案，请你选择 left_i 最小的一个。

请你返回一个数组 ans ，其中 ans[i] = [left_i, right_i] 是第 i 个查询的答案。

子字符串 是一个字符串中一段连续非空的字符序列。

示例 1：

输入：s = "101101", queries = [[0,5],[1,2]]
输出：[[0,2],[2,3]]
解释：第一个查询，端点为 [0,2] 的子字符串为 "101"，对应十进制数字 5，且 5 ^ 0 = 5，所以第一个查询的答案为 [0,2]。第二个查询中，端点为 [2,3] 的子字符串为 "11"，对应十进制数字 3，且 3 ^ 1 = 2。所以第二个查询的答案为 [2,3]。

示例 2：

输入：s = "0101", queries = [[12,8]]
输出：[[-1,-1]]
解释：这个例子中，没有符合查询的答案，所以返回 [-1,-1]。

示例 3：

输入：s = "1", queries = [[4,5]]
输出：[[0,0]]
解释：这个例子中，端点为 [0,0] 的子字符串对应的十进制值为 1，且 1 ^ 4 = 5。所以答案为 [0,0]。

提示：

1 <= s.length <= 10⁴
s[i] 要么是 '0' ，要么是 '1' 。
1 <= queries.length <= 10⁵
0 <= first_i, second_i <= 10⁹

方法一：预处理 + 枚举 · Go 实现

思考

每次查询要找二进制串中值为 $f i r s t \oplus s e c o n d$ 的最短（同长则最左）子串。查询达 $10^{5}$ ，值是 $32$ 位整数，现场扫描每个查询过慢。

任意 $32$ 位子串已覆盖全部可能取值。从每个起点向右至多延伸 $32$ 位，首次出现的值记入哈希表。遇到前导零的全零串立即停止，以免更长的等价表示覆盖更短者。查询时直接查表。

我们可以先预处理出所有长度为 $1$ 到 $32$ 的子串对应的十进制值，找到每个值对应的最小下标以及对应的右端点下标，存放在哈希表 $d$ 中。

然后枚举每个查询，对于每个查询 $[f i r s t, s e c o n d]$ ，我们只需要在哈希表 $d$ 中查找是否存在键为 $f i r s t \oplus s e c o n d$ 的键值对，如果存在，把对应的最小下标和右端点下标加入答案数组即可，否则加入 $[- 1, - 1]$ 。

时间复杂度 $O (n \times \log M + m)$ ，空间复杂度 $O (n \times \log M)$ 。其中 $n$ 和 $m$ 分别为字符串 $s$ 和查询数组 $q u e r i e s$ 的长度，而 $M$ 可以取整数的最大值 $2^{31} - 1$ 。

func substringXorQueries(s string, queries [][]int) (ans [][]int) {
	d := map[int][]int{}
	for i := range s {
		x := 0
		for j := 0; j < 32 && i+j < len(s); j++ {
			x = x<<1 | int(s[i+j]-'0')
			if _, ok := d[x]; !ok {
				d[x] = []int{i, i + j}
			}
			if x == 0 {
				break
			}
		}
	}
	for _, q := range queries {
		first, second := q[0], q[1]
		val := first ^ second
		if v, ok := d[val]; ok {
			ans = append(ans, v)
		} else {
			ans = append(ans, []int{-1, -1})
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2568. 最小无法得到的或值

中等1 种解法

标签：位运算、脑筋急转弯、数组

题目、示例与约束

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

如果存在一些整数满足 0 <= index₁ < index₂ < ... < index_k < nums.length ，得到 nums[index₁] | nums[index₂] | ... | nums[index_k] = x ，那么我们说 x 是 可表达的 。换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。

请你返回 nums 不可表达的 最小非零整数 。

示例 1：

输入：nums = [2,1]
输出：4
解释：1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。

示例 2：

输入：nums = [5,3,2]
输出：1
解释：1 是最小不可表达的数字。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

方法一：枚举 2 的幂 · Go 实现

思考

“可表达”指能由数组某个非空子集按位或得到。或运算只会把位打开，若所有小于 $2^{k}$ 的幂都在数组中，则 $[1, 2^{k + 1} - 1]$ 均可表达。

因此最小不可表达数必是某个缺失的 $2$ 的幂。把数组放入集合后，从 $2^{0}$ 起找第一个不在集合中的幂。

我们从整数 $1$ 开始考虑，如果 $1$ 是可表达的，那么它必须出现在数组 nums 中；如果 $2$ 是可表达的，那么它必须出现在数组 nums 中；如果 $1$ 和 $2$ 都是可表达的，那么它们的或运算 $3$ 也是可表达的，以此类推。

因此，我们可以枚举 $2$ 的幂，如果当前枚举的 $2^{i}$ 不在数组 nums 中，那么 $2^{i}$ 就是不可表达的最小整数。

时间复杂度 $O (n + \log M)$ ，空间复杂度 $O (n)$ 。其中 $n$ 和 $M$ 分别是数组 nums 的长度和数组 nums 中的最大值。

func minImpossibleOR(nums []int) int {
	s := map[int]bool{}
	for _, x := range nums {
		s[x] = true
	}
	for i := 0; ; i++ {
		if !s[1<<i] {
			return 1 << i
		}
	}
}

力扣原题 · Doocs 题解来源

2588. 统计美丽子数组数目

中等1 种解法

标签：位运算、数组、哈希表、前缀和

题目、示例与约束

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：

选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
将 nums[i] 和 nums[j] 都减去 2^k 。

如果一个子数组内执行上述操作若干次（包括 0 次）后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个美丽的子数组。

请你返回数组 nums 中 美丽子数组 的数目。

子数组是一个数组中一段连续非空的元素序列。

注意：所有元素最初都是 0 的子数组被认为是美丽的，因为不需要进行任何操作。

示例 1：

输入：nums = [4,3,1,2,4]
输出：2
解释：nums 中有 2 个美丽子数组：[4,3,1,2,4] 和 [4,3,1,2,4] 。
- 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ：
  - 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 2¹ ，子数组变成 [1, 1, 0] 。
  - 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 2⁰ ，子数组变成 [0, 0, 0] 。
- 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ：
  - 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 2² ，子数组变成 [0, 3, 1, 2, 0] 。
  - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 2⁰ ，子数组变成 [0, 2, 0, 2, 0] 。
  - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 2¹ ，子数组变成 [0, 0, 0, 0, 0] 。

示例 2：

输入：nums = [1,10,4]
输出：0
解释：nums 中没有任何美丽子数组。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶

方法一：前缀异或 + 哈希表 · Go 实现

思考

子数组美丽当且仅当能通过若干次“选两位同时减 $2^{k}$ ”变成全零，即每一位上 $1$ 的个数均为偶数，也就是子数组异或为 $0$ 。枚举区间再异或是平方级。

前缀异或相等的两个位置之间的一段异或为 $0$ 。哈希表统计每个前缀出现次数，当前 $mask$ 加上已有相同值的个数。初始放入 $0$ 以计入从开头出发的段。

我们观察发现，一个子数组能变成一个全为 $0$ 的数组，当且仅当该子数组中的所有元素，每一个二进制位上的 $1$ 的个数都是偶数个。

如果存在下标 $i$ 和 $j$ ，满足 $i < j$ ，且子数组 $n u m s [0, . ., i]$ 和 $n u m s [0, . ., j]$ 二进制位上的 $1$ 的个数同奇同偶，那么就可以将子数组 $n u m s [i + 1, . ., j]$ 变成一个全为 $0$ 的数组。

因此，我们可以用前缀异或的方法，用哈希表 $c n t$ 统计每个前缀异或值出现的次数。遍历数组，对于每个元素 $x$ ，我们计算出它的前缀异或值 $m a s k$ ，然后将 $m a s k$ 出现的次数加到答案中。然后，我们将 $m a s k$ 的出现次数加 $1$ 。

最后，我们返回答案即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为数组 $n u m s$ 的长度。

func beautifulSubarrays(nums []int) (ans int64) {
	cnt := map[int]int{0: 1}
	mask := 0
	for _, x := range nums {
		mask ^= x
		ans += int64(cnt[mask])
		cnt[mask]++
	}
	return
}

力扣原题 · Doocs 题解来源

2595. 奇偶位数

简单2 种解法

标签：位运算

题目、示例与约束

给你一个正整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

请注意，在数字的二进制表示中，位下标的顺序 从右到左。

返回整数数组 answer ，其中 answer = [even, odd] 。

示例 1：

输入：n = 50

输出：[1,2]

解释：

50 的二进制表示是 110010。

在下标 1，4，5 对应的值为 1。

示例 2：

输入：n = 2

输出：[0,1]

解释：

2 的二进制表示是 10。

只有下标 1 对应的值为 1。

提示：

1 <= n <= 1000

方法一：枚举 · Go 实现

思考

$n$ 的范围不超过 $10^{3}$ ，从低位到高位逐位检查即可。下标奇偶用 $i \oplus 1$ 翻转，该位为 $1$ 则对应计数加一。

我们根据题意，枚举 $n$ 的二进制表示中从低位到高位的每一位，如果该位为 $1$ ，则根据该位的下标是奇数还是偶数，将对应的计数器加 $1$ 即可。

时间复杂度 $O (\log n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为给定的整数。

func evenOddBit(n int) []int {
	ans := make([]int, 2)
	for i := 0; n != 0; n, i = n>>1, i^1 {
		ans[i] += n & 1
	}
	return ans
}

方法二：位运算 · Go 实现

思考

方法一位数与 $\log n$ 成正比。偶数下标的位恰好是掩码 $0 x 5555$ ，与 $n$ 按位与后统计 $1$ 的个数即偶数位；奇数位用补掩码同样处理，常数时间。

我们可以定义一个掩码 $mask = 0x5555$ ，它的二进制表示为 ${0101 0101 0101 0101}_{2}$ 。那么 $n$ 与 $mask$ 进行按位与运算，就可以得到 $n$ 的二进制表示中偶数下标的位，而 $n$ 与 $mask$ 取反后再进行按位与运算，就可以得到 $n$ 的二进制表示中奇数下标的位。统计这两个结果中 $1$ 的个数即可。

时间复杂度 $O (1)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为给定的整数。

func evenOddBit(n int) []int {
	mask := 0x5555
	even := bits.OnesCount32(uint32(n & mask))
	odd := bits.OnesCount32(uint32(n & ^mask))
	return []int{even, odd}
}

力扣原题 · Doocs 题解来源

2657. 找到两个数组的前缀公共数组

中等3 种解法

标签：位运算、数组、哈希表

题目、示例与约束

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。

A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。

请你返回 A 和 B 的 前缀公共数组 。

如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的排列。

示例 1：

输入：A = [1,3,2,4], B = [3,1,2,4]
输出：[0,2,3,4]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。
i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。

示例 2：

输入：A = [2,3,1], B = [3,1,2]
输出：[0,1,3]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：只有 3 是公共元素，所以 C[1] = 1 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。

提示：

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
题目保证 A 和 B 两个数组都是 n 个元素的排列。

方法一：计数 · Go 实现

思考

两个排列的前缀公共元素个数。每次重建集合求交， $n \leq 50$ 可行，但前缀只增长一个元素。

分别计数 $A$ 、 $B$ 的出现，对值域 $[1, n]$ 取 $min$ 再求和，即当前公共个数。

我们可以使用两个数组 $c n t 1$ 和 $c n t 2$ 分别记录数组 $A$ 和 $B$ 中每个元素出现的次数，用数组 $a n s$ 记录答案。

遍历数组 $A$ 和 $B$ ，将 $A [i]$ 在 $c n t 1$ 中出现次数加一，将 $B [i]$ 在 $c n t 2$ 中出现次数加一。然后枚举 $j \in [1, n]$ ，计算 $c n t 1$ 和 $c n t 2$ 中每个元素 $j$ 出现次数的最小值，累加到 $a n s [i]$ 中。

遍历结束后，返回答案数组 $a n s$ 即可。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $A$ 和 $B$ 的长度。

func findThePrefixCommonArray(A []int, B []int) []int {
	n := len(A)
	cnt1 := make([]int, n+1)
	cnt2 := make([]int, n+1)
	ans := make([]int, n)
	for i, a := range A {
		b := B[i]
		cnt1[a]++
		cnt2[b]++
		for j := 1; j <= n; j++ {
			ans[i] += min(cnt1[j], cnt2[j])
		}
	}
	return ans
}

方法二：位运算（异或运算） · Go 实现

思考

方法一每步 $O (n)$ 扫值域。排列中每个值恰出现两次（两个数组各一次），用 $v i s$ 异或翻转：第二次见到时公共数加一，从而 $O (1)$ 更新。

我们可以使用一个长度为 $n + 1$ 的数组 $v i s$ 记录数组 $A$ 和 $B$ 中每个元素的出现情况，数组 $v i s$ 的初始值为 $1$ 。另外，我们用一个变量 $s$ 记录当前公共元素的个数。

接下来，我们遍历数组 $A$ 和 $B$ ，更新 $v i s [A [i]] = v i s [A [i]] \oplus 1$ ，并且更新 $v i s [B [i]] = v i s [B [i]] \oplus 1$ ，其中 $\oplus$ 表示异或运算。

如果遍历到当前位置，元素 $A [i]$ 出现过两次（即在数组 $A$ 和 $B$ 中都出现过），那么 $v i s [A [i]]$ 的值将为会 $1$ ，我们将 $s$ 加一。同理，如果元素 $B [i]$ 出现过两次，那么 $v i s [B [i]]$ 的值将为会 $1$ ，我们将 $s$ 加一。然后将 $s$ 的值加入到答案数组 $a n s$ 中。

遍历结束后，返回答案数组 $a n s$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $A$ 和 $B$ 的长度。

func findThePrefixCommonArray(A []int, B []int) (ans []int) {
	vis := make([]int, len(A)+1)
	for i := range vis {
		vis[i] = 1
	}
	s := 0
	for i, a := range A {
		b := B[i]
		vis[a] ^= 1
		s += vis[a]
		vis[b] ^= 1
		s += vis[b]
		ans = append(ans, s)
	}
	return
}

方法三：位运算（空间优化） · Go 实现

思考

方法二仍用 $O (n)$ 数组。 $n \leq 50$ ，可用两个整数作位集，前缀或运算后 bit_count(x & y) 即公共个数，额外空间降为常数。

由于题目中给定的数组 $A$ 和 $B$ 的元素范围是 $[1, n]$ ，且不超过 $50$ ，我们可以使用一个整数 $x$ 和一个整数 $y$ 来分别表示数组 $A$ 和 $B$ 中每个元素的出现情况。具体地，我们用整数 $x$ 的第 $i$ 位表示元素 $i$ 是否在数组 $A$ 中出现过，用整数 $y$ 的第 $i$ 位表示元素 $i$ 是否在数组 $B$ 中出现过。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $A$ 和 $B$ 的长度。空间复杂度 $O (1)$ 。

func findThePrefixCommonArray(A []int, B []int) []int {
	n := len(A)
	ans := make([]int, n)
	var x, y int
	for i := 0; i < n; i++ {
		x |= 1 << A[i]
		y |= 1 << B[i]
		ans[i] = bits.OnesCount(uint(x & y))
	}
	return ans
}

力扣原题 · Doocs 题解来源

2683. 相邻值的按位异或

中等1 种解法

标签：位运算、数组

题目、示例与约束

下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 按位异或（⊕）派生而来。

特别地，对于范围 [0, n - 1] 内的每个下标 i ：

如果 i = n - 1 ，那么 derived[i] = original[i] ⊕ original[0]
否则 derived[i] = original[i] ⊕ original[i + 1]

给你一个数组 derived ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。

如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。

二进制数组是仅由 0 和 1 组成的数组。

示例 1：

输入：derived = [1,1,0]
输出：true
解释：能够派生得到 [1,1,0] 的有效原始二进制数组是 [0,1,0] ：
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

示例 2：

输入：derived = [1,1]
输出：true
解释：能够派生得到 [1,1] 的有效原始二进制数组是 [0,1] ：
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

示例 3：

输入：derived = [1,0]
输出：false
解释：不存在能够派生得到 [1,0] 的有效原始二进制数组。

提示：

n == derived.length
1 <= n <= 10⁵
derived 中的值不是 0 就是 1 。

方法一：位运算 · Go 实现

思考

由 $d e r i v e d [i] = a [i] \oplus a [i + 1]$ 反推是否存在 $a$ 。枚举 $a [0]$ 再推一遍， $n \leq 10^{5}$ 可行，但全部异或后每项出现两次，故 $⨁ d e r i v e d = 0$ 是充要条件。

一次异或折叠即可判定。

我们不妨假设原始二进制数组为 $a$ ，派生数组为 $b$ ，那么有：

b_{0} = a_{0} \oplus a_{1} b_{1} = a_{1} \oplus a_{2} \dots b_{n - 1} = a_{n - 1} \oplus a_{0}

由于异或运算满足交换律和结合律，因此有：

b_{0} \oplus b_{1} \oplus \dots \oplus b_{n - 1} = (a_{0} \oplus a_{1}) \oplus (a_{1} \oplus a_{2}) \oplus \dots \oplus (a_{n - 1} \oplus a_{0}) = 0

因此，只要派生数组的所有元素的异或和为 $0$ ，就一定存在一个满足要求的原始二进制数组。

时间复杂度 $O (n)$ ，其中 $n$ 为数组长度。空间复杂度 $O (1)$ 。

func doesValidArrayExist(derived []int) bool {
	s := 0
	for _, x := range derived {
		s ^= x
	}
	return s == 0
}

力扣原题 · Doocs 题解来源

2732. 找到矩阵中的好子集

困难1 种解法

标签：位运算、数组、哈希表、矩阵

题目、示例与约束

给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。

从原矩阵中选出若干行构成一个行的非空子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 好子集。

更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。

请你返回一个整数数组，它包含好子集的行下标，请你将其升序返回。

如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。

一个矩阵 grid 的行子集，是删除 grid 中某些（也可能不删除）行后，剩余行构成的元素集合。

示例 1：

输入：grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
输出：[0,1]
解释：我们可以选择第 0 和第 1 行构成一个好子集。
选出来的子集大小为 2 。
- 第 0 列的和为 0 + 0 = 0 ，小于等于子集大小的一半。
- 第 1 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 2 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 3 列的和为 0 + 1 = 1 ，小于等于子集大小的一半。

示例 2：

输入：grid = [[0]]
输出：[0]
解释：我们可以选择第 0 行构成一个好子集。
选出来的子集大小为 1 。
- 第 0 列的和为 0 ，小于等于子集大小的一半。

示例 3：

输入：grid = [[1,1,1],[1,1,1]]
输出：[]
解释：没有办法得到一个好子集。

提示：

m == grid.length
n == grid[i].length
1 <= m <= 10⁴
1 <= n <= 5
grid[i][j] 要么是 0 ，要么是 1 。

方法一：分情况讨论 · Go 实现

思考

选若干行使每列和不超过所选行数的一半。行数可达 $10^{4}$ ，列数不超过 $5$ ，枚举行子集不可行，但列掩码只有 $2^{n}$ 种。

分析可知可行子集大小只能是 $1$ 或 $2$ ：全零行单独成立；两行按位与为 $0$ 则每列至多一个 $1$ 。更大的偶数行数会在某列上堆出过多的 $1$ 。对每行压成掩码后检查这两种情形即可。

我们可以从小到大考虑答案选择的行数 $k$ 。

如果 $k = 1$ ，每一列的和最大为 $0$ ，那么必须满足有一行的所有元素都是 $0$ ，否则无法满足条件。
如果 $k = 2$ ，每一列的和最大为 $1$ ，那么必须存在有两行，且这两行的元素按位与之后的结果是 $0$ ，否则无法满足条件。
如果 $k = 3$ ，每一列的和最大也是 $1$ 。如果 $k = 2$ 不满足条件，那么 $k = 3$ 也一定不满足条件，所以我们不需要考虑所有 $k > 2$ 且 $k$ 为奇数的情况。
如果 $k = 4$ ，每一列的和最大为 $2$ ，此时一定是 $k = 2$ 不满足条件，也就是说，任意选取两行，都存在至少一个列的和为 $2$ 。我们在 $4$ 行中任意选取 $2$ 行，一共有 $C_{4}^{2} = 6$ 种选法，那么存在至少 $6$ 个 $2$ 的列。由于列数 $n \leq 5$ ，所以一定存在至少一列的和大于 $2$ ，所以 $k = 4$ 也不满足条件。
对于 $k > 4$ 且 $k$ 为偶数的情况，我们可以得出同样的结论，即 $k$ 一定不满足条件。

综上所述，我们只需要考虑 $k = 1$ 和 $k = 2$ 的情况即可。即判断是否有一行全为 $0$ ，或者是否存在两行按位与之后的结果为 $0$ 。

时间复杂度 $O (m \times n + 4^{n})$ ，空间复杂度 $O (2^{n})$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

func goodSubsetofBinaryMatrix(grid [][]int) []int {
	g := map[int]int{}
	for i, row := range grid {
		mask := 0
		for j, x := range row {
			mask |= x << j
		}
		if mask == 0 {
			return []int{i}
		}
		g[mask] = i
	}
	for a, i := range g {
		for b, j := range g {
			if a&b == 0 {
				return []int{min(i, j), max(i, j)}
			}
		}
	}
	return []int{}
}

力扣原题 · Doocs 题解来源

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

中等1 种解法

标签：位运算、脑筋急转弯、枚举

题目、示例与约束

给你两个整数：num1 和 num2 。

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= num1 <= 10⁹
-10⁹ <= num2 <= 10⁹

方法一：枚举 · Go 实现

思考

每次从 $n u m 1$ 减去 $2^{i} + n u m 2$ ，求最少次数使结果为 $0$ 。 $i$ 的范围大，搜索减数序列不可行。

若恰做 $k$ 次，则 $x = n u m 1 - k \cdot n u m 2$ 必须能写成 $k$ 个二的幂之和，即 $x \geq k$ 且 $x$ 的二进制中 $1$ 的个数不超过 $k$ 。 $k$ 从 $1$ 递增，一旦 $x < 0$ 即可停止。

如果我们操作了 $k$ 次，那么问题实际上就变成了：判断 $num1 - k \times num2$ 能否拆分成 $k$ 个 $2^{i}$ 之和。

我们不妨假设 $x = num1 - k \times num2$ ，接下来分类讨论：

如果 $x < 0$ ，那么 $x$ 无法拆分成 $k$ 个 $2^{i}$ 之和，因为 $2^{i} > 0$ ，显然无解；
如果 $x$ 的二进制表示中 $1$ 的个数大于 $k$ ，此时也是无解；
否则，对于当前 $k$ ，一定存在一个拆分方案。

因此，我们从 $1$ 开始枚举 $k$ ，一旦找到一个满足条件的 $k$ ，就可以直接返回答案。

时间复杂度 $O (\log x)$ ，空间复杂度 $O (1)$ 。

func makeTheIntegerZero(num1 int, num2 int) int {
	for k := 1; ; k++ {
		x := num1 - k*num2
		if x < 0 {
			break
		}
		if bits.OnesCount(uint(x)) <= k && k <= x {
			return k
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

2802. 找出第 K 个幸运数字 🔒

中等1 种解法

标签：位运算、数学、字符串

题目、示例与约束

我们知道 4 和 7 是幸运数字。同时，如果一个数字只包含幸运数字，那么它被称为幸运数字。

给定一个整数 k，返回第 k 个幸运数字，并将其表示为一个 字符串 。

示例 1：

输入：k = 4
输出："47"
解释：第一个幸运数字是 4，第二个是 7，第三个是 44，第四个是 47。

示例 2：

输入：k = 10
输出："477"
解释：按递增顺序列出的幸运数字为：
4, 7, 44, 47, 74, 77, 444, 447, 474, 477。 因此第10个幸运数字是477。

示例 3：

输入：k = 1000
输出："777747447"
解释：第 1000 个幸运数字是 777747447。

提示：

1 <= k <= 10⁹

方法一：数学 · Go 实现

思考

按从小到大依次生成幸运数直至第 $k$ 个，在 $k$ 很大时不可行。仅含 $4$ 与 $7$ 的 $n$ 位数恰有 $2^{n}$ 个，等价于把二进制位映射为这两种数字。先减去较短位数的个数以确定位数 $n$ ，再自高位根据 $k$ 是否落在长度为 $2^{n - 1}$ 的前一半决定写 $4$ 还是 $7$ 。

根据题目描述，一个幸运数只包含数字 $4$ 和 $7$ ，因此 $n$ 位幸运数的个数为 $2^{n}$ 。

我们初始化 $n = 1$ ，接下来循环判断 $k$ 是否大于 $2^{n}$ ，如果大于则将 $k$ 减去 $2^{n}$ ，同时 $n$ 加一，直到 $k$ 小于等于 $2^{n}$ 。此时，我们只需要找出 $n$ 位幸运数中的第 $k$ 个即可。

如果 $k$ 小于等于 $2^{n - 1}$ ，则第 $k$ 个幸运数的第一位为 $4$ ，否则第一位为 $7$ ，然后我们将 $k$ 减去 $2^{n - 1}$ ，继续判断第二位，直到 $n$ 位幸运数的所有位都判断完毕。

时间复杂度 $O (\log k)$ ，空间复杂度 $O (\log k)$ 。

func kthLuckyNumber(k int) string {
	n := 1
	for k > 1<<n {
		k -= 1 << n
		n++
	}
	ans := []byte{}
	for n > 0 {
		n--
		if k <= 1<<n {
			ans = append(ans, '4')
		} else {
			ans = append(ans, '7')
			k -= 1 << n
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

2857. 统计距离为 k 的点对

中等1 种解法

标签：位运算、数组、哈希表

题目、示例与约束

给你一个二维整数数组 coordinates 和一个整数 k ，其中 coordinates[i] = [x_i, y_i] 是第 i 个点在二维平面里的坐标。

我们定义两个点 (x₁, y₁) 和 (x₂, y₂) 的距离为 (x1 XOR x2) + (y1 XOR y2) ，XOR 指的是按位异或运算。

请你返回满足 i < j 且点 i 和点 j之间距离为 k 的点对数目。

示例 1：

输入：coordinates = [[1,2],[4,2],[1,3],[5,2]], k = 5
输出：2
解释：以下点对距离为 k ：
- (0, 1)：(1 XOR 4) + (2 XOR 2) = 5 。
- (2, 3)：(1 XOR 5) + (3 XOR 2) = 5 。

示例 2：

输入：coordinates = [[1,3],[1,3],[1,3],[1,3],[1,3]], k = 0
输出：10
解释：任何两个点之间的距离都为 0 ，所以总共有 10 组点对。

提示：

2 <= coordinates.length <= 50000
0 <= x_i, y_i <= 10⁶
0 <= k <= 100

方法一：哈希表 + 枚举 · Go 实现

思考

距离定义为横坐标异或与纵坐标异或之和等于 $k$ 。 $k \leq 100$ ，可枚举 $x$ 方向的异或值 $a$ ，则 $y$ 方向为 $k - a$ ，目标点由当前点异或还原。哈希表保存已扫过的点，按出现顺序配对以免重复。

我们可以用一个哈希表 $c n t$ 统计数组 $c o o r d i n a t e s$ 中每个点出现的次数。

接下来，我们枚举数组 $c o o r d i n a t e s$ 中的每个点 $(x_{2}, y_{2})$ ，由于 $k$ 的取值范围为 $[0, 100]$ ，而 $x_{1} \oplus x_{2}$ 或 $y_{1} \oplus y_{2}$ 的结果一定大于等于 $0$ ，因此我们可以在 $[0, . . k]$ 范围内枚举 $x_{1} \oplus x_{2}$ 的结果 $a$ ，那么 $y_{1} \oplus y_{2}$ 的结果就是 $b = k - a$ 。这样一来，我们就可以计算出 $x_{1}$ 和 $y_{1}$ 的值，将 $(x_{1}, y_{1})$ 出现的次数累加到答案中。

时间复杂度 $O (n \times k)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是数组 $c o o r d i n a t e s$ 的长度。

func countPairs(coordinates [][]int, k int) (ans int) {
	cnt := map[[2]int]int{}
	for _, c := range coordinates {
		x2, y2 := c[0], c[1]
		for a := 0; a <= k; a++ {
			b := k - a
			x1, y1 := a^x2, b^y2
			ans += cnt[[2]int{x1, y1}]
		}
		cnt[[2]int{x2, y2}]++
	}
	return
}

力扣原题 · Doocs 题解来源

2859. 计算 K 置位下标对应元素的和

简单1 种解法

标签：位运算、数组

题目、示例与约束

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

请你用整数形式返回 nums 中的特定元素之和，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。

整数的二进制表示中的 1 就是这个整数的置位。

例如，21 的二进制表示为 10101 ，其中有 3 个置位。

示例 1：

输入：nums = [5,10,1,5,2], k = 1
输出：13
解释：下标的二进制表示是： 
0 = 000₂
1 = 001₂
2 = 010₂
3 = 011₂
4 = 100₂下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。
因此，答案为 nums[1] + nums[2] + nums[4] = 13 。

示例 2：

输入：nums = [4,3,2,1], k = 2
输出：1
解释：下标的二进制表示是： 
0 = 00₂
1 = 01₂
2 = 10₂
3 = 11₂只有下标 3 的二进制表示中存在 k = 2 个置位。
因此，答案为 nums[3] = 1 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁵
0 <= k <= 10

方法一：模拟 · Go 实现

思考

$n$ 不大，直接判断每个下标的二进制 $1$ 的个数是否等于 $k$ 并累加对应元素即可。

我们直接遍历每个下标 $i$ ，判断其二进制表示中 $1$ 的个数是否等于 $k$ ，如果等于则将其对应的元素累加到答案 $a n s$ 中。

遍历结束后，返回答案即可。

时间复杂度 $O (n \times \log n)$ ，其中 $n$ 是数组 $n u m s$ 的长度。空间复杂度 $O (1)$ 。

func sumIndicesWithKSetBits(nums []int, k int) (ans int) {
	for i, x := range nums {
		if bits.OnesCount(uint(i)) == k {
			ans += x
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2869. 收集元素的最少操作次数

简单1 种解法

标签：位运算、数组、哈希表

题目、示例与约束

给你一个正整数数组 nums 和一个整数 k 。

一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。

请你返回收集元素 1, 2, ..., k 需要的 最少操作次数 。

示例 1：

输入：nums = [3,1,5,4,2], k = 2
输出：4
解释：4 次操作后，集合中的元素依次添加了 2 ，4 ，5 和 1 。此时集合中包含元素 1 和 2 ，所以答案为 4 。

示例 2：

输入：nums = [3,1,5,4,2], k = 5
输出：5
解释：5 次操作后，集合中的元素依次添加了 2 ，4 ，5 ，1 和 3 。此时集合中包含元素 1 到 5 ，所以答案为 5 。

示例 3：

输入：nums = [3,2,5,3,1], k = 3
输出：4
解释：4 次操作后，集合中的元素依次添加了 1 ，3 ，5 和 2 。此时集合中包含元素 1 到 3  ，所以答案为 4 。

提示：

1 <= nums.length <= 50
1 <= nums[i] <= nums.length
1 <= k <= nums.length
输入保证你可以收集到元素 1, 2, ..., k 。

方法一：逆序遍历 · Go 实现

思考

每次只能取数组末尾，故最少操作等于从右往左首次集齐 $1. . k$ 时所经过的长度。逆序扫描并用布尔数组去重，集齐 $k$ 个不同目标值时返回 $n - i$ 。

我们可以逆序遍历数组，每次遍历到的元素如果小于等于 $k$ ，且没有被添加过，就将其添加到集合中，直到集合中包含了元素 $1$ 到 $k$ 为止。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $n u m s$ 的长度。空间复杂度 $O (k)$ 。

func minOperations(nums []int, k int) int {
	isAdded := make([]bool, k)
	count := 0
	n := len(nums)
	for i := n - 1; ; i-- {
		if nums[i] > k || isAdded[nums[i]-1] {
			continue
		}
		isAdded[nums[i]-1] = true
		count++
		if count == k {
			return n - i
		}
	}
}

力扣原题 · Doocs 题解来源

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

简单1 种解法

标签：位运算、数组

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。让我们通过扩展标准的按位或来介绍 K-or 操作。在 K-or 操作中，如果在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值是 1 。

返回 nums 的 K-or 值。

示例 1：

输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：
用二进制表示 numbers：

Number	Bit 3	Bit 2	Bit 1	Bit 0
7	0	1	1	1
12	1	1	0	0
9	1	0	0	1
8	1	0	0	0
9	1	0	0	1
15	1	1	1	1
Result = 9	1	0	0	1

位 0 在 7, 9, 9, 15 中为 1。位 3 在 12, 9, 8, 9, 15 中为 1。 只有位 0 和 3 满足。结果是 (1001)₂ = 9。

示例 2：

输入：nums = [2,12,1,11,4,5], k = 6
输出：0
解释：没有位在所有 6 个数字中都为 1，如 k = 6 所需要的。所以，答案为 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³¹
1 <= k <= nums.length

方法一：枚举 · Go 实现

思考

K-or 在第 $i$ 位为 $1$ 当且仅当至少 $k$ 个数该位为 $1$ ，各位独立。 $n u m s [i] < 2^{31}$ ，枚举 $32$ 位即可。

对每一位统计 $1$ 的个数，达到 $k$ 则把该位置入答案。 $n \leq 50$ ，无需位运算加速以外的结构。

我们可以在 $[0, 32)$ 范围内枚举每一位 $i$ ，统计数组 $n u m s$ 有多少个数的第 $i$ 位为 $1$ ，记为 $c n t$ 。如果 $c n t \geq k$ ，那么我们就将 $2^{i}$ 次方加到答案中。

枚举结束后，返回答案即可。

时间复杂度 $O (n \times \log M)$ ，其中 $n$ 和 $M$ 分别是数组 $n u m s$ 的长度以及 $n u m s$ 的最大值。空间复杂度 $O (1)$ 。

func findKOr(nums []int, k int) (ans int) {
	for i := 0; i < 32; i++ {
		cnt := 0
		for _, x := range nums {
			cnt += (x >> i & 1)
		}
		if cnt >= k {
			ans |= 1 << i
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2980. 检查按位或是否存在尾随零

简单1 种解法

标签：位运算、数组

题目、示例与约束

给你一个 正整数 数组 nums 。

你需要检查是否可以从数组中选出 两个或更多 元素，满足这些元素的按位或运算（ OR）结果的二进制表示中至少存在一个尾随零。

例如，数字 5 的二进制表示是 "101"，不存在尾随零，而数字 4 的二进制表示是 "100"，存在两个尾随零。

如果可以选择两个或更多元素，其按位或运算结果存在尾随零，返回 true；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4,5]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110" ，存在一个尾随零。

示例 2：

输入：nums = [2,4,8,16]
输出：true
解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110"，存在一个尾随零。
其他按位或运算结果存在尾随零的可能选择方案包括：(2, 8), (2, 16), (4, 8), (4, 16), (8, 16), (2, 4, 8), (2, 4, 16), (2, 8, 16), (4, 8, 16), 以及 (2, 4, 8, 16) 。

示例 3：

输入：nums = [1,3,5,7,9]
输出：false
解释：不存在按位或运算结果存在尾随零的选择方案。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 100

方法一：统计偶数个数 · Go 实现

思考

按位或的末位为 $0$ 当且仅当参与的数末位均为 $0$ ，即都是偶数。至少选两个数，故存在两个偶数即可。 $n \leq 100$ ，统计偶数个数。

根据题意，我们可以知道，如果数组中存在两个或两个以上的元素，其按位或运算结果存在尾随零，那么数组中必然存在至少两个偶数。因此，我们可以统计数组中偶数的个数，如果偶数的个数大于等于 $2$ ，那么就返回 true，否则返回 false。

时间复杂度 $O (n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O (1)$ 。

func hasTrailingZeros(nums []int) bool {
	cnt := 0
	for _, x := range nums {
		cnt += (x&1 ^ 1)
	}
	return cnt >= 2
}

力扣原题 · Doocs 题解来源

2997. 使数组异或和等于 K 的最少操作次数

中等1 种解法

标签：位运算、数组

题目、示例与约束

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

你可以对数组执行以下操作 任意次 ：

选择数组里的任意一个元素，并将它的 二进制 表示翻转一个数位，翻转数位表示将 0 变成 1 或者将 1 变成 0 。

你的目标是让数组里所有元素的按位异或和得到 k ，请你返回达成这一目标的最少操作次数。

注意，你也可以将一个数的前导 0 翻转。比方说，数字 (101)₂ 翻转第四个数位，得到 (1101)₂ 。

示例 1：

输入：nums = [2,1,3,4], k = 1
输出：2
解释：我们可以执行以下操作：
- 选择下标为 2 的元素，也就是 3 == (011)₂ ，我们翻转第一个数位得到 (010)₂ == 2 。数组变为 [2,1,2,4] 。
- 选择下标为 0 的元素，也就是 2 == (010)₂ ，我们翻转第三个数位得到 (110)₂ == 6 。数组变为 [6,1,2,4] 。
最终数组的所有元素异或和为 (6 XOR 1 XOR 2 XOR 4) == 1 == k 。
无法用少于 2 次操作得到异或和等于 k 。

示例 2：

输入：nums = [2,0,2,0], k = 0
输出：0
解释：数组所有元素的异或和为 (2 XOR 0 XOR 2 XOR 0) == 0 == k 。所以不需要进行任何操作。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶
0 <= k <= 10⁶

方法一：位运算 · Go 实现

思考

一次操作翻转某个数的某一位，等价于翻转全体异或的同一位。最少次数即 $n u m s$ 的异或与 $k$ 的汉明距离。

把 $k$ 一并异或后统计 $1$ 的位数。 $n \leq 10^{5}$ ，一次归约即可。

我们可以将数组 $n u m s$ 中的所有元素进行异或运算，判断得到的结果与 $k$ 的二进制表示中有多少位不同，这个数就是最少操作次数。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $n u m s$ 的长度。空间复杂度 $O (1)$ 。

func minOperations(nums []int, k int) (ans int) {
	for _, x := range nums {
		k ^= x
	}
	return bits.OnesCount(uint(k))
}

力扣原题 · Doocs 题解来源

3011. 判断一个数组是否可以变为有序

中等1 种解法

标签：位运算、数组、排序

题目、示例与约束

给你一个下标从 0 开始且全是正整数的数组 nums 。

一次操作中，如果两个相邻元素在二进制下设置位的数目相同，那么你可以将这两个元素交换。你可以执行这个操作 任意次 （也可以 0 次）。

如果你可以使数组变为非降序，请你返回 true ，否则返回 false 。

示例 1：

输入：nums = [8,4,2,30,15]
输出：true
解释：我们先观察每个元素的二进制表示。 2 ，4 和 8 分别都只有一个数位为 1 ，分别为 "10" ，"100" 和 "1000" 。15 和 30 分别有 4 个数位为 1 ："1111" 和 "11110" 。
我们可以通过 4 个操作使数组非降序：
- 交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。
- 交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。
- 交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。
- 交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 ，数组变为 [2,4,8,15,30] 。
数组变成有序的，所以我们返回 true 。
注意我们还可以通过其他的操作序列使数组变得有序。

示例 2：

输入：nums = [1,2,3,4,5]
输出：true
解释：数组已经是非降序的，所以我们返回 true 。

示例 3：

输入：nums = [3,16,8,4,2]
输出：false
解释：无法通过操作使数组变为非降序。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 2⁸

方法一：双指针 · Go 实现

思考

$n \leq 100$ ，可交换的充要条件是两点的二进制中 $1$ 的个数相同。按位计数分段后，段内可任意重排。

全局有序当且仅当各段排序后能够首尾相接，即本段最小值不小于上一段最大值。

双指针按 $popcount$ 切段，记录每段最值并与前一段最大值比较。

我们可以使用双指针，将数组 $nums$ 分成若干个子数组，每个子数组中的元素的二进制表示中 $1$ 的个数相同。对于每个子数组，我们只需要关注它的最大值和最小值，如果最小值比上一个子数组的最大值小，那么就无法通过交换使得数组有序。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O (1)$ 。

func canSortArray(nums []int) bool {
	preMx := 0
	i, n := 0, len(nums)
	for i < n {
		cnt := bits.OnesCount(uint(nums[i]))
		j := i + 1
		mi, mx := nums[i], nums[i]
		for j < n && bits.OnesCount(uint(nums[j])) == cnt {
			mi = min(mi, nums[j])
			mx = max(mx, nums[j])
			j++
		}
		if preMx > mi {
			return false
		}
		preMx = mx
		i = j
	}
	return true
}

力扣原题 · Doocs 题解来源

3064. 使用按位查询猜测数字 I 🔒

中等1 种解法

标签：位运算、交互

题目、示例与约束

你需要找到一个数字 n。

这里有一个预定义的 API int commonSetBits(int num)，它返回 n 和 num 在二进制表示的同一位置上都是 1 的位数。换句话说，它返回 n & num 的设置位数量，其中 & 是按位 AND 运算符。

返回数字 n。

示例 1：

输入：n = 31

输出：31

解释：能够证明使用给定的 API 找到 31 是可能的。

示例 2：

输入：n = 33

输出：33

解释：能够证明使用给定的 API 找到 33 是可能的。

提示：

1 <= n <= 2³⁰ - 1
0 <= num <= 2³⁰ - 1
如果你查询的 num 超出了给定的范围，输出就不可靠。

方法一：枚举 · Go 实现

思考

$commonSetBits (x)$ 返回 $n$ 与 $x$ 的公共 $1$ 位数。 $n < 2^{30}$ ，可逐位询问。

对 $x = 2^{i}$ ，返回值非零当且仅当 $n$ 的第 $i$ 位为 $1$ 。

枚举 $32$ 位，把询问为真的位或进答案。

我们可以枚举 $2$ 的幂次方，然后调用 commonSetBits 方法，如果返回值大于 $0$ ，则说明 $n$ 的二进制表示中的对应位是 $1$ 。

时间复杂度 $O (\log n)$ ，本题中 $n \leq 2^{30}$ 。空间复杂度 $O (1)$ 。

/**
 * Definition of commonSetBits API.
 * func commonSetBits(num int) int;
 */

func findNumber() (n int) {
	for i := 0; i < 32; i++ {
		if commonSetBits(1<<i) > 0 {
			n |= 1 << i
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3094. 使用按位查询猜测数字 II 🔒

中等1 种解法

标签：位运算、交互

题目、示例与约束

你需要找到一个在 0 和 2³⁰ - 1 （均包含）之间的数字 n。

有一个预定义的 API int commonBits(int num) 能帮助你完成任务。但挑战是每次你调用这个函数，n 都会以某种方式改变。但是记住，你需要找到的是 n 的 初始值。

commonBits(int num) 的操作如下：

计算 n 和 num 的二进制表示中值相同的二进制位的位的数量 count。
n = n XOR num
返回 count。

返回数字 n。

注意：在这个世界中，所有数字都在 0 和 2³⁰ - 1 之间（均包含），因此在计算公共二进制位时，我们只看那些数字的前 30 个二进制位。

提示：

0 <= n <= 2³⁰ - 1
0 <= num <= 2³⁰ - 1
如果你查询的 num 超出了给定的范围，输出将会是不可靠的。

方法一：位运算 · Go 实现

思考

$commonBits (x)$ 先把 $n$ 异或上 $x$ ，再返回与 $n$ 的公共 $1$ 个数。每次询问会永久改写 $n$ 。

对同一 $x$ 询问两次，第二次把 $n$ 变回原值。比较两次返回值可知该位在异或前是否为 $1$ ：先变大说明原来是 $1$ 。

对每一位询问 $1 ≪ i$ 两次，按两次计数的大小关系置位。

根据题目描述，我们观察到：

如果我们对同一个数调用两次 commonBits 函数，那么 $n$ 的值将不会发生变化。
如果我们调用 commonBits(1 << i)，那么 $n$ 的第 $i$ 位将会被翻转，即 $n$ 的第 $i$ 位为 $1$ 时，调用后变为 $0$ ，反之亦然。

因此，对于每一位 $i$ ，我们可以调用 commonBits(1 << i) 两次，分别记为 count1 和 count2，如果 count1 > count2，那么说明 $n$ 的第 $i$ 位为 $1$ ，否则为 $0$ 。

时间复杂度 $O (\log n)$ ，空间复杂度 $O (1)$ 。

/**
 * Definition of commonBits API.
 * func commonBits(num int) int;
 */

func findNumber() (n int) {
	for i := 0; i < 32; i++ {
		count1 := commonBits(1 << i)
		count2 := commonBits(1 << i)
		if count1 > count2 {
			n |= 1 << i
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3133. 数组最后一个元素的最小值

中等1 种解法

标签：位运算

题目、示例与约束

给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。

返回 nums[n - 1] 可能的最小值。

示例 1：

输入：n = 3, x = 4

输出：6

解释：

数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。

示例 2：

输入：n = 2, x = 7

输出：15

解释：

数组 nums 可以是 [7,15] ，最后一个元素为 15 。

提示：

1 <= n, x <= 10⁸

方法一：贪心 + 位运算 · Go 实现

思考

构造长为 $n$ 的严格递增正整数列，使全体按位与为 $x$ ，并最小化末项。从 $x$ 起逐个试下一个候选会在 $n$ 很大时过慢。

第一项必须是 $x$ ，其后各项只能在 $x$ 的零位上填入递增二进制，才能保持与值仍为 $x$ 。忽略这些被占用的一位后，序列恰为 $0, 1, 2, \dots, n - 1$ 。

因此把 $n - 1$ 的各位依次写入 $x$ 的空位（低位优先），更高位整体接到第 $31$ 位之上。得到的数即为最小末项。

根据题目描述，要使得数组的最后一个元素尽可能小，且数组中的元素按位与的结果为 $x$ ，那么数组的第一个元素必须为 $x$ 。

假设 $x$ 的二进制表示为 $\underset{―}{1} 00 \underset{―}{1} 00$ ，那么数组序列为 $\underset{―}{1} 00 \underset{―}{1} 00$ , $\underset{―}{1} 00 \underset{―}{1} 01$ , $\underset{―}{1} 00 \underset{―}{1} 10$ , $\underset{―}{1} 00 \underset{―}{1} 11$ ...

如果我们忽略掉下划线部分，那么数组序列为 $0000$ , $0001$ , $0010$ , $0011$ ...，第一项为 $0$ ，那么第 $n$ 项为 $n - 1$ 。

因此，答案就是在 $x$ 的基础上，将 $n - 1$ 的二进制的每一位依次填入 $x$ 的二进制中的 $0$ 位。

时间复杂度 $O (\log x)$ ，空间复杂度 $O (1)$ 。

func minEnd(n int, x int) (ans int64) {
	n--
	ans = int64(x)
	for i := 0; i < 31; i++ {
		if x>>i&1 == 0 {
			ans |= int64((n & 1) << i)
			n >>= 1
		}
	}
	ans |= int64(n) << 31
	return
}

力扣原题 · Doocs 题解来源

3158. 求出出现两次数字的 XOR 值

简单2 种解法

标签：位运算、数组、哈希表

题目、示例与约束

给你一个数组 nums ，数组中的数字要么出现一次，要么出现两次。

请你返回数组中所有出现两次数字的按位 XOR 值，如果没有数字出现过两次，返回 0 。

示例 1：

输入：nums = [1,2,1,3]

输出：1

解释：

nums 中唯一出现过两次的数字是 1 。

示例 2：

输入：nums = [1,2,3]

输出：0

解释：

nums 中没有数字出现两次。

示例 3：

输入：nums = [1,2,2,1]

输出：3

解释：

数字 1 和 2 出现过两次。1 XOR 2 == 3 。

提示：

1 <= nums.length <= 50
1 <= nums[i] <= 50
nums 中每个数字要么出现过一次，要么出现过两次。

方法一：计数 · Go 实现

思考

只把出现恰好两次的数异或起来。值域很小，计数后筛选即可。

一次遍历统计频次，再把频次为 $2$ 的键异或。空则得到 $0$ 。

用 Counter 后 reduce(xor, ...) 得到答案，时间为线性。

我们定义一个数组或哈希表 $cnt$ 记录每个数字出现的次数。

接下来，遍历数组 $nums$ ，当某个数字出现两次时，我们将其与答案进行异或运算。

最后返回答案即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (M)$ 。其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值或数组 $nums$ 不同数字的个数。

func duplicateNumbersXOR(nums []int) (ans int) {
	cnt := [51]int{}
	for _, x := range nums {
		cnt[x]++
		if cnt[x] == 2 {
			ans ^= x
		}
	}
	return
}

方法二：位运算 · Go 实现

思考

方法一使用哈希表，在 $1 \leq n u m s [i] \leq 50$ 时空间可再压到常数。

一个 $64$ 位掩码足以标记每个值是否出现过；第二次见到便异或进答案。

遍历时若 $m a s k$ 第 $x$ 位已立则 $a n s \oplus = x$ ，否则置位。无需额外数组。

由于题目中给出的数字范围是 $1 \leq nums [i] \leq 50$ ，我们可以使用一个 $64$ 位的整数来存储每个数字的出现次数。

我们定义一个整数 $mask$ 来记录每个数字是否出现过。

接下来，遍历数组 $nums$ ，当某个数字出现两次时，即 $mask$ 的二进制表示中第 $x$ 位为 $1$ 时，我们将其与答案进行异或运算。否则，我们将 $mask$ 的第 $x$ 位设置为 $1$ 。

最后返回答案即可。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O (1)$ 。

func duplicateNumbersXOR(nums []int) (ans int) {
	mask := 0
	for _, x := range nums {
		if mask>>x&1 == 1 {
			ans ^= x
		} else {
			mask |= 1 << x
		}
	}
	return
}

力扣原题 · Doocs 题解来源

3173. 相邻元素的按位或 🔒

简单1 种解法

标签：位运算、数组

题目、示例与约束

给定一个长度为 n 的数组 nums，返回一个长度为 n - 1 的数组 answer 使得 answer[i] = nums[i] | nums[i + 1]，其中 | 表示按位 OR 操作。

示例 1：

输入：nums = [1,3,7,15]

输出：[3,7,15]

示例 2：

输入：nums = [8,4,2]

输出：[12,6]

示例 3：

输入：nums = [5,4,9,11]

输出：[5,13,11]

提示：

2 <= nums.length <= 100
0 <= nums[i] <= 100

方法一：遍历 · Go 实现

思考

答案第 $i$ 位定义为 $n u m s [i] \lor n u m s [i + 1]$ ，与更远元素无关。

一对一对计算即可，无需前缀或。

对 pairwise(nums) 取或，得到长 $n - 1$ 的数组。

我们遍历数组的前 $n - 1$ 个元素，对于每个元素，计算它和它的下一个元素的按位或值，将结果存入答案数组中。

时间复杂度 $O (n)$ ，其中 $n$ 是数组的长度。忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

func orArray(nums []int) (ans []int) {
	for i, x := range nums[1:] {
		ans = append(ans, x|nums[i])
	}
	return
}

力扣原题 · Doocs 题解来源

3199. 用偶数异或设置位计数三元组 I 🔒

简单1 种解法

标签：位运算、数组

题目、示例与约束

给定三个整数数组 a，b 和 c，返回组内元素按位 XOR 有偶数个设置位的三元组 (a[i], b[j], c[k]) 的数量。

示例 1:

输入：a = [1], b = [2], c = [3]

输出：1

解释：

只有一个三元组 (a[0], b[0], c[0]) 并且它们的 XOR 为：1 XOR 2 XOR 3 = 00₂。

示例 2:

输入：a = [1,1], b = [2,3], c = [1,5]

输出：4

解释：

考虑以下 4 个三元组：

(a[0], b[1], c[0]): 1 XOR 3 XOR 1 = 011₂
(a[1], b[1], c[0]): 1 XOR 3 XOR 1 = 011₂
(a[0], b[0], c[1]): 1 XOR 2 XOR 5 = 110₂
(a[1], b[0], c[1]): 1 XOR 2 XOR 5 = 110₂

提示：

1 <= a.length, b.length, c.length <= 100
0 <= a[i], b[i], c[i] <= 100

方法一：位运算 · Go 实现

思考

统计 $a_{i} \oplus b_{j} \oplus c_{k}$ 的置位数为偶数的三元组。三重循环在长度同为 $n$ 时是 $O (n^{3})$ 。

异或的置位数奇偶等于三个数各自置位数奇偶之和的奇偶，只需 $0 / 1$ 两个桶。

分别统计三个数组的 $b i t_c o u n t mod 2$ ，再枚举 $i, j, k \in {0, 1}$ ，当 $i + j + k$ 为偶数时累加桶的乘积。

对于两个整数，异或结果中 $1$ 的个数的奇偶性，取决于两个整数的二进制表示中 $1$ 的个数的奇偶性。

我们可以用三个数组 cnt1、cnt2、cnt3 分别记录数组 a、b、c 中每个数的二进制表示中 $1$ 的个数的奇偶性。

然后我们在 $[0, 1]$ 的范围内枚举三个数组中的每个数的二进制表示中 $1$ 的个数的奇偶性，如果三个数的二进制表示中 $1$ 的个数的奇偶性之和为偶数，那么这三个数的异或结果中 $1$ 的个数也为偶数，此时我们将这三个数的组合数相乘累加到答案中。

最后返回答案即可。

时间复杂度 $O (n)$ ，其中 $n$ 为数组 a、b、c 的长度。空间复杂度 $O (1)$ 。

func tripletCount(a []int, b []int, c []int) (ans int) {
	cnt1 := [2]int{}
	cnt2 := [2]int{}
	cnt3 := [2]int{}
	for _, x := range a {
		cnt1[bits.OnesCount(uint(x))%2]++
	}
	for _, x := range b {
		cnt2[bits.OnesCount(uint(x))%2]++
	}
	for _, x := range c {
		cnt3[bits.OnesCount(uint(x))%2]++
	}
	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			for k := 0; k < 2; k++ {
				if (i+j+k)%2 == 0 {
					ans += cnt1[i] * cnt2[j] * cnt3[k]
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

LeetCode Go · 位运算（3） ​

2419. 按位与最大的最长子数组 ​

2425. 所有数对的异或和 ​

2433. 找出前缀异或的原始数组 ​

2438. 二的幂数组中查询范围内的乘积 ​

2505. 所有子序列和的按位或 🔒 ​

2506. 统计相似字符串对的数目 ​

2527. 查询数组异或美丽值 ​

2546. 执行逐位运算使字符串相等 ​

2564. 子字符串异或查询 ​

2568. 最小无法得到的或值 ​

2588. 统计美丽子数组数目 ​

2595. 奇偶位数 ​

2657. 找到两个数组的前缀公共数组 ​

2683. 相邻值的按位异或 ​

2732. 找到矩阵中的好子集 ​

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

2802. 找出第 K 个幸运数字 🔒 ​

2857. 统计距离为 k 的点对 ​

2859. 计算 K 置位下标对应元素的和 ​

2869. 收集元素的最少操作次数 ​

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

2980. 检查按位或是否存在尾随零 ​

2997. 使数组异或和等于 K 的最少操作次数 ​

3011. 判断一个数组是否可以变为有序 ​

3064. 使用按位查询猜测数字 I 🔒 ​

3094. 使用按位查询猜测数字 II 🔒 ​

3133. 数组最后一个元素的最小值 ​

3158. 求出出现两次数字的 XOR 值 ​

3173. 相邻元素的按位或 🔒 ​

3199. 用偶数异或设置位计数三元组 I 🔒 ​

继续阅读

LeetCode Go · 位运算（3）

2419. 按位与最大的最长子数组

2425. 所有数对的异或和

2433. 找出前缀异或的原始数组

2438. 二的幂数组中查询范围内的乘积

2505. 所有子序列和的按位或 🔒

2506. 统计相似字符串对的数目

2527. 查询数组异或美丽值

2546. 执行逐位运算使字符串相等

2564. 子字符串异或查询

2568. 最小无法得到的或值

2588. 统计美丽子数组数目

2595. 奇偶位数

2657. 找到两个数组的前缀公共数组

2683. 相邻值的按位异或

2732. 找到矩阵中的好子集

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

2802. 找出第 K 个幸运数字 🔒

2857. 统计距离为 k 的点对

2859. 计算 K 置位下标对应元素的和

2869. 收集元素的最少操作次数

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

2980. 检查按位或是否存在尾随零

2997. 使数组异或和等于 K 的最少操作次数

3011. 判断一个数组是否可以变为有序

3064. 使用按位查询猜测数字 I 🔒

3094. 使用按位查询猜测数字 II 🔒

3133. 数组最后一个元素的最小值

3158. 求出出现两次数字的 XOR 值

3173. 相邻元素的按位或 🔒

3199. 用偶数异或设置位计数三元组 I 🔒