LeetCode Go · 位运算（1）

返回题库与筛选 · 收录范围与使用说明

来源与许可

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

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

29. 两数相除

中等1 种解法

标签：位运算、数学

题目、示例与约束

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的 商 。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231,  231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。

 

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333.. ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。

 

提示：

• -231 <= dividend, divisor <= 231 - 1
• divisor != 0

方法一：模拟 + 快速幂 · Go 实现

思考

除法可以看成反复减法，但若每次只从被除数中减去 $1$ 倍除数、商加 $1$，当 $|a|$ 接近 $2^{31}$ 时循环次数过大，无法通过。题目同时禁止乘法、除法与取余运算。

在剩余量仍够的前提下将除数不断左移加倍，即可一次扣掉 $2^k$ 倍，商按二进制累加。这与快速幂的思想一致。左移时还需防止溢出：若再翻倍会超出 $32$ 位范围，则停止倍增。

注意到环境只能存储 $32$ 位有符号整数，将负数取相反数可能溢出（例如 $a=-2^{31}$）。因此符号单独记录，运算全程在负数上进行；并特判 $b=1$，以及 $a=-2^{31}$ 且 $b=-1$ 时返回 $2^{31}-1$。

除法本质上就是减法，题目要求我们计算出两个数相除之后的取整结果，其实就是计算被除数是多少个除数加上一个小于除数的数构成的。但是一次循环只能做一次减法，效率太低会导致超时，可借助快速幂的思想进行优化。

需要注意的是，由于题目明确要求最大只能使用 32 位有符号整数，所以需要将除数和被除数同时转换为负数进行计算。因为转换正数可能会导致溢出，如当被除数为 INT32_MIN 时，转换为正数时会大于 INT32_MAX。

假设被除数为 $a$，除数为 $b$，则时间复杂度为 $O(\log a\times \log b)$，空间复杂度 $O(1)$。

func divide(a int, b int) int {
	if b == 1 {
		return a
	}
	if a == math.MinInt32 && b == -1 {
		return math.MaxInt32
	}

	sign := (a > 0 && b > 0) || (a < 0 && b < 0)
	if a > 0 {
		a = -a
	}
	if b > 0 {
		b = -b
	}
	ans := 0

	for a <= b {
		x := b
		cnt := 1
		for x >= (math.MinInt32>>1) && a <= (x<<1) {
			x <<= 1
			cnt <<= 1
		}
		ans += cnt
		a -= x
	}

	if sign {
		return ans
	}
	return -ans
}

力扣原题 · Doocs 题解来源

67. 二进制求和

简单1 种解法

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

题目、示例与约束

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

 

示例 1：

输入:a = "11", b = "1"
输出："100"

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

 

提示：

• 1 <= a.length, b.length <= 104
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0" ，就不含前导零

方法一：模拟 · Go 实现

思考

二进制串长度可达 ${10}^4$，不能转换成普通整数再相加。

两串长度可能不同，最高位仍可能再产生进位，这与十进制竖式相同。为此从低位对齐向高位累加，用 $\mathit{\text{carry}}$ 记录进位；两个指针自末尾同步前移，缺位视为 $0$，循环条件同时包含 $\mathit{\text{carry}}$，使最后多出的进位也会写入答案。

我们用一个变量 $\mathit{\text{carry}}$ 记录当前的进位，用两个指针 $i$ 和 $j$ 分别指向 $a$ 和 $b$ 的末尾，从末尾到开头逐位相加即可。

时间复杂度 $O(max(m,n))$，其中 $m$ 和 $n$ 分别为字符串 $a$ 和 $b$ 的长度。空间复杂度 $O(max(m,n))$。

