note4cs/技术/Go/Go实现BitMap.md

在 Go 语言中，`uint64` 是一种无符号整数类型，占用 64 位（bit）。每一位可以存储一个布尔值（0 或 1）。以下是 `bit` 和 `uint64` 之间的对应关系及操作的详细解释：

---

### 1. **`uint64` 的结构**
- 一个 `uint64` 类型的变量由 64 个二进制位组成，例如：
  ```
  00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  ```
  每一位从右到左编号为 0 到 63（最低位是第 0 位，最高位是第 63 位）。

---

### 2. **如何定位某个位**
假设我们要操作第 `pos` 位（从 0 开始计数），可以通过以下步骤确定其在 `uint64` 中的位置：

#### (1) **计算所在 `uint64` 的索引**
- 如果位图使用多个 `uint64` 来存储数据，则需要先确定目标位所在的 `uint64` 索引。
- 公式为：  
  ```go
  index = pos / 64
  ```
  - `pos / 64` 表示将位的位置除以 64，得到它属于哪个 `uint64`。

#### (2) **计算具体位偏移量**
- 在确定了目标 `uint64` 后，需要进一步确定该位在当前 `uint64` 中的具体位置。
- 公式为：  
  ```go
  offset = pos % 64
  ```
  - `pos % 64` 表示取余运算，得到目标位在当前 `uint64` 中的偏移量（范围为 0 到 63）。

---

### 3. **位操作的实现**
Go 语言提供了位运算符来操作单个位。以下是常见的位操作及其作用：

#### (1) **设置某一位为 1**
- 使用按位或运算符 `|` 和左移运算符 `<<`：
  ```go
  b.bits[pos/64] |= 1 << uint(pos%64)
  ```
  - `1 << uint(pos%64)`：将数字 `1` 左移 `offset` 位，生成一个只有目标位为 1 的掩码。
  - `|=`：将掩码与当前 `uint64` 值进行按位或运算，确保目标位被设置为 1。

#### (2) **清除某一位为 0**
- 使用按位与运算符 `&` 和按位取反运算符 `^`：
  ```go
  b.bits[pos/64] &^= 1 << uint(pos%64)
  ```
  - `1 << uint(pos%64)`：生成一个只有目标位为 1 的掩码。
  - `&^=`：将掩码取反后与当前 `uint64` 值进行按位与运算，确保目标位被清除为 0。

#### (3) **检查某一位是否为 1**
- 使用按位与运算符 `&`：
  ```go
  return b.bits[pos/64]&(1<<uint(pos%64)) != 0
  ```
  - `1 << uint(pos%64)`：生成一个只有目标位为 1 的掩码。
  - `&`：将掩码与当前 `uint64` 值进行按位与运算，结果非零表示目标位为 1，否则为 0。

---

### 4. **举例说明**
假设我们有一个 `uint64`，初始值为 `0`：
```
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
```

#### (1) 设置第 10 位为 1
- 计算索引和偏移量：
  - `index = 10 / 64 = 0`
  - `offset = 10 % 64 = 10`
- 执行操作：
  ```go
  bits[0] |= 1 << 10
  ```
  结果：
  ```
  00000000 00000000 00000000 00000000 00000000 00000000 00000100 00000000
  ```

#### (2) 清除第 10 位为 0
- 执行操作：
  ```go
  bits[0] &^= 1 << 10
  ```
  结果：
  ```
  00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  ```

#### (3) 检查第 10 位是否为 1
- 执行操作：
  ```go
  result := bits[0]&(1<<10) != 0
  ```
  - 如果第 10 位为 1，`result` 为 `true`。
  - 如果第 10 位为 0，`result` 为 `false`。

---

### 5. **总结**
- `uint64` 是一个 64 位的存储单元，每一位可以独立存储一个布尔值。
- 通过 `pos / 64` 确定目标位所在的 `uint64`，通过 `pos % 64` 确定目标位在当前 `uint64` 中的具体位置。
- 使用位运算符（如 `|`、`&`、`^` 和 `<<`）可以高效地操作单个位。

## 6.代码实现
~~~ go 
package main

import (
	"fmt"
)

// Bitmap 结构体表示位图
type Bitmap struct {
	bits []uint64 // 使用一个 uint64 切片存储位图数据，每个元素存储 64 位
	size int      // 位图的总大小（位数）
}

// NewBitmap 创建一个新的位图，size为位图的大小
func NewBitmap(size int) *Bitmap {
	if size < 0 {
		size = 0
	}
	return &Bitmap{
		bits: make([]uint64, (size+63)/64), // 根据位图大小计算需要的 uint64 元素数量
		size: size,                         // 记录位图的总大小
	}
}

// SetBit 设置指定位置的位为1
func (b *Bitmap) SetBit(pos int) {
	if pos < 0 || pos >= b.size { // 检查位置是否越界
		return
	}
	idx := pos / 64
	offset := pos % 64
	// 使用 uint64(1) 避免可能的整数溢出问题
	b.bits[idx] |= uint64(1) << offset
}

// ClearBit 清除指定位置的位为0
func (b *Bitmap) ClearBit(pos int) {
	if pos < 0 || pos >= b.size { // 检查位置是否越界
		return
	}
	idx := pos / 64
	offset := pos % 64
	// 使用 uint64(1) 避免可能的整数溢出问题
	b.bits[idx] &^= uint64(1) << offset
}

// GetBit 获取指定位置的位
func (b *Bitmap) GetBit(pos int) bool {
	if pos < 0 || pos >= b.size { // 检查位置是否越界
		return false
	}
	idx := pos / 64
	offset := pos % 64
	// 使用 uint64(1) 避免可能的整数溢出问题
	return (b.bits[idx] & (uint64(1) << offset)) != 0
}

func main() {
	// 创建一个大小为 100 的位图
	bitmap := NewBitmap(100)

	// 设置第 10 位为 1
	bitmap.SetBit(10)

	// 检查第 10 位是否为 1，并打印结果（输出 true）
	fmt.Println(bitmap.GetBit(10)) // 输出: true

	// 清除第 10 位为 0
	bitmap.ClearBit(10)

	// 再次检查第 10 位是否为 1，并打印结果（输出 false）
	fmt.Println(bitmap.GetBit(10)) // 输出: false
}

~~~