使用位逻辑运算实现位向量

@Daniate  March 12, 2022

使用位逻辑运算实现位向量

本文首发于Daniate的个人网站,文章链接:https://daniate.com/archives/213/

解答《编程珠玑》中相关习题时的一些思考。

假定,我们需要使用X个类型为type的整数来创建一个至少包含N个比特位的位向量,那么,计算出的X就是:

int X = (int)ceil(N * 1.0 / (sizeof(type) * 8))

通过这些整数,形成一个数组,就能构建出了我们需要的位向量:

type bit_vector[X]

如果要对索引位置为i的比特位进行操作,就需要知道该比特位是哪个整数中的哪个比特位,因此需要处理两个小任务:

  1. 查找整数
  2. 查找整数中的比特位

16371209477144.jpg

查找整数

查找整数,也即定位到该比特位所在的整数。

很明显,该整数在bit_vector中的索引N为:i / st,也即i >> log2(st)

这里,我们将log2(st)记为shift

shift = log2(st)

因此,N = i >> shift

使用不同的整数类型时,所对应的shift如下:

整数类型shift
uint8_t3
uint16_t4
uint32_t5
uint64_t6

查找整数中的比特位

该比特位在整数bit_vector[N]中的索引是i % st,也即i - (i / st * st),使用位逻辑运算就是i - ((i >> log2(st)) << log2(st)),也即i - ((i >> shift) << shift)

其中的(i >> shift) << shift,也就是将i的低shift位,置为0。示例:

16370306722349.gif

所以,i - ((i >> shift) << shift)就表示保留i的低shift位的值。示例:

16371298360824.jpg

使用位逻辑运算实现低shift位的保留时,我们需要用到一个低shift位均为1而其他位均为0的整数,让其与i进行&运算。

shift位均为1而其他位均为0的整数,也即((1 << shift) - 1),我们将其记为mask

mask = ((1 << shift) - 1)

16371307436761.jpg

使用mask实现低位保留:

16371301658599.jpg

前面提到shift = log2(st),因此((1 << shift) - 1)就是st - 1

使用不同的整数类型时,所对应的mask如下:

整数类型mask
uint8_t7(0x07)
uint16_t15(0x0F)
uint32_t31(0x1F)
uint64_t63(0x3F)

最终,该比特位在整数bit_vector[i >> shift]中的索引i - ((i >> shift) << shift)可以用i & mask表示:

16370308979968.jpg

当对位向量中索引为i的比特位进行设置、清除、测试时,就可以用bit_vector[i >> shift](1 << (i & mask))进行位逻辑运算实现这些操作。

设置:

bit_vector[i >> shift] |= (1 << (i & mask))

清除:

bit_vector[i >> shift] &= ~(1 << (i & mask))

测试:

bit_vector[i >> shift] & (1 << (i & mask))

知识共享许可协议
本作品由Daniate采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。


添加新评论