mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 09:23:19 +08:00
45 lines
1.1 KiB
Markdown
45 lines
1.1 KiB
Markdown
---
|
||
title: 2.15 ✅ Bit Manipulation
|
||
type: docs
|
||
weight: 15
|
||
---
|
||
|
||
# Bit Manipulation
|
||
|
||
|
||
|
||
- 异或的特性。第 136 题，第 268 题，第 389 题，第 421 题，
|
||
|
||
```go
|
||
x ^ 0 = x
|
||
x ^ 11111……1111 = ~x
|
||
x ^ (~x) = 11111……1111
|
||
x ^ x = 0
|
||
a ^ b = c => a ^ c = b => b ^ c = a (交换律)
|
||
a ^ b ^ c = a ^ (b ^ c) = (a ^ b）^ c (结合律)
|
||
```
|
||
|
||
- 构造特殊 Mask，将特殊位置放 0 或 1。
|
||
|
||
```go
|
||
将 x 最右边的 n 位清零， x & ( ~0 << n )
|
||
获取 x 的第 n 位值(0 或者 1)，(x >> n) & 1
|
||
获取 x 的第 n 位的幂值，x & (1 << (n - 1))
|
||
仅将第 n 位置为 1，x | (1 << n)
|
||
仅将第 n 位置为 0，x & (~(1 << n))
|
||
将 x 最高位至第 n 位(含)清零，x & ((1 << n) - 1)
|
||
将第 n 位至第 0 位(含)清零，x & (~((1 << (n + 1)) - 1)）
|
||
```
|
||
|
||
- 有特殊意义的 & 位操作运算。第 260 题，第 201 题，第 318 题，第 371 题，第 397 题，第 461 题，第 693 题，
|
||
|
||
```go
|
||
X & 1 == 1 判断是否是奇数(偶数)
|
||
X & = (X - 1) 将最低位(LSB)的 1 清零
|
||
X & -X 得到最低位(LSB)的 1
|
||
X & ~X = 0
|
||
```
|
||
|
||
|
||
|
||
{{.AvailableTagTable}} |