位图（位集）：求解《2166. 设计位集》

位集

位集 Bitset 紧凑形式存储位的数据结构

例题

2166. 设计位集

位集 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 位一致。

答案

var Bitset = function(size) {
  this.ar = new Uint8Array(size)
  this.reversed = 0
  this.countOne = 0
};

Bitset.prototype.fix = function(idx) {
  if (this.ar[idx] ^ this.reversed === 0) {
    this.ar[idx] ^= 1
    this.countOne++
  }
};

Bitset.prototype.unfix = function(idx) {
  if (this.ar[idx] ^ this.reversed === 1) {
    this.ar[idx] ^= 1
    this.countOne--
  }
};

Bitset.prototype.flip = function() {
  this.reversed ^= 1
  this.countOne = this.ar.length - this.countOne
};

Bitset.prototype.all = function() {
  return this.countOne === this.ar.length
};

Bitset.prototype.one = function() {
  return this.countOne >= 1
};

Bitset.prototype.count = function() {
  return this.countOne
};

Bitset.prototype.toString = function() {
  return this.ar.reduce((sum, v) => sum += v ^ this.reversed, '')
};

type Bitset struct {
  ar []byte
  countOne int
  reversed byte
  size int
}

func Constructor(size int) Bitset {
  return Bitset {
    ar: make([]byte, size),
    countOne: 0,
    reversed: 0,
    size: size,
  }
}

func (this *Bitset) Fix(idx int)  {
  if this.ar[idx] ^ this.reversed == 0 {
    this.ar[idx] ^= 1
    this.countOne++
  }
}

func (this *Bitset) Unfix(idx int)  {
  if this.ar[idx] ^ this.reversed == 1 {
    this.ar[idx] ^= 1
    this.countOne--
  }
}

func (this *Bitset) Flip()  {
  this.reversed ^= 1
  this.countOne = this.size - this.countOne
}

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

func (this *Bitset) One() bool {
  return this.countOne >= 1
}

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

func (this *Bitset) ToString() string {
  r := make([]byte, this.size)
  for i, ch := range this.ar {
    if this.reversed == 1 {
      if ch == 0 {
        r[i] = '1'
      } else {
        r[i] = '0'
      }
    } else {
      if ch == 1 {
        r[i] = '1'
      } else {
        r[i] = '0'
      }
    }
  }
  return string(r)
}