2022-04-24：位集 Bitset 是一种能以紧凑形式存储位的数据结构。请你实现 Bitset 类。 Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。

原创

福大大架构师每日一题

发布于 2022-04-24 21:47:37

2240

发布于 2022-04-24 21:47:37

文章被收录于专栏：福大大架构师每日一题

2022-04-24：位集 Bitset 是一种能以紧凑形式存储位的数据结构。

请你实现 Bitset 类。

Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。

void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变。

void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变。

void flip() 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然。

boolean all() 检查 Bitset 中每一位的值是否都是 1 。如果满足此条件，返回 true ；否则，返回 false 。

boolean one() 检查 Bitset 中是否至少一位的值是 1 。如果满足此条件，返回 true ；否则，返回 false 。

int count() 返回 Bitset 中值为 1 的位的总数。

String toString() 返回 Bitset 的当前组成情况。注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。

输入：

"Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"

[5, 3, 1, [], [], 0, [], [], 0, [], []]。

输出：

null, null, null, null, false, null, null, true, null, 2, "01010"。

力扣2166. 设计位集。

答案2022-04-24：

自然智慧即可。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
	bs := Constructor(5)
	bs.Fix(3)
	bs.Fix(1)
	bs.Flip()
	fmt.Println(bs.All())
	bs.Unfix(0)
	bs.Flip()
	fmt.Println(bs.One())
	bs.Unfix(0)
	fmt.Println(bs.Count())
	fmt.Println(bs.ToString())
}

type Bitset struct {
	bits    []int
	size    int
	zeros   int
	ones    int
	reverse bool
}

func Constructor(n int) Bitset {
	ans := Bitset{}
	ans.bits = make([]int, (n+31)/32)
	ans.size = n
	ans.zeros = n
	ans.ones = 0
	ans.reverse = false
	return ans
}

func (this *Bitset) Fix(idx int) {
	index := idx / 32
	bit := idx % 32
	if !this.reverse {
		if (this.bits[index] & (1 << bit)) == 0 {
			this.zeros--
			this.ones++
			this.bits[index] |= (1 << bit)
		}
	} else {
		if (this.bits[index] & (1 << bit)) != 0 {
			this.zeros--
			this.ones++
			this.bits[index] ^= (1 << bit)
		}
	}
}

func (this *Bitset) Unfix(idx int) {
	index := idx / 32
	bit := idx % 32
	if !this.reverse {
		if (this.bits[index] & (1 << bit)) != 0 {
			this.ones--
			this.zeros++
			this.bits[index] ^= (1 << bit)
		}
	} else {
		if (this.bits[index] & (1 << bit)) == 0 {
			this.ones--
			this.zeros++
			this.bits[index] |= (1 << bit)
		}
	}
}

func (this *Bitset) Flip() {
	this.reverse = !this.reverse
	tmp := this.zeros
	this.zeros = this.ones
	this.ones = tmp
}

func (this *Bitset) All() bool {
	return this.ones == this.size
}

func (this *Bitset) One() bool {
	return this.ones > 0
}

func (this *Bitset) Count() int {
	return this.ones
}

func (this *Bitset) ToString() string {
	builder := make([]byte, 0)
	for i := 0; i < this.size; i++ {
		status := this.bits[i/32] & (1 << (i % 32))
		if this.reverse {
			if status == 0 {
				builder = append(builder, '1')
			} else {
				builder = append(builder, '0')
			}
		} else {
			if status == 0 {
				builder = append(builder, '0')
			} else {
				builder = append(builder, '1')
			}
		}
	}
	return string(builder)
}

执行结果如下：