算法笔试-位运算
Updated Time
Category
Tags
关于语言：一刷用 Golang，二刷用 Rust
位运算
集合可以用二进制表示，从低到高第 \(i\) 位为 \(1\) 表示 \(i\) 在集合中。例如集合 \(\{ 0, 2, 3 \}\) 可以用二进制数 \(1101_{(2)}\) 表示；反之 $ 1101_{(2)}$ 对应着集合 \(\{ 0, 2, 3 \}\)
也就是说，包含非负整数的集合 \(S\) 可以压缩成一个数字。
集合与集合：& 表示按位与，| 表示按位或，\(\oplus\) 表示按位异或，~ 表示按位取反，对称差指仅在其中一个集合的元素。
| 术语 | 集合 | 位运算 | |
|---|---|---|---|
| 交集 | \(A \cap B\) | \(a \& b\) | |
| 并集 | \(A \cup B\) | \(a | b\) | |
| 对称差 | \(A \bigtriangleup B\) | \(a \oplus b\) | |
| 差 | \(A \backslash B\) | \(a \& \sim b\) |
集合与元素：
| 术语 | 集合 | 位运算 |
|---|---|---|
| 属于 | \(i \in S\) | \((s >> i) \& 1 = 1\) |
| 不属于 | \(i \notin S\) | \((s >> i) \& 1 = 0\) |
| 添加元素 | \(S \cup \{ i\}\) | s | (1 << i) |
| 删除元素 | \(S \backslash \{i\}\) | s & ~ (1 << i) |
| 删除最小元素 | s & (s-1) |
库函数： |术语|Python|Java|C++|Go|
|---|------|----|---|---|
|集合大小|s.bit_count()|Integer.bitcount(s)|__builtin_popcount(s)|bits.OnesCount(s)|
|二进制长度（减一得到集合中的最大元素）|s.bit_length()|32-Integer.numberOfLeadingZeros(s)|32-__builtin_clz(s)|bits.Len(s)|
|集合中的最小元素|(s&-s).bit_length()-1|Integer.numberOfTrailingZeros(s)|__builtin_ctz(s)|bits.TrailingZeros(s)|
遍历集合：设元素范围从 \(0\) 到 \(n-1\)，挨个判断是否在集合 \(s\) 中：
for (int i = 0; i < n; i++) {
if ((s >> i) & 1) { // i 在 s 中
// 处理 i 的逻辑
}
}
枚举集合：设元素范围从 \(0\) 到 \(n-1\)，从空集枚举到全集：
for (int s = 0; s < (1 << n); s++) {
// 处理 s 的逻辑
}
设集合为 \(s\)，从大到小枚举 \(s\) 的所有非空子集 \(sub\)：
for (int sub = s; sub; sub = (sub - 1) & s) {
// 处理 sub 的逻辑
}
题单
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 3370. 仅含置位位的最小整数 | 第 426 场周赛 Q1 | 简单 | 1199 |
| 3226. 使两个整数相等的位更改次数 | 第 407 场周赛 Q1 | 简单 | 1247 |
| 1356. 根据数字二进制下 1 的数目排序 | 第 20 场双周赛 Q1 | 简单 | 1258 |
| 461. 汉明距离 | 简单 | ||
| 476. 数字的补数 | 简单 | ||
| 868. 二进制间距 | 第 93 场周赛 Q1 | 简单 | 1307 |
| 3211. 生成不含相邻零的二进制字符串 | 第 405 场周赛 Q2 | 中等 | 1353 |
| 2917. 找出数组中的 K-or 值 | 第 369 场周赛 Q1 | 简单 | 1389 |
| 693. 交替位二进制数 | 简单 | ||
| 2657. 找到两个数组的前缀公共数组 | 第 103 场周赛 Q2 | 中等 | 1304 |
| 231. 2 的幂 | 简单 |
题解
3370. 仅含置位位的最小整数
func smallestNumber(n int) int {
return 1 << bits.Len(uint(n)) - 1
}
3226. 使两个整数相等的位更改次数
func minChanges(n int, k int) int {
if n & k != k {
return -1
}
return bits.OnesCount(uint(n ^ k))
}
1356. 根据数字二进制下 1 的数目排序
func sortByBits(arr []int) []int {
sort.Slice(arr, func (i, j int) bool {
a := bits.OnesCount(uint(arr[i]))
b := bits.OnesCount(uint(arr[j]))
if a != b {
return bits.OnesCount(uint(arr[i])) < bits.OnesCount(uint(arr[j]))
}
return arr[i] < arr[j]
})
return arr
}
461. 汉明距离
func hammingDistance(x int, y int) int {
return bits.OnesCount(uint(x ^ y))
}
476. 数字的补数
func findComplement(num int) int {
return 1 << bits.Len(uint(num)) - 1 - num
}
868. 二进制间距
func binaryGap(n int) int {
i, idx, ans := 0, -1, 0
for ; n > 0; n = n >> 1 {
if n & 1 == 1 {
if idx != -1 {
ans = max(ans, i - idx)
}
idx = i
}
i++
}
return ans
}
3211. 生成不含相邻零的二进制字符串
func validStrings(n int) []string {
ans := make([]string, 0)
var dfs func (pos int, path []byte)
dfs = func (pos int, path []byte) {
if pos >= n {
ans = append(ans, string(path))
return
}
path[pos] = '1'
dfs(pos + 1, path)
if pos == 0 || path[pos-1] == '1' {
path[pos] = '0'
dfs(pos + 1, path)
}
}
dfs(0, make([]byte, n))
return ans
}
2917. 找出数组中的 K-or 值
func findKOr(nums []int, k int) int {
cnt := make([]int, 31)
for i := 0; i < 31; i++ {
for _, v := range nums {
if (v >> i) & 1 == 1 {
cnt[i]++
}
}
}
ans := 0
for i := 30; i >= 0; i-- {
if cnt[i] >= k {
fmt.Println(i)
ans |= 1
}
if i != 0 {
ans <<= 1
}
}
return ans
}
693. 交替位二进制数
func hasAlternatingBits(n int) bool {
t := n & 1
n >>= 1
for ; n > 0; n >>= 1 {
if t == n & 1 {
return false
}
t = n & 1
}
return true
}
2657. 找到两个数组的前缀公共数组
func findThePrefixCommonArray(A []int, B []int) []int {
var q, p uint
ans := make([]int, len(A))
for i := 0; i < len(A); i++ {
a, b := A[i], B[i]
q |= (1 << a)
p |= (1 << b)
ans[i] = bits.OnesCount(q & p)
}
return ans
}
231. 2 的幂
func isPowerOfTwo(n int) bool {
return bits.OnesCount(uint(n)) == 1
}