编程珠玑:如何使用位逻辑运算来实现位向量 - Swift

1,593 阅读3分钟

题目描述:使用二进制位来表示整数,比如将二进制位的第 9 位置为 1 来表示整数 9 。

二进制:10 0000 0000 代表 十进制:9

因为 Int 类型占用四个字节,共 32 位,如果每一位存储一个整数的话,则数组的第一个元素可以表示: 1~32,第二个元素可以表示:33~64 ...以此类推。

首先定义一下要使用的变量,假设我们需要存储 1亿 以内的整数 :

let bits = 32 // Int 占用 4 个字节,一共 32 位
let shift = 5 // 32 为 2 的 5 次方,即偏移量为 5
let mask = 31 
let n = 10_000_000
var nums = Array(repeating: 0, count: 1 + n / bits)

添加函数

接下来我们看一下添加函数。该函数需要以下的三步:

  • 1)计算出当前整数在数组中的索引
  • 2)计算出 2 的当前整数的次方
  • 3)将第 2 步中得出的值再或上数组中当前索引存储的值,将结果存入数组即可

下面来详细说一下上面的三步:

计算出当前整数在数组中的索引

以十进制整数 45 举例。下面是计算 45 的索引代码:

let index = 45 >> shift // 等价于 45 / 32 

上述代码计算得出 45 的索引为 1 ,即 index = 1。计算出索引之后要计算在该索引存储的具体值。

计算出 2 的当前整数的次方

以 45 来举例:

let power = 1 << (45 & mask) // 相当与求 2 的 45 次方

将第 2 步中得出的值再或上数组中当前索引存储的值,将结果存入数组

let oldValue = nums[index]
let newValue = oldValue | power
nums[index] = newValue

采用或的方式是因为这样不会影响上次存储的值,因为上次存储的值已将相应位置为 1 。

完整的添加函数:

func set(_ newElement: Int) {
    let index = newElement >> shift
    let power = 1 << (newElement & mask)
    let oldValue = nums[index]
    let newValue = oldValue | power
    nums[index] = newValue
}

移除函数

移除函数共需要三步:

  • 1)计算索引(同上)
  • 2)计算出 2 的当前整数的次方,然后取反
  • 3)将第 2 步中得出的值再与上数组中当前索引存储的值,将结果存入数组

计算出 2 的当前整数的次方,取反

let power = 1 << (element & mask)
let negation = ~power
let oldValue = nums[index]
let newValue = oldValue & negation
nums[index] = newValue

完整的移除函数:

func remove(_ element: Int) {
    let index = element >> shift
    let power = 1 << (element & mask)
    let negation = ~power
    let oldValue = nums[index]
    let newValue = oldValue & negation
    nums[index] = newValue
}

获取函数

获取函数共需要三步:

  • 1)计算索引(同上)
  • 2)计算出 2 的当前整数的次方(同上)
  • 3)将第 2 步中得出的值再与上数组中当前索引存储的值,返回结果

完整代码:

func get(_ element: Int) -> Int {
    let index = element >> shift
    let value = 1 << (element & mask)
    return nums[index] & value
}

测试代码

set(30)
print(nums[0]) // 2 的 30 次方 1073741824
print(get(30)) // 1073741824
remove(30)
print(get(30)) // 0

易读版完整代码:

func set(_ newElement: Int) {
    let index = newElement >> shift
    let power = 1 << (newElement & mask)
    let oldValue = nums[index]
    let newValue = oldValue | power
    nums[index] = newValue
}

func remove(_ element: Int) {
    let index = element >> shift
    let power = 1 << (element & mask)
    let negation = ~power
    let oldValue = nums[index]
    let newValue = oldValue & negation
    nums[index] = newValue
}

func get(_ element: Int) -> Int {
    let index = element >> shift
    let value = 1 << (element & mask)
    return nums[index] & value
}

下面的代码版本为简易版本(个人感觉不太易读):

func set(_ newElement: Int) {
    let index = newElement >> shift
    let curNum = nums[index]
    nums[index] = curNum | (1 << (newElement & mask))
}

func remove(_ element: Int) {
    let index = element >> shift
    nums[index] &= ~(1 << (element & mask))
}

func get(_ element: Int) -> Int {
    let index = element >> shift
    return nums[index] & (1 << (element & mask))
}