func addBinary(a string, b string) string {
	i, j := len(a)-1, len(b)-1
	ans := []byte{}
	for carry := 0; i >= 0 || j >= 0 || carry > 0; i, j = i-1, j-1 {
		if i >= 0 {
			carry += int(a[i] - '0')
		}
		if j >= 0 {
			carry += int(b[j] - '0')
		}
		ans = append(ans, byte(carry%2+'0'))
		carry /= 2
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

136. 只出现一次的数字

简单1 种解法

标签：位运算、数组

题目、示例与约束

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

 

示例 1 ：

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

输出：1

示例 2 ：

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

输出：4

示例 3 ：

输入：nums = [1]

输出：1

 

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

方法一：位运算 · Go 实现

思考

其余数出现两次、一个出现一次，要求线性时间、常数空间。哈希计数空间是 $O(n)$。异或满足 $x\oplus x=0$、 $x\oplus 0=x$ 且可交换，全部异或后成对的数消掉，剩下即只出现一次的那个。

异或运算的性质：

• 任何数和 $0$ 做异或运算，结果仍然是原来的数，即 $x\oplus 0=x$；
• 任何数和其自身做异或运算，结果是 $0$，即 $x\oplus x=0$；

我们对该数组所有元素进行异或运算，结果就是那个只出现一次的数字。

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

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

力扣原题 · Doocs 题解来源

137. 只出现一次的数字 II

中等2 种解法

标签：位运算、数组

题目、示例与约束

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

 

示例 1：

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

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

 

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

方法一：位运算 · Go 实现

思考

其余数出现三次、一个出现一次，异或不再直接可用，因为 $x\oplus x\oplus x=x$。进阶仍要常数空间。按位统计 $1$ 的个数再模 $3$，出现三次的位被清掉，余数即答案对应位。符号位单独处理以免溢出。

我们可以枚举每个二进制位 $i$，对于每个二进制位，我们统计所有数字在该二进制位上的和，如果该二进制位上的和能被 $3$ 整除，那么只出现一次的数字在该二进制位上为 $0$，否则为 $1$。

时间复杂度 $O(n\times \log M)$，空间复杂度 $O(1)$。其中 $n$ 和 $M$ 分别是数组的长度和数组中元素的范围。

C++ 在处理符号位时直接加上 INT_MIN，避免对有符号整数进行可能溢出的左移。

func singleNumber(nums []int) int {
	ans := int32(0)
	for i := 0; i < 32; i++ {
		cnt := int32(0)
		for _, num := range nums {
			cnt += int32(num) >> i & 1
		}
		cnt %= 3
		ans |= cnt << i
	}
	return int(ans)
}

方法二：数字电路 · Go 实现

思考

方法一对每个位扫描整数组。用两个整数 $a,b$ 按位表示「该位出现次数模 $3$」，读入下一个数时按真值表更新，一遍扫描完成同样的模 $3$ 计数。

我们考虑一种更高效的方法，该方法使用数字电路来模拟上述的位运算。

一个整数的每个二进制位是 $0$ 或 $1$，只能表示 $2$ 种状态。但我们需要表示当前遍历过的所有整数的第 $i$ 位之和模 $3$ 的结果，因此，我们可以使用 $a$ 和 $b$ 两个整数来表示。那么会有以下三种情况：

1. 整数 $a$ 的第 $i$ 位为 $0$ 且整数 $b$ 的第 $i$ 位为 $0$，表示模 $3$ 结果是 $0$；
2. 整数 $a$ 的第 $i$ 位为 $0$ 且整数 $b$ 的第 $i$ 位为 $1$，表示模 $3$ 结果是 $1$；
3. 整数 $a$ 的第 $i$ 位为 $1$ 且整数 $b$ 的第 $i$ 位为 $0$，表示模 $3$ 结果是 $2$。

我们用整数 $c$ 表示当前要读入的数，那么有以下真值表：

$a_i$	$b_i$	$c_i$	新的 $a_i$	新的 $b_i$
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	0	0

基于以上真值表，我们可以写出逻辑表达式：

$$a_i=a_i^{\prime }{b}_i{c}_i+a_i{b}_i^{\prime }{c}_i^{\prime }$$

以及：

$$b_i=a_i^{\prime }{b}_i^{\prime }{c}_i+a_i^{\prime }{b}_i{c}_i^{\prime }=a_i^{\prime }(b_i\oplus c_i)$$

最后结果是 $b$，因为 $b$ 的二进制位上为 $1$ 时表示这个数字出现了 $1$ 次。

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

func singleNumber(nums []int) int {
	a, b := 0, 0
	for _, c := range nums {
		aa := (^a & b & c) | (a & ^b & ^c)
		bb := ^a & (b ^ c)
		a, b = aa, bb
	}
	return b
}

力扣原题 · Doocs 题解来源

190. 颠倒二进制位

简单1 种解法

标签：位运算、分治

题目、示例与约束

颠倒给定的 32 位有符号整数的二进制位。

 

示例 1：

输入：n = 43261596

输出：964176192

解释：

整数	二进制
43261596	00000010100101000001111010011100
964176192	00111001011110000010100101000000

示例 2：

输入：n = 2147483644

输出：1073741822

解释：

整数	二进制
2147483644	01111111111111111111111111111100
1073741822	00111111111111111111111111111110

 

提示：

• 0 <= n <= 231 - 2
• n 为偶数

 

进阶: 如果多次调用这个函数，你将如何优化你的算法？

方法一：位运算 · Go 实现

思考

把 $32$ 位无符号整数的比特左右对调。可以按位取出再放到对称位置。从低到高扫 $32$ 次：取出 $n$ 的最低位，写入答案的 $31-i$ 位，然后 $n$ 右移。位数固定，时间常数。

我们可以从低位到高位，逐个取出 $n$ 的每一位，然后将其放到 $\mathit{\text{ans}}$ 的对应位置上。

比如，对于第 $i$ 位，我们可以通过 $(n\mathrm{\&}1)\ll (31-i)$ 来取出 $n$ 的第 $i$ 位，并将其放到 $\mathit{\text{ans}}$ 的第 $31-i$ 位上，然后将 $n$ 右移一位。

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

func reverseBits(n uint32) (ans uint32) {
	for i := 0; i < 32; i++ {
		ans |= (n & 1) << (31 - i)
		n >>= 1
	}
	return
}

力扣原题 · Doocs 题解来源

191. 位1的个数

简单2 种解法

标签：位运算、分治

题目、示例与约束

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

 

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

 

提示：

• 1 <= n <= 231 - 1

 

进阶：

• 如果多次调用这个函数，你将如何优化你的算法？

方法一：位运算 · Go 实现

思考

统计二进制中 $1$ 的个数。逐位检查要看满 $32$ 位。 $n\mathrm{\&}(n-1)$ 会清掉最低的 $1$，循环次数等于 $1$ 的个数，比固定 $32$ 次更省。

利用 n & (n - 1) 消除 n 中最后一位 1 这一特点，优化过程：

HAMMING-WEIGHT(n)
    r = 0
    while n != 0
        n &= n - 1
        r += 1
    r

以 5 为例，演示推演过程：

[0, 1, 0, 1] // 5
[0, 1, 0, 0] // 5 - 1 = 4
[0, 1, 0, 0] // 5 & 4 = 4

[0, 1, 0, 0] // 4
[0, 0, 1, 1] // 4 - 1 = 3
[0, 0, 0, 0] // 4 & 3 = 0

func hammingWeight(num uint32) int {
	ans := 0
	for num != 0 {
		num &= num - 1
		ans++
	}
	return ans
}

方法二：lowbit · Go 实现

思考

方法一用 $n\mathrm{\&}(n-1)$。 $\mathit{\text{lowbit}}=n\mathrm{\&}-n$ 同样取出最低的 $1$，减去它再循环，语义等价，便于和树状数组那套位运算对应。

x -= (x & -x) 可以消除二进制形式的最后一位 1。

同 剑指 Offer 15. 二进制中 1 的个数

func hammingWeight(num uint32) int {
	ans := 0
	for num != 0 {
		num -= (num & -num)
		ans++
	}
	return ans
}

力扣原题 · Doocs 题解来源

201. 数字范围按位与

中等1 种解法

标签：位运算

题目、示例与约束

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

 

示例 1：

输入：left = 5, right = 7
输出：4

示例 2：

输入：left = 0, right = 0
输出：0

示例 3：

输入：left = 1, right = 2147483647
输出：0

 

提示：

• 0 <= left <= right <= 231 - 1

方法一：位运算 · Go 实现

思考

将 $[left,right]$ 中每个整数依次做按位与，在 $right-left$ 接近 $2^{31}$ 时不可行。连续整数的按位与等于它们的公共二进制前缀：更低的位会在某个数上被清零。

为此当 $left<right$ 时，反复将 $right$ 的最低位 $1$ 清掉（即 $right\mathrm{\&}=right-1$），直到 $right\le left$。此时 $right$ 即为该公共前缀。

题目可以转换为求数字的公共二进制前缀。

当 $left<right$ 时，我们循环将 $right$ 的最后一个二进制位 $1$ 变成 $0$，直到 $left=right$，此时 $right$ 即为数字的公共二进制前缀，返回 $right$ 即可。

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

func rangeBitwiseAnd(left int, right int) int {
	for left < right {
		right &= (right - 1)
	}
	return right
}

力扣原题 · Doocs 题解来源

231. 2 的幂

简单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

 

提示：

• -231 <= n <= 231 - 1

 

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

方法一：位运算 · Go 实现

思考

循环除以 $2$ 可判定，但位运算一步即可。2 的幂在二进制中恰有一个 $1$，因此 $n>0$ 且 $n\mathrm{\&}(n-1)=0$。

根据位运算的性质，执行 $\mathtt{\text{n\&(n-1)}}$ 可以消去二进制形式的 $n$ 的最后一位 $1$。因此，如果 $n>0$，并且满足 $\mathtt{\text{n\&(n-1)}}$ 结果为 $0$，则说明 $n$ 是 $2$ 的幂。

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

func isPowerOfTwo(n int) bool {
	return n > 0 && (n&(n-1)) == 0
}

方法二：Lowbit · Go 实现

思考

消去最低位 $1$ 与取 $\mathrm{lowbit}$ 等价。若 $n>0$ 且 $n=n\mathrm{\&}(-n)$，则 $n$ 只有这一位 $1$，同为 2 的幂。

根据 $\text{lowbit}$ 的定义，我们知道 $\text{lowbit}(x)=x\mathrm{\&}(-x)$，可以得到 $n$ 的最后一位 $1$ 表示的十进制数。因此，如果 $n>0$，并且满足 $\text{lowbit}(n)$ 等于 $n$，则说明 $n$ 是 $2$ 的幂。

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

func isPowerOfTwo(n int) bool {
	return n > 0 && n == (n&(-n))
}

力扣原题 · Doocs 题解来源

260. 只出现一次的数字 III

中等1 种解法

标签：位运算、数组

题目、示例与约束

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

 

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

 

提示：

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

方法一：位运算 · Go 实现

思考

除两个数各出现一次外其余均出现两次，全部异或得到的是这两个数之异或 $xs$。二者不等，故 $xs$ 至少有一位为 $1$。

取 $xs$ 的 $\mathrm{lowbit}$ 按该位分组，两个目标数落入不同组；对含该位的一组再异或得到 $a$，则 $b=xs\oplus a$。

异或运算有以下性质：

• 任何数和 $0$ 做异或运算，结果仍然是原来的数，即 $x\oplus 0=x$；
• 任何数和其自身做异或运算，结果是 $0$，即 $x\oplus x=0$；

由于数组中除了两个数字之外，其他数字都出现了两次，因此我们对数组中的所有数字进行异或运算，得到的结果即为两个只出现一次的数字的异或结果。

而由于这两个数字不相等，因此异或结果中至少存在一位为 $1$。我们可以通过 lowbit 运算找到异或结果中最低位的 $1$，并将数组中的所有数字按照该位是否为 $1$ 分为两组，这样两个只出现一次的数字就被分到了不同的组中。

对两个组分别进行异或运算，即可得到两个只出现一次的数字 $a$ 和 $b$。

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

func singleNumber(nums []int) []int {
	xs := 0
	for _, x := range nums {
		xs ^= x
	}
	lb := xs & -xs
	a := 0
	for _, x := range nums {
		if x&lb != 0 {
			a ^= x
		}
	}
	b := xs ^ a
	return []int{a, b}
}

力扣原题 · Doocs 题解来源

266. 回文排列 🔒

简单1 种解法

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

题目、示例与约束

给你一个字符串 s ，如果该字符串的某个排列是 回文串 ，则返回 true ；否则，返回 false 。

 

示例 1：

输入：s = "code"
输出：false

示例 2：

输入：s = "aab"
输出：true

示例 3：

输入：s = "carerac"
输出：true

 

提示：

• 1 <= s.length <= 5000
• s 仅由小写英文字母组成

方法一：计数 · Go 实现

思考

能排成回文当且仅当最多一个字符出现奇数次。统计频次后看奇数个计数是否少于 $2$。

如果一个字符串是回文串，那么至多只有一个字符出现奇数次数，其余字符都出现偶数次数。因此我们只需要统计每个字符出现的次数，然后判断是否满足这个条件即可。

时间复杂度 $O(n)$，空间复杂度 $O(|\mathrm{\Sigma }|)$。其中 $n$ 是字符串的长度，而 $|\mathrm{\Sigma }|$ 是字符集的大小，本题中字符集为小写字母，因此 $|\mathrm{\Sigma }|=26$。

func canPermutePalindrome(s string) bool {
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	odd := 0
	for _, x := range cnt {
		odd += x & 1
	}
	return odd < 2
}

力扣原题 · Doocs 题解来源

318. 最大单词长度乘积

中等2 种解法

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

题目、示例与约束

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

 

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。

示例 3：

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

 

提示：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 仅包含小写字母

方法一：位运算 · Go 实现

思考

两词无公共字母时长度乘积才计入。集合求交为 $O(\sigma )$，词数较多时需更快的正交判定。

把每个词压成 $26$ 位掩码，按位与为零即无公共字母。对每对 $i>j$ 检查掩码并更新最大乘积。 $n\le 1000$ 时 $O(n^2)$ 可接受。

题目需要我们找到两个没有公共字母的字符串，使得它们的长度乘积最大。我们可以将每个字符串用一个二进制数 $mask[i]$ 表示，这个二进制数的每一位表示字符串中是否含有某个字母。如果两个字符串没有公共字母，那么这两个字符串对应的二进制数的按位与的结果为 $0$，即 $mask[i]\mathrm{\&}mask[j]=0$。

我们遍历每个字符串，对于当前遍历到的字符串 $words[i]$，我们先算出对应的二进制数 $mask[i]$，然后再遍历 $j\in [0,i)$ 的所有字符串 $words[j]$，检查 $mask[i]\mathrm{\&}mask[j]=0$ 是否成立，如果成立就更新答案为 $max(ans,|words[i]|\times |words[j]|)$。

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

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

func maxProduct(words []string) (ans int) {
	n := len(words)
	mask := make([]int, n)
	for i, s := range words {
		for _, c := range s {
			mask[i] |= 1 << (c - 'a')
		}
		for j, t := range words[:i] {
			if mask[i]&mask[j] == 0 {
				ans = max(ans, len(s)*len(t))
			}
		}
	}
	return
}

方法二 · Go 实现

思考

方法一对相同字母集合的词会重复比较。用哈希表保留每种掩码的最大长度，枚举时只与已出现掩码比较。相同集合只留最长串，比较次数下降。

func maxProduct(words []string) (ans int) {
	mask := map[int]int{}
	for _, s := range words {
		a := len(s)
		x := 0
		for _, c := range s {
			x |= 1 << (c - 'a')
		}
		for y, b := range mask {
			if x&y == 0 {
				ans = max(ans, a*b)
			}
		}
		mask[x] = max(mask[x], a)
	}
	return
}

力扣原题 · Doocs 题解来源

342. 4的幂

简单1 种解法

标签：位运算、递归、数学

题目、示例与约束

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

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

 

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

 

提示：

• -231 <= n <= 231 - 1

 

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

方法一：位运算 · Go 实现

思考

判断是否为 $4$ 的幂。循环除以 $4$ 可行，但有位运算闭式。 $4^x=2^{2x}$，故须为正、恰一个 $1$，且该 $1$ 落在偶数位。

$n\mathrm{\&}(n-1)=0$ 保证是 $2$ 的幂； $n\mathrm{\&}\mathtt{\text{0xAAAAAAAA}}=0$ 排除奇数位上的那一个 $1$。三条件同时成立即可。

如果一个数是 $4$ 的幂次方，那么这个数必须是大于 $0$ 的。不妨假设这个数是 $4^x$，即 $2^{2x}$，那么这个数的二进制表示中有且仅有一个 $1$，且这个 $1$ 出现在偶数位上。

因此，我们首先判断这个数是否大于 $0$，然后判断这个数是否是 $2^{2x}$，即 $n$ 与 $n-1$ 的按位与结果是否为 $0$，最后判断这个数的 $1$ 是否出现在偶数位上，即 $n$ 与 $\mathit{\text{0xAAAAAAAA}}$ 的按位与结果是否为 $0$。如果这三个条件都满足，那么这个数就是 $4$ 的幂次方。

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

func isPowerOfFour(n int) bool {
	return n > 0 && (n&(n-1)) == 0 && (n&0xaaaaaaaa) == 0
}

力扣原题 · Doocs 题解来源

371. 两整数之和

中等1 种解法

标签：位运算、数学

题目、示例与约束

给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

 

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

 

提示：

• -1000 <= a, b <= 1000

方法一：位运算 · Go 实现

思考

不用加减号求两整数之和。按位：无进位和为异或，进位为与再左移。重复直到进位为零。

Python 整数无限长，先与 $0xFFFFFFFF$ 截到 $32$ 位；循环中同样掩码。结果若符号位为 $1$ 则按补码还原为负。

两数字的二进制形式 a,b ，求和 s = a + b ，a(i)、b(i) 分别表示 a、b 的第 i 个二进制位。一共有 4 种情况：

a(i)	b(i)	不进位的和	进位
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

观察可以发现，“不进位的和”与“异或运算”有相同规律，而进位则与“与”运算规律相同，并且需要左移一位。

• 对两数进行按位 ^ 异或运算，得到不进位的和；
• 对两数进行按位 & 与运算，然后左移一位，得到进位；
• 问题转换为求：“不进位的数 + 进位” 之和；
• 循环，直至进位为 0，返回不进位的数即可（也可以用递归实现）。

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

func getSum(a int, b int) int {
	for b != 0 {
		s := a ^ b
		b = (a & b) << 1
		a = s
	}
	return a
}

力扣原题 · Doocs 题解来源

389. 找不同

简单2 种解法

标签：位运算、哈希表、字符串、排序

题目、示例与约束

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

 

示例 1：

输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。

示例 2：

输入：s = "", t = "y"
输出："y"

 

提示：

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s 和 t 只包含小写字母

方法一：计数 · Go 实现

思考

$t$ 由 $s$ 打乱后再加一个字母。统计差即可。

计数 $s$，扫 $t$ 减一，减成负数的字符即多出的那个。

我们可以用一个哈希表或数组 $cnt$ 统计字符串 $s$ 中每个字符出现的次数，再遍历字符串 $t$，对于每个字符，我们在 $cnt$ 中减去一次出现的次数，如果对应次数为负数，则说明该字符在 $t$ 中出现的次数大于在 $s$ 中出现的次数，因此该字符为被添加的字符。

时间复杂度 $O(n)$，空间复杂度 $O(|\mathrm{\Sigma }|)$，其中 $n$ 为字符串的长度，而 $\mathrm{\Sigma }$ 表示字符集，这里字符集为所有小写字母，所以 $|\mathrm{\Sigma }|=26$。

func findTheDifference(s, t string) byte {
	cnt := [26]int{}
	for _, ch := range s {
		cnt[ch-'a']++
	}
	for i := 0; ; i++ {
		ch := t[i]
		cnt[ch-'a']--
		if cnt[ch-'a'] < 0 {
			return ch
		}
	}
}

方法二：求和 · Go 实现

思考

计数需 $O(\mathrm{\Sigma })$ 空间。两边 ASCII 之和的差即多出字符的码点，常数空间。

我们可以将字符串 $t$ 中每个字符的 ASCII 码的值求和，再减去字符串 $s$ 中每个字符的 ASCII 码的值求和，最后的结果即为被添加的字符的 ASCII 码对应的值。

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

func findTheDifference(s string, t string) byte {
	ss := 0
	for _, c := range s {
		ss -= int(c)
	}
	for _, c := range t {
		ss += int(c)
	}
	return byte(ss)
}

力扣原题 · Doocs 题解来源

393. UTF-8 编码验证

中等1 种解法

标签：位运算、数组

题目、示例与约束

给定一个表示数据的整数数组 data ，返回它是否为有效的 UTF-8 编码。

UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：

1. 对于 1 字节 的字符，字节的第一位设为 0 ，后面 7 位为这个符号的 unicode 码。
2. 对于 n 字节 的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0 ，后面字节的前两位一律设为 10 。剩下的没有提及的二进制位，全部为这个符号的 unicode 码。

这是 UTF-8 编码的工作方式：

      Number of Bytes  |        UTF-8 octet sequence
                       |              (binary)
   --------------------+---------------------------------------------
            1          | 0xxxxxxx
            2          | 110xxxxx 10xxxxxx
            3          | 1110xxxx 10xxxxxx 10xxxxxx
            4          | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x 表示二进制形式的一位，可以是 0 或 1。

注意：输入是整数数组。只有每个整数的 最低 8 个有效位 用来存储数据。这意味着每个整数只表示 1 字节的数据。

 

示例 1：

输入：data = [197,130,1]
输出：true
解释：数据表示字节序列:11000101 10000010 00000001。
这是有效的 utf-8 编码，为一个 2 字节字符，跟着一个 1 字节字符。

示例 2：

输入：data = [235,140,4]
输出：false
解释：数据表示 8 位的序列: 11101011 10001100 00000100.
前 3 位都是 1 ，第 4 位为 0 表示它是一个 3 字节字符。
下一个字节是开头为 10 的延续字节，这是正确的。
但第二个延续字节不以 10 开头，所以是不符合规则的。

 

提示:

• 1 <= data.length <= 2 * 104
• 0 <= data[i] <= 255

方法一：一次遍历 · Go 实现

思考

校验整数数组是否为合法 UTF-8 字节流。需按首字节的前缀确定后续 $10$ 开头的个数。一次扫描即可。

cnt 为仍待匹配的续字节。续字节须 10xxxxxx；否则按前缀判 $1$– $4$ 字节首部并设置 cnt。结束时 cnt 须为 $0$，中途不符则失败。

我们用一个变量 $cnt$ 记录当前需要填充的以 $10$ 开头的字节的个数，初始时 $cnt=0$。

遍历数组中的每个整数，对于每个整数 $v$：

• 如果 $cnt>0$，则判断 $v$ 是否以 $10$ 开头，如果不是，则返回 false，否则 $cnt$ 减一。
• 如果 $v$ 的最高位为 $0$，则 $cnt=0$。
• 如果 $v$ 的最高两位为 $110$，则 $cnt=1$。
• 如果 $v$ 的最高三位为 $1110$，则 $cnt=2$。
• 如果 $v$ 的最高四位为 $11110$，则 $cnt=3$。
• 否则，返回 false。

最后，如果 $cnt=0$，则返回 true，否则返回 false。

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

func validUtf8(data []int) bool {
	cnt := 0
	for _, v := range data {
		if cnt > 0 {
			if v>>6 != 0b10 {
				return false
			}
			cnt--
		} else if v>>7 == 0 {
			cnt = 0
		} else if v>>5 == 0b110 {
			cnt = 1
		} else if v>>4 == 0b1110 {
			cnt = 2
		} else if v>>3 == 0b11110 {
			cnt = 3
		} else {
			return false
		}
	}
	return cnt == 0
}

力扣原题 · Doocs 题解来源

405. 数字转换为十六进制数

简单1 种解法

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

题目、示例与约束

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

答案字符串中的所有字母都应该是小写字符，并且除了 0 本身之外，答案中不应该有任何前置零。

注意: 不允许使用任何由库提供的将数字直接转换或格式化为十六进制的方法来解决这个问题。

 

示例 1：

输入：num = 26
输出："1a"

示例 2：

输入：num = -1
输出："ffffffff"

 

提示：

• -231 <= num <= 231 - 1

方法一 · Go 实现

思考

补码 $32$ 位整数转十六进制，负数亦按位解释。逐位模拟十进制转码需要处理符号，不如直接按 $4$ 位一组取出。

从高到低共 $8$ 组，每组与 $0\text{xF}$ 得到 $0$– $15$，再映射到字符表。跳过尚未写出的前导零； $0$ 单独返回。

从高位开始扫描，才能在不反转缓冲区的前提下丢掉前导零。

func toHex(num int) string {
	if num == 0 {
		return "0"
	}
	sb := &strings.Builder{}
	for i := 7; i >= 0; i-- {
		x := num >> (4 * i) & 0xf
		if x > 0 || sb.Len() > 0 {
			var c byte
			if x < 10 {
				c = '0' + byte(x)
			} else {
				c = 'a' + byte(x-10)
			}
			sb.WriteByte(c)
		}
	}
	return sb.String()
}

力扣原题 · Doocs 题解来源

461. 汉明距离

简单1 种解法

标签：位运算

题目、示例与约束

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

 

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

 

提示：

• 0 <= x, y <= 231 - 1

 

注意：本题与 2220. 转换数字的最少位翻转次数 相同。

方法一：位运算 · Go 实现

思考

汉明距离是二进制不同位的个数。逐位比较需要循环 $32$ 次。

$x\oplus y$ 的 $1$ 位恰是不同位，对其做 $\mathit{\text{bit\_count}}$ 即可。

异或把比较收成一次字运算，再数 $1$ 的硬件指令或循环均可。

我们将 $x$ 和 $y$ 按位异或，得到的结果中的 $1$ 的个数就是汉明距离。

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

func hammingDistance(x int, y int) int {
	return bits.OnesCount(uint(x ^ y))
}

力扣原题 · Doocs 题解来源

476. 数字的补数

简单1 种解法

标签：位运算

题目、示例与约束

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

• 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

 

示例 1：

输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

示例 2：

输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

 

提示：

• 1 <= num < 231

 

注意：本题与 1009 https://leetcode.cn/problems/complement-of-base-10-integer/ 相同

方法一：位运算 · Go 实现

思考

补数是在不含前导零的二进制长度内按位取反。直接取反会连高位的 $0$ 一起翻成 $1$。

用 $2^{\mathit{\text{bit\_length}}}-1$ 做掩码，与原数异或，只翻转有效位。

掩码长度恰好等于最高位 $1$ 的位置，前导零不会进入结果。

根据题目描述，我们可以通过异或运算来实现取反的操作，步骤如下：

我们首先找到 $\mathit{\text{num}}$ 的二进制表示中最高位的 $1$，位置记为 $k$。

然后，构造一个二进制数，第 $k$ 位为 $0$，其余低位为 $1$，即 $2^k-1$；

最后，将 $\mathit{\text{num}}$ 与上述构造的二进制数进行异或运算，即可得到答案。

时间复杂度 $O(\log \mathit{\text{num}})$，其中 $\mathit{\text{num}}$ 为输入的整数。空间复杂度 $O(1)$。

func findComplement(num int) int {
	return num ^ ((1 << bits.Len(uint(num))) - 1)
}

力扣原题 · Doocs 题解来源

477. 汉明距离总和

中等1 种解法

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

题目、示例与约束

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。

 

示例 1：

输入：nums = [4,14,2]
输出：6
解释：在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，2表示为 0010 。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6

示例 2：

输入：nums = [4,14,4]
输出：4

 

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 109
• 给定输入的对应答案符合 32-bit 整数范围

方法一：位运算 · Go 实现

思考

所有数对的汉明距离之和。两两异或再计数是 $O(n^2)$。某一位上的贡献互相独立。

对第 $i$ 位，统计 $1$ 的个数 $a$，则 $0$ 的个数为 $n-a$，该位贡献 $a(n-a)$。累加 $32$ 位。

按位拆开后，每对数在该位上是否不同被计数一次，不必枚举数对。

我们在 $[0,31]$ 的范围内枚举每一位，对于当前枚举的位 $i$，我们统计所有数字中的第 $i$ 位为 $1$ 的个数 $a$，那么这些数字中的第 $i$ 位为 $0$ 的个数就是 $b=n-a$，其中 $n$ 是数组的长度。这样的话，在第 $i$ 位上的汉明距离之和就是 $a\times b$，我们把所有的位的汉明距离相加即为答案。

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

func totalHammingDistance(nums []int) (ans int) {
	for i := 0; i < 32; i++ {
		a := 0
		for _, x := range nums {
			a += x >> i & 1
		}
		b := len(nums) - a
		ans += a * b
	}
	return
}

力扣原题 · Doocs 题解来源

645. 错误的集合

简单3 种解法

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

题目、示例与约束

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了该集合发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

 

示例 1：

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

示例 2：

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

 

提示：

• 2 <= nums.length <= 104
• 1 <= nums[i] <= 104

方法一：数学 · Go 实现

思考

$[1,n]$ 中一数重复、一数缺失。扫描标记即可，也可用和差一次求出。

记 $s$ 为数组和、 $s_2$ 为去重和、 $s_1$ 为 $1..n$ 之和。则重复为 $s-s_2$，缺失为 $s_1-s_2$。

我们用 $s_1$ 表示 $[1,..n]$ 所有数字的和，用 $s_2$ 表示数组 $nums$ 去重后的数字和，用 $s$ 表示数组 $nums$ 的数字和。

那么 $s-s_2$ 就是重复的数字，而 $s_1-s_2$ 就是缺失的数字。

时间复杂度 $O(n)$，空间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。需要额外的空间对数组去重。

func findErrorNums(nums []int) []int {
	n := len(nums)
	s1 := (1 + n) * n / 2
	s2, s := 0, 0
	set := map[int]bool{}
	for _, x := range nums {
		if !set[x] {
			set[x] = true
			s2 += x
		}
		s += x
	}
	return []int{s - s2, s1 - s2}
}

方法二：哈希表 · Go 实现

思考

数学法依赖去重集合。直接计每个值的出现次数，出现 $2$ 次与 $0$ 次的即答案，读写更直观。

我们也可以一种更加直观的方法，直接用哈希表 $cnt$ 统计数组 $nums$ 中每个数字出现的次数。

接下来遍历 $x\in [1,n]$，如果 $cnt[x]=2$，那么 $x$ 就是重复的数字，如果 $cnt[x]=0$，那么 $x$ 就是缺失的数字。

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

func findErrorNums(nums []int) []int {
	n := len(nums)
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	ans := make([]int, 2)
	for x := 1; x <= n; x++ {
		if cnt[x] == 2 {
			ans[0] = x
		} else if cnt[x] == 0 {
			ans[1] = x
		}
	}
	return ans
}

方法三：位运算 · Go 实现

思考

前两法都要线性额外空间。把 $nums$ 与 $1..n$ 全部异或得到 $a\oplus b$，再用 $\mathit{\text{lowbit}}$ 分组，两组分别异或出 $a,b$，看谁出现在数组里即知重复与缺失。

根据异或运算的性质，对于整数 $x$，有 $x\oplus x=0$ 以及 $x\oplus 0=x$，因此我们对数组 $nums$ 中的所有元素以及 $i\in [1,n]$ 的所有数字进行异或运算，可以消除出现两次的数字，最终只留下缺失的数字和重复的数字的异或结果，即 $xs=a\oplus b$。

由于这两个数字不相等，因此异或结果中至少存在一位为 $1$。我们通过 $lowbit$ 运算找到异或结果中最低位的 $1$，然后将数组 $nums$ 中所有数字以及 $i\in [1,n]$ 的所有数字按照该位是否为 $1$ 分为两组，这样两个数字就被分到了不同的组中。其中一组数字的异或结果为 $a$，另一组数字的异或结果为 $b$。那么这两个数字就是我们要找的答案。

接下来我们只需要判断 $a$ 和 $b$ 哪个数字是重复的数字，哪个数字是缺失的数字即可。因此，遍历数组 $nums$，对于遍历到的数字 $x$，如果 $x=a$，那么 $a$ 就是重复的数字，返回 $[a,b]$，否则遍历结束，返回 $[b,a]$。

时间复杂度 $O(n)$，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$，仅使用常数大小的额外空间。

func findErrorNums(nums []int) []int {
	xs := 0
	for i, x := range nums {
		xs ^= x ^ (i + 1)
	}
	lb := xs & -xs
	a := 0
	for i, x := range nums {
		if (i+1)&lb != 0 {
			a ^= (i + 1)
		}
		if x&lb != 0 {
			a ^= x
		}
	}
	b := xs ^ a
	for _, x := range nums {
		if x == a {
			return []int{a, b}
		}
	}
	return []int{b, a}
}

力扣原题 · Doocs 题解来源

693. 交替位二进制数

简单2 种解法

标签：位运算

题目、示例与约束

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

 

示例 1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2：

输入：n = 7
输出：false
解释：7 的二进制表示是：111.

示例 3：

输入：n = 11
输出：false
解释：11 的二进制表示是：1011.

 

提示：

• 1 <= n <= 231 - 1

方法一：模拟 · Go 实现

思考

判断相邻二进制位是否严格交替。逐位比较即可。

反复取最低位并右移，与上一比特相同则失败，扫完为真。

我们将 $n$ 循环右移直至为 $0$，依次检测 $n$ 的二进制位是否交替出现。若循环过程中发现 $0$, $1$ 没有交替出现，直接返回 $\mathit{\text{false}}$。否则循环结束返回 $\mathit{\text{true}}$。

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

func hasAlternatingBits(n int) bool {
	prev := -1
	for n != 0 {
		curr := n & 1
		if prev == curr {
			return false
		}
		prev = curr
		n >>= 1
	}
	return true
}

方法二：位运算 · Go 实现

思考

模拟是 $O(\log n)$。 $n\oplus (n\gg 1)$ 若各位交替会变成一串 $1$，再与 $n+1$ 相与应为 $0$，常数时间判定。

假设 $\text{01}$ 交替出现，那么我们可以通过错位异或将尾部全部转为 $\text{1}$，加 $\text{1}$ 可以得到 $2$ 的幂次的一个数 $n$（ $n$ 中只有一个位是 $\text{1}$），接着利用 $\text{n}\mathrm{\&}(\text{n}+1)$ 可以消除最后一位的 $\text{1}$。

此时判断是否为 $\text{0}$，若是，说明假设成立，是 $\text{01}$ 交替串。

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

func hasAlternatingBits(n int) bool {
	n ^= (n >> 1)
	return (n & (n + 1)) == 0
}

力扣原题 · Doocs 题解来源

751. IP 到 CIDR 🔒

中等1 种解法

标签：位运算、字符串

题目、示例与约束

IP地址 是一个格式化的 32位 无符号整数，每组 8位 被打印为一个十进制数字和，点字符 '.' 起到了分组的作用。

• 例如，二进制数 00001111 10001000 11111111 01101011 ( 为清晰起见增加了空格)被格式化为IP地址将是 “15.136.255.107” 。

CIDR块 是一种用来表示一组特定IP地址的格式。字符串形式，由基础IP地址、斜杠和前缀长度 k 组成。它所覆盖的地址是所有IP地址的 前 k 位 与基础IP地址相同的IP地址。

• 例如， “123.45.67.89/20” 是一个前缀长度为 20 的 CIDR块。任何二进制表示形式匹配 01111011 00101101 0100xxxx xxxxxxxx 的IP地址，其中 x 可以是 0 或 1 ，都在CIDR块覆盖的集合中。

给你一个起始IP地址 ip 和我们需要覆盖的IP地址数量 n 。你的目标是使用 尽可能少的CIDR块 来 覆盖范围 [ip, ip + n - 1] 内的所有IP地址 。不应该覆盖范围之外的其他IP地址。

返回 包含IP地址范围的 CIDR块 的 最短 列表。如果有多个答案，返回其中 任何 一个 。

 

示例 1：

输入：ip = "255.0.0.7", n = 10
输出：["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]
解释：
需要覆盖的IP地址有:
- 255.0.0.7 -> 11111111 00000000 00000000 00000111
- 255.0.0.8 -> 11111111 00000000 00000000 00001000
- 255.0.0.9 -> 11111111 00000000 00000000 00001001
- 255.0.0.10 -> 11111111 00000000 00000000 00001010
- 255.0.0.11 -> 11111111 00000000 00000000 00001011
- 255.0.0.12 -> 11111111 00000000 00000000 00001100
- 255.0.0.13 -> 11111111 00000000 00000000 00001101
- 255.0.0.14 -> 11111111 00000000 00000000 00001110
- 255.0.0.15 -> 11111111 00000000 00000000 00001111
- 255.0.0.16 -> 11111111 00000000 00000000 00010000
CIDR区块“255.0.0.7/32”包含第一个地址。
CIDR区块255.0.0.8/29包含中间的8个地址(二进制格式为11111111 00000000 00000000 00001xxx)。
CIDR区块“255.0.0.16/32”包含最后一个地址。
请注意，虽然CIDR区块“255.0.0.0/28”覆盖了所有的地址，但它也包括范围之外的地址，所以我们不能使用它。

示例 2:

输入：ip = "117.145.102.62", n = 8
输出：["117.145.102.62/31","117.145.102.64/30","117.145.102.68/31"]

 

提示:

• 7 <= ip.length <= 15
• ip 是一个有效的 IPv4 ，形式为 "a.b.c.d" ，其中 a, b, c,  d 是 [0, 255] 范围内的整数
• 1 <= n <= 1000
• 每个隐含地址 ip + x ( x < n) 都是有效的 IPv4 地址

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

本站根据题意与 Doocs 参考思路整理为 Go，非上游原文。按 CC BY-SA 4.0 共享。

根据题意补写贪心。把 IPv4 地址转换为 32 位无符号整数。当前起点最低有效位给出满足对齐的最大块，再缩小到不超过剩余地址数；输出对应 CIDR 后向前移动。起点为零时允许 2³² 大小的对齐块，避免 lowbit 为零导致死循环。若输出 B 个块，时间 O(32B)，额外空间 O(1)，输出空间 O(B)。

import (
	"fmt"
	"math/bits"
	"strconv"
	"strings"
)

func ipToCIDR(ip string, n int) []string {
	var value uint64
	for _, part := range strings.Split(ip, ".") {
		v, _ := strconv.Atoi(part)
		value = value*256 + uint64(v)
	}
	remaining := uint64(n)
	ans := []string{}
	for remaining > 0 {
		size := value & -value
		if size == 0 {
			size = uint64(1) << 32
		}
		for size > remaining {
			size >>= 1
		}
		prefix := 32 - bits.TrailingZeros64(size)
		ans = append(ans, fmt.Sprintf("%d.%d.%d.%d/%d", value>>24&255, value>>16&255, value>>8&255, value&255, prefix))
		value += size
		remaining -= size
	}
	return ans
}

力扣原题 · Doocs 题解来源

762. 二进制表示中质数个计算置位

简单1 种解法

标签：位运算、数学、素性测试

题目、示例与约束

给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。

计算置位位数 就是二进制表示中 1 的个数。

• 例如， 21 的二进制表示 10101 有 3 个计算置位。

 

示例 1：

输入：left = 6, right = 10
输出：4
解释：
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
共计 4 个计算置位为质数的数字。

示例 2：

输入：left = 10, right = 15
输出：5
解释：
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)
共计 5 个计算置位为质数的数字。

 

提示：

• 1 <= left <= right <= 106
• 0 <= right - left <= 104

方法一：数学 + 位运算 · Go 实现

思考

区间长度不超过 ${10}^4$，上界 ${10}^6$，二进制中 $1$ 的个数至多 $20$。枚举每个数统计比特再判断质数完全可行。

$20$ 以内质数只有八个，放进集合后 $\mathit{\text{bit\_count}}$ 一次查询即可。不必对每个个数做试除。

题目中 $\mathit{\text{left}}$ 和 $\mathit{\text{right}}$ 的范围均在 ${10}^6$ 以内，而 $2^{20}=1048576$，因此，二进制中 $1$ 的个数最多也就 $20$ 个，而 $20$ 以内的质数有 $[2,3,5,7,11,13,17,19]$。

我们枚举 $[\mathit{\text{left}},..\mathit{\text{right}}]$ 范围内的每个数，统计其二进制中 $1$ 的个数，然后判断该个数是否为质数，如果是，答案加一。

时间复杂度 $O(n\times \log m)$。其中 $n=\mathit{\text{right}}-\mathit{\text{left}}+1$，而 $m$ 为 $[\mathit{\text{left}},..\mathit{\text{right}}]$ 范围内的最大数。

func countPrimeSetBits(left int, right int) (ans int) {
	primes := map[int]int{}
	for _, v := range []int{2, 3, 5, 7, 11, 13, 17, 19} {
		primes[v] = 1
	}
	for i := left; i <= right; i++ {
		ans += primes[bits.OnesCount(uint(i))]
	}
	return
}

力扣原题 · Doocs 题解来源

779. 第K个语法符号

中等2 种解法

标签：位运算、递归、数学

题目、示例与约束

我们构建了一个包含 n 行( 索引从 1  开始 )的表。首先在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

• 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。

给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）

示例 1:

输入: n = 1, k = 1
输出: 0
解释: 第一行：0

示例 2:

输入: n = 2, k = 1
输出: 0
解释: 
第一行: 0 
第二行: 01

示例 3:

输入: n = 2, k = 2
输出: 1
解释:
第一行: 0
第二行: 01

 

提示:

• 1 <= n <= 30
• 1 <= k <= 2n - 1

方法一：递归 · Go 实现

思考

第 $n$ 行由上一行每位变成 $01$ 或 $10$ 得到，求第 $k$ 位。行长 $2^{n-1}$，不能生成整行。

前半与上一行相同，后半是上一行的翻转。按 $k$ 落在哪一半递归到 $n-1$，后半再异或 $1$。

我们先来看一下前几行的规律：

n = 1: 0
n = 2: 0 1
n = 3: 0 1 1 0
n = 4: 0 1 1 0 1 0 0 1
n = 5: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
...

可以发现，每一行的前半部分和上一行完全一致，后半部分是上一行的反转。注意，这里的“反转”指的是 $0$ 变 $1$, $1$ 变 $0$。

如果 $k$ 在前半部分，那么第 $k$ 个字符就是上一行的第 $k$ 个字符，直接递归 $kthGrammar(n-1,k)$ 即可。

如果 $k$ 在后半部分，那么第 $k$ 个字符就是上一行的第 $k-2^{n-2}$ 个字符的反转，即 $kthGrammar(n - 1, k - 2^{n - 2}) \oplus 1 $。

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

func kthGrammar(n int, k int) int {
	if n == 1 {
		return 0
	}
	if k <= (1 << (n - 2)) {
		return kthGrammar(n-1, k)
	}
	return kthGrammar(n-1, k-(1<<(n-2))) ^ 1
}

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

思考

方法一仍走 $n$ 层。观察从根到第 $k$ 位（改从 $0$ 编号）的路径：每次走向奇数孩子就翻转一次，翻转次数即 $k-1$ 的二进制中 $1$ 的个数。

因此答案为 $(k-1).\mathit{\text{bit\_count}}mod2$，与 $n$ 无关（ $n$ 足够长即可）。

题目中索引从 $1$ 开始，我们将 $k$ 改成 $k-1$，将索引转换为从 $0$ 开始。在接下来的讨论中，索引均从 $0$ 开始。

仔细观察，一行中的第 $i$ 个字符，会在第 $2i$ 和第 $2i+1$ 个位置产生两个字符。

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

如果第 $i$ 个字符是 $0$，那么在位置 $2i$ 和 $2i+1$ 产生的字符分别是 $0$ 和 $1$；如果第 $i$ 个字符是 $1$，产生的字符是 $1$ 和 $0$。

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
      ^     * *

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
        ^       * *

可以发现，第 $2i$ （偶数位）个字符总是和第 $i$ 个字符相同，而第 $2i+1$ （奇数位）个字符是第 $i$ 个字符的反转。也就是说，奇数位上的字符总是发生了一次反转而来的。反转偶数次，字符不变；反转奇数次，相当于反转了一次。

因此，我们只需要看 $k$ 这个数字是否是奇数，若是，累计一次反转。然后将 $k$ 除以 $2$，继续判断，并累计反转次数，直至 $k$ 为 $0$。

最后判断反转的次数是否为奇数，是则答案为 $1$，否则为 $0$。

以上累计反转次数的过程，实际上等价于求 $k$ 的二进制表示中，有多少位是 $1$。

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

func kthGrammar(n int, k int) int {
	return bits.OnesCount(uint(k-1)) & 1
}

力扣原题 · Doocs 题解来源

782. 变为棋盘

困难1 种解法

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

题目、示例与约束

一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能交换任意两列或是两行的位置。

返回 将这个矩阵变为  “棋盘”  所需的最小移动次数 。如果不存在可行的变换，输出 -1。

“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。

 

示例 1:

输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:一种可行的变换方式如下，从左到右：
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。

示例 2:

输入: board = [[0, 1], [1, 0]]
输出: 0
解释: 注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.

示例 3:

输入: board = [[1, 0], [1, 0]]
输出: -1
解释: 任意的变换都不能使这个输入变为合法的棋盘。

 

提示：

• n == board.length
• n == board[i].length
• 2 <= n <= 30
• board[i][j] 将只包含 0或 1

方法一：规律观察 + 状态压缩 · Go 实现

思考

只允许整行整列交换，要变成棋盘染色。 $n\le 30$，枚举交换序列不可行。合法棋盘的行只能有两种且互为取反，列同理，且 $0/1$ 个数各半（或差一）。

用第一行、第一列的比特掩码代表这两种模式，其余行/列必须等于它或它的取反，否则无解。

再按奇偶分别计算把第一行（列）调成 $0101\dots$ 或 $1010\dots$ 的交换次数，取合法较小值。行、列次数相加。

在一个有效的棋盘中，有且仅有两种“行”。

例如，如果棋盘中有一行为“01010011”，那么任何其它行只能为“01010011”或者“10101100”。列也满足这种性质。

另外，每一行和每一列都有一半 $0$ 和一半 $1$。假设棋盘为 $n\times n$：

• 若 $n=2\times k$，则每一行和每一列都有 $k$ 个 $1$ 和 $k$ 个 $0$。
• 若 $n=2\times k+1$，则每一行都有 $k$ 个 $1$ 和 $k+1$ 个 $0$，或者 $k+1$ 个 $1$ 和 $k$ 个 $0$。

基于以上的结论，我们可以判断一个棋盘是否有效。若有效，可以计算出最小的移动次数。

若 $n$ 为偶数，最终的合法棋盘有两种可能，即第一行的元素为“010101...”，或者“101010...”。我们计算出这两种可能所需要交换的次数的较小值作为答案。

若 $n$ 为奇数，那么最终的合法棋盘只有一种可能。如果第一行中 $0$ 的数目大于 $1$，那么最终一盘的第一行只能是“01010...”，否则就是“10101...”。同样算出次数作为答案。

时间复杂度 $O(n^2)$，其中 $n$ 是棋盘的大小。空间复杂度 $O(1)$。

func movesToChessboard(board [][]int) int {
	n := len(board)
	mask := (1 << n) - 1
	rowMask, colMask := 0, 0
	for i := 0; i < n; i++ {
		rowMask |= board[0][i] << i
		colMask |= board[i][0] << i
	}
	revRowMask := mask ^ rowMask
	revColMask := mask ^ colMask
	sameRow, sameCol := 0, 0
	for i := 0; i < n; i++ {
		curRowMask, curColMask := 0, 0
		for j := 0; j < n; j++ {
			curRowMask |= board[i][j] << j
			curColMask |= board[j][i] << j
		}
		if curRowMask != rowMask && curRowMask != revRowMask {
			return -1
		}
		if curColMask != colMask && curColMask != revColMask {
			return -1
		}
		if curRowMask == rowMask {
			sameRow++
		}
		if curColMask == colMask {
			sameCol++
		}
	}
	f := func(mask, cnt int) int {
		ones := bits.OnesCount(uint(mask))
		if n%2 == 1 {
			if abs(n-ones*2) != 1 || abs(n-cnt*2) != 1 {
				return -1
			}
			if ones == n/2 {
				return n/2 - bits.OnesCount(uint(mask&0xAAAAAAAA))
			}
			return (n+1)/2 - bits.OnesCount(uint(mask&0x55555555))
		} else {
			if ones != n/2 || cnt != n/2 {
				return -1
			}
			cnt0 := n/2 - bits.OnesCount(uint(mask&0xAAAAAAAA))
			cnt1 := n/2 - bits.OnesCount(uint(mask&0x55555555))
			return min(cnt0, cnt1)
		}
	}
	t1 := f(rowMask, sameRow)
	t2 := f(colMask, sameCol)
	if t1 == -1 || t2 == -1 {
		return -1
	}
	return t1 + t2
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

810. 黑板异或游戏

困难1 种解法

标签：位运算、脑筋急转弯、数组、数学、博弈、零和博弈、无偏博弈

题目、示例与约束

黑板上写着一个非负整数数组 nums[i] 。

Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。

并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0 ，这个玩家获胜。

假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。

 

示例 1：

输入: nums = [1,1,2]
输出: false
解释: 
Alice 有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。
如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。

示例 2:

输入: nums = [0,1]
输出: true

示例 3:

输入: nums = [1,2,3]
输出: true

 

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 216

方法一：位运算 · Go 实现

思考

每次擦掉一个数后，若剩余数字异或为 $0$ 则对方失败。直接搜索博弈树在 $n\le 1000$ 时过深。关键观察是：若当前异或已为 $0$，先手立刻获胜；否则当 $n$ 为偶数时，总存在一种擦法使后手面对异或非零的偶数局面，先手必胜。

因此答案只取决于「长度是否为偶数」或「全体异或是否为 $0$」，一次异或扫描即可。

根据游戏规则，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果为 $0$，这个玩家获胜。由于 Alice 先手，因此当 $\mathit{\text{nums}}$ 中所有数字的异或结果为 $0$ 时，Alice 可以获胜。

当 $\mathit{\text{nums}}$ 中所有数字的异或结果不为 $0$ 时，我们不妨考虑从数组 $\mathit{\text{nums}}$ 的长度奇偶性来分析 Alice 的获胜情况。

当 $\mathit{\text{nums}}$ 的长度为偶数时，如果 Alice 必败，那么只有一种情况，就是 Alice 无论擦掉哪个数字，剩余所有数字的异或结果都等于 $0$。我们来分析一下是否存在这种情况。

假设数组 $\mathit{\text{nums}}$ 长度为 $n$，并且 $n$ 是偶数，记所有数字异或结尾为 $S$，则有：

$$S=\mathit{\text{nums}}[0]\oplus \mathit{\text{nums}}[1]\oplus \cdots \oplus \mathit{\text{nums}}[n-1]\ne 0$$

我们记 $S_i$ 为数组 $\mathit{\text{nums}}$ 擦掉第 $i$ 个数字后的异或结果，那么有：

$$S_i\oplus \mathit{\text{nums}}[i]=S$$

等式两边同时异或 $\mathit{\text{nums}}[i]$，得到：

$$S_i=S\oplus \mathit{\text{nums}}[i]$$

如果无论 Alice 擦掉哪个数字，剩余所有数字的异或结果都等于 $0$，那么对所有 $i$，都有 $S_i=0$，即：

$$S_0\oplus S_1\oplus \cdots \oplus S_{n-1}=0$$

我们将 $S_i=S\oplus \mathit{\text{nums}}[i]$ 代入上式，得到：

$$S\oplus \mathit{\text{nums}}[0]\oplus S\oplus \mathit{\text{nums}}[1]\oplus \cdots \oplus S\oplus \mathit{\text{nums}}[n-1]=0$$

上式共有 $n$（偶数）个 $S$，而 $\mathit{\text{nums}}[0]\oplus \mathit{\text{nums}}[1]\oplus \cdots \oplus \mathit{\text{nums}}[n-1]$ 也等于 $S$，因此上式等价于 $0\oplus S=0$。这与 $S\ne 0$ 矛盾，因此不存在这种情况。因此当 $\mathit{\text{nums}}$ 的长度为偶数时，Alice 必胜。

如果长度为奇数，那么 Alice 擦掉一个数字后，剩余数字个数为偶数，也就是将偶数长度的情况留给 Bob，那么 Bob 必胜，也即 Alice 必败。

综上，当 $\mathit{\text{nums}}$ 的长度为偶数，或者 $\mathit{\text{nums}}$ 中所有数字的异或结果为 $0$ 时，Alice 可以获胜。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func xorGame(nums []int) bool {
	if len(nums)%2 == 0 {
		return true
	}
	x := 0
	for _, v := range nums {
		x ^= v
	}
	return x == 0
}

力扣原题 · Doocs 题解来源

868. 二进制间距

简单1 种解法

标签：位运算

题目、示例与约束

给定一个正整数 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 <= 109

方法一：位运算 · Go 实现

思考

求二进制中两个相邻 $1$ 的最大距离。 $n\le {10}^9$，移位扫描全部比特即可，不必转成字符串。

记下上一个 $1$ 的位次，再遇到 $1$ 时用间距更新答案。没有两个 $1$ 则间距保持为 $0$。

我们用两个指针 $\mathit{\text{pre}}$ 和 $\mathit{\text{cur}}$ 分别表示上一个和当前的 $1$ 的位置，初始时 $\mathit{\text{pre}}=100$, $\mathit{\text{cur}}=0$，然后遍历 $n$ 的二进制表示，当遇到 $1$ 时，计算当前位置和上一个 $1$ 的位置之间的距离，并更新答案。

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

func binaryGap(n int) (ans int) {
	for pre, cur := 100, 0; n != 0; n >>= 1 {
		if n&1 == 1 {
			ans = max(ans, cur-pre)
			pre = cur
		}
		cur++
	}
	return
}

力扣原题 · Doocs 题解来源

957. N 天后的牢房

中等1 种解法

标签：位运算、数组、哈希表、数学、Floyd 判圈算法

题目、示例与约束

监狱中 8 间牢房排成一排，每间牢房可能被占用或空置。

每天，无论牢房是被占用或空置，都会根据以下规则进行变更：

• 如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
• 否则，它就会被空置。

注意：由于监狱中的牢房排成一行，所以行中的第一个和最后一个牢房不存在两个相邻的房间。

给你一个整数数组 cells ，用于表示牢房的初始状态：如果第 i 间牢房被占用，则 cell[i]==1，否则 cell[i]==0 。另给你一个整数 n 。

请你返回 n 天后监狱的状况（即，按上文描述进行 n 次变更）。

 

示例 1：

输入：cells = [0,1,0,1,1,0,0,1], n = 7
输出：[0,0,1,1,0,0,0,0]
解释：下表总结了监狱每天的状况：
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

示例 2：

输入：cells = [1,0,0,1,0,0,1,0], n = 1000000000
输出：[0,0,1,1,1,1,1,0]

 

提示：

• cells.length == 8
• cells[i] 为 0 或 1
• 1 <= n <= 109

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

根据题意整理：本地 Doocs 实现围栏为空，依据题意和状态循环提示实现。把 8 间牢房编码成 8 位整数。记录每个状态第一次出现时的剩余天数；再次出现时，两次剩余天数之差就是周期，将剩余天数对周期取模，再继续同步更新。新状态只计算中间 6 位，两端固定为零。

变量与复杂度：state 是当前状态，seen[state] 是曾记录的剩余天数，n 为剩余天数，S≤256 为可达状态数。时间 O(8S)，空间 O(S)，与原始天数是否达到 10⁹ 无关。

平台接口：prisonAfterNDays(cells []int, n int) []int；返回新切片，不改调用者的 cells，无额外平台类型。

出处与许可：基于 Doocs 原题及参考资料，固定提交 91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011；Go 代码及本说明按 CC BY-SA 4.0 共享。

// 依据 Doocs/leetcode 题目与参考资料进行 Go 改写/整理。
// 来源：https://github.com/doocs/leetcode/blob/91ef8c241a5eaabf96f9ca8d45cfb1a338bcb011/solution/0900-0999/0957.Prison%20Cells%20After%20N%20Days/README.md
// 许可：CC BY-SA 4.0，https://creativecommons.org/licenses/by-sa/4.0/

func prisonAfterNDays(cells []int, n int) []int {
	state := 0
	for i, v := range cells {
		state |= v << i
	}
	seen := map[int]int{}
	for n > 0 {
		if previous, ok := seen[state]; ok {
			n %= previous - n
			if n == 0 {
				break
			}
		}
		seen[state] = n
		next := 0
		for i := 1; i < 7; i++ {
			if (state>>(i-1))&1 == (state>>(i+1))&1 {
				next |= 1 << i
			}
		}
		state = next
		n--
	}
	ans := make([]int, 8)
	for i := range ans {
		ans[i] = (state >> i) & 1
	}
	return ans
}

力扣原题 · Doocs 题解来源

982. 按位与为零的三元组

困难1 种解法

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

题目、示例与约束

给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

• 0 <= i < nums.length
• 0 <= j < nums.length
• 0 <= k < nums.length
• nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

 

示例 1：

输入：nums = [2,1,3]
输出：12
解释：可以选出如下 i, j, k 三元组：
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

示例 2：

输入：nums = [0,0,0]
输出：27

 

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 216

方法一：枚举 + 计数 · Go 实现

思考

统计 $x\mathrm{\&}y\mathrm{\&}z=0$ 的三元组， $n\le 1000$，三重循环偏紧。先枚举前两个数，用计数表记下 $x\mathrm{\&}y$；再枚举该与值与 $z$，若再与为 $0$ 则累加次数。值域小于 $2^{16}$，表的规模可接受。

我们可以先枚举任意两个数 $x$ 和 $y$，用哈希表或数组 $cnt$ 统计它们的按位与结果 $x\mathrm{\&}y$ 出现的次数。

然后我们枚举 $x$ 和 $y$ 的按位与结果 $xy$，再枚举 $z$，如果 $xy\mathrm{\&}z=0$，则将 $cnt[xy]$ 的值加入答案。

最后返回答案即可。

时间复杂度 $O(n^2+n\times M)$，空间复杂度 $O(M)$，其中 $n$ 是数组 $nums$ 的长度；而 $M$ 是数组 $nums$ 中的最大值，本题中 $M\le 2^{16}$。

func countTriplets(nums []int) (ans int) {
	mx := slices.Max(nums)
	cnt := make([]int, mx+1)
	for _, x := range nums {
		for _, y := range nums {
			cnt[x&y]++
		}
	}
	for xy := 0; xy <= mx; xy++ {
		for _, z := range nums {
			if xy&z == 0 {
				ans += cnt[xy]
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1009. 十进制整数的反码

简单1 种解法

标签：位运算

题目、示例与约束

每个非负整数 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 。

 

提示：

1. 0 <= N < 10^9
2. 本题与 476：https://leetcode.cn/problems/number-complement/ 相同

方法一：位运算 · Go 实现

思考

写成二进制再按位取反可以得到补数，但 $n$ 可达 ${10}^9$，且补数不含前导零对应的高位翻转， $n=0$ 还需单独得到 $1$。

从低到高逐位处理时，只需对 $n$ 中实际出现过的位取反并写入答案，处理完后 $n$ 右移为空即停，自然不会碰到更高的零位。

用 $i$ 记录当前位数，将 $(nmod2)$ 取反后或入 $\mathit{\text{ans}}$ 的第 $i$ 位，直到 $n$ 变为 $0$。

我们首先判断 $n$ 是否为 $0$，如果是，则返回 $1$。

接着我们定义两个变量 $\mathit{\text{ans}}$ 和 $i$，初始化为 $0$。然后我们遍历 $n$，在每次遍历中，我们将 $\mathit{\text{ans}}$ 的第 $i$ 位设置为 $n$ 的第 $i$ 位取反，然后将 $i$ 加 $1$，并且 $n$ 右移 $1$ 位。

最后返回 $\mathit{\text{ans}}$ 即可。

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

func bitwiseComplement(n int) (ans int) {
	if n == 0 {
		return 1
	}
	for i := 0; n != 0; n >>= 1 {
		ans |= (n&1 ^ 1) << i
		i++
	}
	return
}

力扣原题 · Doocs 题解来源