Design bitset

Array Hash Table String Design

32.6% acceptance

Feb 23, 2026

612

A Bitset is a data structure that compactly stores bits. Implement the Bitset class: Bitset(int size) Initializes the Bitset with size bits, all of which are 0. void fix(int idx) Updates the value of the bit at idx to 1. void unfix(int idx) Updates the value of the bit at idx to 0. void flip() Flips the values of each bit. boolean all() Checks if all bits are 1. boolean one() Checks if at least one bit is 1. int count() Returns total number of bits with value 1. String toString() Returns the current composition of the Bitset.

Solution

Rust

Time O(1)

Space O(n)

LeetCode

solution.rs

pub struct Bitset {
  bits: Vec<bool>,
  flipped: bool,
  ones: usize,
  size: usize,
}

impl Bitset {
  pub fn new(size: i32) -> Self {
    let size = size as usize;
    Bitset {
      bits: vec![false; size],
      flipped: false,
      ones: 0,
      size,
    }
  }

  pub fn fix(&mut self, idx: i32) {
    let idx = idx as usize;
    // In flipped mode, bits[idx]=false means the logical value is 1
    let logical_val = if self.flipped { !self.bits[idx] } else { self.bits[idx] };
    if !logical_val {
      self.bits[idx] = !self.bits[idx];
      self.ones += 1;
    }
  }

  pub fn unfix(&mut self, idx: i32) {
    let idx = idx as usize;
    let logical_val = if self.flipped { !self.bits[idx] } else { self.bits[idx] };
    if logical_val {
      self.bits[idx] = !self.bits[idx];
      self.ones -= 1;
    }
  }

  pub fn flip(&mut self) {
    self.flipped = !self.flipped;
    self.ones = self.size - self.ones;
  }

  pub fn all(&self) -> bool {
    self.ones == self.size
  }

  pub fn one(&self) -> bool {
    self.ones > 0
  }

  pub fn count(&self) -> i32 {
    self.ones as i32
  }

  pub fn to_string(&self) -> String {
    (0..self.size)
      .map(|i| {
        let logical = if self.flipped { !self.bits[i] } else { self.bits[i] };
        if logical { '1' } else { '0' }
      })
      .collect()
  }
}