什么是 BitMap

BitMap 就是利用二进制位标志数值来存储数据,可以极大的节省存储空间。

举个栗子:比如我只有 1 byte(8 bit)的空间,我想对数字 3,5,1,4,7 这几个数字排序,该怎么做?

  • 初始化 1 byte(8 bit)的空间,并且把每个位都置为 0, 当前所有位为 00000000
  • 把 3 存进去,即把第 3 个 0 置为 1, 下标从右 0 开始,当前所有位为 00001000
  • 把 5 存进去,即把第 5 个 0 置为 1, 下标从右 0 开始,当前所有位为 00101000
  • 把 1 存进去,即把第 1 个 0 置为 1, 下标从右 0 开始,当前所有位为 00101010
  • 把 4 存进去,即把第 4 个 0 置为 1, 下标从右 0 开始,当前所有位为 00111010
  • 把 7 存进去,即把第 7 个 0 置为 1, 下标从右 0 开始,当前所有位为 10111010
  • 现在只需看 1 所在的位置即可得到排序好的数字 1,3,4,5,7

用程序来实现:

package main

import "fmt"

func bitMap(arr []uint8) uint8 {
	var bitMap uint8 = 0 // 初始化 bit 为为 0, `00000000`
	for _,v := range arr{
		var bitPos uint8 = 1 << v	 // 比如要把第 3 位置为1, 先写出二进制表达式 `00001000`
		bitMap |= bitPos // 按位或操作, 把指定位置为 1, `00000000 | 00001000 = 00001000`
	}
	return bitMap
}

func main() {
	arr := []uint8{3,5,1,4,7}
	bitMap := bitMap(arr)	// 结果 `10111010`

	var sorted []uint8
	var i uint8 = 0
	for i=0; i<8; i++ {
		var bitPos uint8 = 1 << i
		if bitMap & bitPos == bitPos {	// 按位与操作,判断当前为是否为 1, 比如判断第一位 `10111010 & 00000010 = 00000010`
			sorted = append(sorted, i)
		}
	}
	fmt.Println(sorted)
}