Struct BitSet 

pub struct BitSet {
    size: usize,
    bits: Vec<Block>,
}

Fields

size: usize

bits: Vec<Block>

Implementations

impl BitSet

pub fn new(size: usize) -> Self

Examples found in repository

crates/competitive/src/math/bit_matrix.rs (line 23)

    pub fn zeros(shape: (usize, usize)) -> Self {
        Self {
            shape,
            data: vec![BitSet::new(shape.1); shape.0],
        }
    }

    pub fn from_vec(data: Vec<BitSet>) -> Self {
        let shape = (data.len(), data.first().map_or(0, BitSet::len));
        assert!(data.iter().all(|row| row.len() == shape.1));
        Self { shape, data }
    }

    pub fn new_with(shape: (usize, usize), mut f: impl FnMut(usize, usize) -> bool) -> Self {
        let mut a = Self::zeros(shape);
        for (i, row) in a.data.iter_mut().enumerate() {
            for (w, word) in row.words_mut().iter_mut().enumerate() {
                for j in w * 64..shape.1.min((w + 1) * 64) {
                    *word |= u64::from(f(i, j)) << (j & 63);
                }
            }
        }
        a
    }

    pub fn eye(shape: (usize, usize)) -> Self {
        let mut a = Self::zeros(shape);
        for i in 0..shape.0.min(shape.1) {
            a[i].set(i, true);
        }
        a
    }

    pub fn transpose(&self) -> Self {
        let mut a = Self::zeros((self.shape.1, self.shape.0));
        for (i, row) in self.data.iter().enumerate() {
            for j in row.iter_ones() {
                a[j].set(i, true);
            }
        }
        a
    }

    /// Replaces the matrix with reduced row echelon form and returns its pivot columns.
    pub fn row_reduction(&mut self) -> Vec<usize> {
        self.eliminate(self.shape.1, true, false)
    }

    /// Replaces the matrix with row echelon form and returns its rank.
    pub fn rank(&mut self) -> usize {
        self.eliminate(self.shape.1, false, false).len()
    }

    /// Computes the determinant in place. The matrix must be square.
    pub fn determinant(&mut self) -> bool {
        assert_eq!(self.shape.0, self.shape.1);
        self.eliminate(self.shape.1, false, true).len() == self.shape.0
    }

    /// Returns the inverse, or `None` if singular. The matrix must be square.
    pub fn inverse(&self) -> Option<Self> {
        let (n, m) = self.shape;
        assert_eq!(n, m);
        let mut a = Self::zeros((n, 2 * n));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(n + i, true);
        }
        if a.eliminate(n, true, true).len() != n {
            return None;
        }
        for row in &mut a.data {
            *row >>= n;
        }
        let mut inverse = Self::zeros((n, n));
        for (row, source) in inverse.data.iter_mut().zip(&a.data) {
            let len = row.words().len();
            row.words_mut().copy_from_slice(&source.words()[..len]);
        }
        Some(inverse)
    }

    /// Returns a particular solution and a basis of the kernel, or `None` if inconsistent.
    /// `b.len()` must equal the number of rows.
    pub fn solve_system_of_linear_equations(&self, b: &BitSet) -> Option<BitMatrixSolution> {
        let (n, m) = self.shape;
        assert_eq!(b.len(), n);
        let mut a = Self::zeros((n, m + 1));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(m, b.get(i));
        }
        let pivots = a.eliminate(m, true, false);
        if a.data[pivots.len()..].iter().any(|row| row.get(m)) {
            return None;
        }
        let mut particular = BitSet::new(m);
        let mut free = BitSet::ones(m);
        for (i, &c) in pivots.iter().enumerate() {
            particular.set(c, a[i].get(m));
            free.set(c, false);
        }
        let columns: Vec<_> = free.iter_ones().collect();
        let mut basis: Vec<_> = columns
            .iter()
            .map(|&c| {
                let mut row = BitSet::new(m);
                row.set(c, true);
                row
            })
            .collect();
        for (i, &p) in pivots.iter().enumerate() {
            for (row, &c) in basis.iter_mut().zip(&columns) {
                row.words_mut()[p / 64] |= u64::from(a[i].get(c)) << (p & 63);
            }
        }
        Some(BitMatrixSolution { particular, basis })
    }

    pub fn pow(self, mut n: usize) -> Self {
        assert_eq!(self.shape.0, self.shape.1);
        let mut result = Self::eye(self.shape);
        let mut a = self;
        while n != 0 {
            if n & 1 != 0 {
                result = &result * &a;
            }
            n >>= 1;
            if n != 0 {
                a = &a * &a;
            }
        }
        result
    }

    fn eliminate(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        #[cfg(target_arch = "x86_64")]
        match simd_backend() {
            // SAFETY: the dispatcher checks the required CPU features.
            SimdBackend::Avx512 => {
                return unsafe { self.eliminate_avx512(cols, full, require_full_rank) };
            }
            // SAFETY: the dispatcher checks AVX2 support.
            SimdBackend::Avx2 => {
                return unsafe { self.eliminate_avx2(cols, full, require_full_rank) };
            }
            SimdBackend::Scalar => {}
        }
        self.eliminate_impl(cols, full, require_full_rank)
    }

    // Inlined into each target-feature entry point to vectorize the row operations.
    #[inline(always)]
    fn eliminate_impl(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut pivots = Vec::with_capacity(n.min(cols));
        if n < 32 {
            let mut c = 0;
            while c < cols {
                let r = pivots.len();
                if r == n {
                    break;
                }
                let Some(p) = (r..n).find(|&i| self[i].get(c)) else {
                    if require_full_rank {
                        return pivots;
                    }
                    c = self.next_column(r, c + 1, cols);
                    continue;
                };
                self.data.swap(r, p);
                let (upper, lower) = self.data.split_at_mut(r);
                let (pivot, lower) = lower.split_first_mut().unwrap();
                for row in lower
                    .iter_mut()
                    .chain(upper.iter_mut().take(if full { r } else { 0 }))
                {
                    if row.get(c) {
                        xor(&mut row.words_mut()[c / 64..], &pivot.words()[c / 64..]);
                    }
                }
                pivots.push(c);
                c += 1;
            }
            return pivots;
        }
        // Eliminating a shared leading coefficient preserves the two-coefficient bound.
        if self
            .data
            .iter()
            .all(|row| row.iter_ones().take_while(|&c| c < cols).take(3).count() <= 2)
        {
            return self.eliminate_sparse(cols, full, require_full_rank);
        }
        let block: usize = if n < 512 {
            4
        } else if n < 1536 {
            8
        } else {
            32
        };
        let mut table = vec![BitSet::new(self.shape.1); (1 << block.min(8)) * block.div_ceil(8)];
        let mut reduced = vec![0; n];
        let mut start = 0;
        while start < cols {
            let first = pivots.len();
            let word = start / 64;
            reduced.fill(first);
            let end = cols.min(start + block);
            let mut c = start;
            while c < end {
                let r = pivots.len();
                let mut pivot = None;
                for (i, reduced) in reduced.iter_mut().enumerate().skip(r) {
                    let (upper, lower) = self.data.split_at_mut(i);
                    let row = &mut lower[0];
                    for p in *reduced..r {
                        if row.get(pivots[p]) {
                            xor(&mut row.words_mut()[word..], &upper[p].words()[word..]);
                        }
                    }
                    *reduced = r;
                    if row.get(c) {
                        pivot = Some(i);
                        break;
                    }
                }
                if let Some(p) = pivot {
                    self.data.swap(r, p);
                    reduced.swap(r, p);
                    pivots.push(c);
                    c += 1;
                } else if require_full_rank {
                    return pivots;
                } else {
                    c = self.next_column(r, c + 1, end);
                }
            }
            let rank = pivots.len();
            if first == rank {
                let next = self.next_column(rank, start + block, cols);
                if next == cols {
                    break;
                }
                start = next / block * block;
                continue;
            }
            // Make the panel's pivot columns an identity matrix before indexing its table.
            for r in (first..rank).rev() {
                let (upper, lower) = self.data.split_at_mut(r);
                for row in &mut upper[first..] {
                    if row.get(pivots[r]) {
                        xor(&mut row.words_mut()[word..], &lower[0].words()[word..]);
                    }
                }
            }
            let mut indices = [[0usize; 256]; 4];
            let mut masks = [0usize; 4];
            for group in 0..block.div_ceil(8) {
                let mut keys = [0usize; 256];
                let mut count = 0;
                for (row, &c) in pivots[first..].iter().enumerate() {
                    if (c - start) / 8 != group {
                        continue;
                    }
                    let half = 1 << count;
                    count += 1;
                    for index in 0..half {
                        keys[index + half] = keys[index] | (1 << ((c - start) % 8));
                        let (lower, upper) = table.split_at_mut(group * 256 + index + half);
                        let target = &mut upper[0].words_mut()[word..];
                        let source = &lower[group * 256 + index].words()[word..];
                        let pivot = &self[first + row].words()[word..];
                        for ((x, y), z) in target.iter_mut().zip(source).zip(pivot) {
                            *x = y ^ z;
                        }
                    }
                }
                masks[group] = keys[(1 << count) - 1];
                for (i, &key) in keys[..1 << count].iter().enumerate() {
                    indices[group][key] = i;
                }
            }
            for i in (rank..n).chain(0..if full { first } else { 0 }) {
                let key = (self[i].words()[word] >> (start & 63)) as usize;
                let x = indices[0][key & masks[0]];
                if block <= 8 {
                    if x != 0 {
                        xor(&mut self[i].words_mut()[word..], &table[x].words()[word..]);
                    }
                    continue;
                }
                let y = indices[1][(key >> 8) & masks[1]];
                let z = indices[2][(key >> 16) & masks[2]];
                let w = indices[3][(key >> 24) & masks[3]];
                if x | y | z | w != 0 {
                    let p = &table[x].words()[word..];
                    let q = &table[256 + y].words()[word..];
                    let r = &table[512 + z].words()[word..];
                    let s = &table[768 + w].words()[word..];
                    for ((((x, y), z), r), s) in self[i].words_mut()[word..]
                        .iter_mut()
                        .zip(p)
                        .zip(q)
                        .zip(r)
                        .zip(s)
                    {
                        *x ^= y ^ z ^ r ^ s;
                    }
                }
            }
            if rank == n {
                break;
            }
            start += block;
        }
        pivots
    }

    fn next_column(&self, row: usize, mut start: usize, cols: usize) -> usize {
        while start < cols {
            let word = start / 64;
            let bits = self.data[row..]
                .iter()
                .fold(0, |x, row| x | row.words()[word])
                & (u64::MAX << (start & 63));
            if bits != 0 {
                return (word * 64 + bits.trailing_zeros() as usize).min(cols);
            }
            start = (word + 1) * 64;
        }
        cols
    }

    #[inline(always)]
    fn eliminate_sparse(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut basis = vec![n; cols];
        let mut pivots = Vec::new();
        for i in 0..n {
            loop {
                let Some(c) = self[i].iter_ones().next().filter(|&c| c < cols) else {
                    if require_full_rank {
                        return pivots;
                    }
                    break;
                };
                if basis[c] == n {
                    basis[c] = i;
                    pivots.push(c);
                    break;
                }
                let (upper, lower) = self.data.split_at_mut(i);
                xor(
                    &mut lower[0].words_mut()[c / 64..],
                    &upper[basis[c]].words()[c / 64..],
                );
            }
        }
        pivots.sort_unstable();
        self.data
            .sort_by_cached_key(|row| row.iter_ones().next().filter(|&c| c < cols).unwrap_or(cols));
        if full {
            for (i, &c) in pivots.iter().enumerate() {
                basis[c] = i;
            }
            for i in (0..pivots.len()).rev() {
                let next = self[i].iter_ones().take_while(|&c| c < cols).nth(1);
                if let Some(c) = next
                    && basis[c] != n
                {
                    let (upper, lower) = self.data.split_at_mut(basis[c]);
                    xor(
                        &mut upper[i].words_mut()[c / 64..],
                        &lower[0].words()[c / 64..],
                    );
                }
            }
        }
        pivots
    }

    #[inline(always)]
    fn mul_impl(&self, rhs: &Self) -> Self {
        let mut result = Self::zeros((self.shape.0, rhs.shape.1));
        let ones = self.data.iter().map(BitSet::count_ones).sum::<u64>();
        let size = self.shape.0 as u64 * self.shape.1 as u64;
        if self.shape.0 < 256 || self.shape.1 < 32 || ones <= size / 8 {
            for (a, c) in self.data.iter().zip(&mut result.data) {
                for j in a.iter_ones() {
                    xor(c.words_mut(), rhs[j].words());
                }
            }
            return result;
        }
        if size - ones <= size / 8 {
            let mut sum = BitSet::new(rhs.shape.1);
            for row in &rhs.data {
                sum ^= row;
            }
            for (a, c) in self.data.iter().zip(&mut result.data) {
                c.words_mut().copy_from_slice(sum.words());
                for j in (!a.clone()).iter_ones() {
                    xor(c.words_mut(), rhs[j].words());
                }
            }
            return result;
        }
        let width = rhs.shape.1.div_ceil(64);
        if width == 0 {
            return result;
        }

        // Separate the table groups by a cache line to avoid mapping them to the same sets.
        let group = 256 * width + 8;
        let mut storage = BitSet::new(8 * group * 64);
        let table = storage.words_mut();
        for start in (0..self.shape.1).step_by(64) {
            for (t, table) in table.chunks_exact_mut(group).enumerate() {
                let col = start + t * 8;
                for bit in 0..self.shape.1.saturating_sub(col).min(8) {
                    let row = rhs[col + bit].words();
                    let half = (1 << bit) * width;
                    let (lower, upper) = table.split_at_mut(half);
                    for (source, dest) in
                        lower.chunks_exact(width).zip(upper.chunks_exact_mut(width))
                    {
                        for ((x, y), z) in dest.iter_mut().zip(source).zip(row) {
                            *x = y ^ z;
                        }
                    }
                }
            }
            for (a, c) in self.data.iter().zip(&mut result.data) {
                let key = a.words()[start / 64];
                let offset = (key & 255) as usize * width;
                let p0 = &table[offset..offset + width];
                let offset = group + (key >> 8 & 255) as usize * width;
                let p1 = &table[offset..offset + width];
                let offset = 2 * group + (key >> 16 & 255) as usize * width;
                let p2 = &table[offset..offset + width];
                let offset = 3 * group + (key >> 24 & 255) as usize * width;
                let p3 = &table[offset..offset + width];
                let offset = 4 * group + (key >> 32 & 255) as usize * width;
                let p4 = &table[offset..offset + width];
                let offset = 5 * group + (key >> 40 & 255) as usize * width;
                let p5 = &table[offset..offset + width];
                let offset = 6 * group + (key >> 48 & 255) as usize * width;
                let p6 = &table[offset..offset + width];
                let offset = 7 * group + (key >> 56 & 255) as usize * width;
                let p7 = &table[offset..offset + width];
                for ((((((((x, p0), p1), p2), p3), p4), p5), p6), p7) in c
                    .words_mut()
                    .iter_mut()
                    .zip(p0)
                    .zip(p1)
                    .zip(p2)
                    .zip(p3)
                    .zip(p4)
                    .zip(p5)
                    .zip(p6)
                    .zip(p7)
                {
                    *x ^= p0 ^ p1 ^ p2 ^ p3 ^ p4 ^ p5 ^ p6 ^ p7;
                }
            }
        }
        result
    }

crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 13)

    pub fn new(size: usize) -> Self {
        let mut dp = BitSet::new(if size == !0 { 0 } else { size } + 1);
        dp.set(0, true);
        Self {
            size,
            dp,
            pending_weights: vec![],
        }
    }

crates/competitive/src/data_structure/bitset.rs (line 47)

    pub fn from_binary(s: &str) -> Option<Self> {
        let bytes = s.as_bytes();
        let mut bits = Self::new(bytes.len());
        let end = bytes.len() / 64 * 64;
        #[cfg(target_arch = "x86_64")]
        let parsed = if avx512_enabled() && is_x86_feature_detected!("avx512bw") {
            // SAFETY: AVX-512BW is available; each complete chunk contains 64 bytes.
            unsafe { simd::parse_binary_avx512(&bytes[..end], bits.words_mut()) }
        } else if is_x86_feature_detected!("avx2") {
            // SAFETY: AVX2 is available; each complete chunk contains 64 bytes.
            unsafe { simd::parse_binary_avx2(&bytes[..end], bits.words_mut()) }
        } else {
            Self::parse_binary_scalar(&bytes[..end], bits.words_mut())
        };
        #[cfg(not(target_arch = "x86_64"))]
        let parsed = Self::parse_binary_scalar(&bytes[..end], bits.words_mut());
        if !parsed {
            return None;
        }
        if end != bytes.len() {
            let mut word = 0;
            for (i, &b) in bytes[end..].iter().enumerate() {
                if b != b'0' && b != b'1' {
                    return None;
                }
                word |= u64::from(b & 1) << i;
            }
            bits.words_mut()[end / 64] = word;
        }
        Some(bits)
    }

    fn parse_binary_scalar(bytes: &[u8], words: &mut [u64]) -> bool {
        for (chunk, word) in bytes.as_chunks::<64>().0.iter().zip(words) {
            for (i, byte) in chunk.as_chunks::<8>().0.iter().enumerate() {
                let x = u64::from_le_bytes(*byte);
                if x & 0xfefe_fefe_fefe_fefe != 0x3030_3030_3030_3030 {
                    return false;
                }
                *word |= ((x & 0x0101_0101_0101_0101).wrapping_mul(0x0102_0408_1020_4080) >> 56)
                    << (i * 8);
            }
        }
        true
    }

    /// Returns ASCII `0` and `1` in increasing bit-index order.
    pub fn to_binary(&self) -> String {
        const TABLE: [[u8; 8]; 256] = {
            let mut table = [[b'0'; 8]; 256];
            let mut i = 0;
            while i < 256 {
                let mut j = 0;
                while j < 8 {
                    table[i][j] |= ((i >> j) & 1) as u8;
                    j += 1;
                }
                i += 1;
            }
            table
        };
        let mut bytes = vec![b'0'; self.size.div_ceil(8) * 8];
        #[cfg(target_arch = "x86_64")]
        let end = if self.size >= 64 && avx512_enabled() && is_x86_feature_detected!("avx512bw") {
            let end = self.size / 64 * 64;
            // SAFETY: AVX-512BW is available; each output chunk holds one 64-bit word.
            unsafe {
                simd::write_binary_avx512(&mut bytes[..end], self.words());
            }
            end
        } else if self.size >= 64 && is_x86_feature_detected!("avx2") {
            let end = self.size / 64 * 64;
            // SAFETY: AVX2 is available; each output chunk holds one complete 64-bit word.
            unsafe {
                simd::write_binary_avx2(&mut bytes[..end], self.words());
            }
            end
        } else {
            0
        };
        #[cfg(not(target_arch = "x86_64"))]
        let end = 0;
        for (chunk, &word) in bytes[end..].chunks_mut(64).zip(&self.words()[end / 64..]) {
            for (i, byte) in chunk.as_chunks_mut::<8>().0.iter_mut().enumerate() {
                byte.copy_from_slice(&TABLE[(word >> (i * 8) & 255) as usize]);
            }
        }
        bytes.truncate(self.size);
        // SAFETY: every output byte is ASCII `0` or `1`.
        unsafe { String::from_utf8_unchecked(bytes) }
    }

    pub fn ones(size: usize) -> Self {
        let mut self_ = Self {
            size,
            bits: vec![Block([u64::MAX; 8]); size.div_ceil(512)],
        };
        self_.trim();
        self_
    }

    pub fn get(&self, i: usize) -> bool {
        self.bits[i >> 9].0[i >> 6 & 7] & (1 << (i & 63)) != 0
    }

    pub fn set(&mut self, i: usize, b: bool) {
        let word = &mut self.bits[i >> 9].0[i >> 6 & 7];
        if b {
            *word |= 1 << (i & 63);
        } else {
            *word &= !(1 << (i & 63));
        }
    }

    /// Clears all bits.
    pub fn reset(&mut self) {
        self.bits.fill(Block::default());
    }

    /// Sets all bits to `value`.
    pub fn fill(&mut self, value: bool) {
        self.bits.fill(Block([if value { u64::MAX } else { 0 }; 8]));
        self.trim();
    }

    /// Tests whether any bit is set.
    #[inline]
    pub fn any(&self) -> bool {
        !self.none()
    }

    /// Tests whether all bits are unset.
    #[inline]
    pub fn none(&self) -> bool {
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if self.bits[0].0[0] != 0 {
                return false;
            }
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                return unsafe { simd::none_avx512(&self.bits) };
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                return unsafe { simd::none_avx2(&self.bits) };
            }
        }
        self.words().iter().all(|&word| word == 0)
    }

    /// Tests whether all bits are set.
    #[inline(always)]
    pub fn all(&self) -> bool {
        let words = self.words();
        let full_words = self.size >> 6;
        #[cfg(target_arch = "x86_64")]
        if self.size >> 9 >= SIMD_MIN_BLOCKS {
            let full_blocks = self.size >> 9;
            if words[0] != u64::MAX {
                return false;
            }
            let full_blocks_are_set = if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                Some(unsafe { simd::all_avx512(&self.bits[..full_blocks]) })
            } else if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                Some(unsafe { simd::all_avx2(&self.bits[..full_blocks]) })
            } else {
                None
            };
            if let Some(full_blocks_are_set) = full_blocks_are_set {
                return full_blocks_are_set
                    && words[full_blocks * 8..full_words]
                        .iter()
                        .all(|&word| word == u64::MAX)
                    && (self.size & 63 == 0
                        || words[full_words] == u64::MAX >> (64 - (self.size & 63)));
            }
        }
        if self.size & 63 == 0 {
            return words.iter().all(|&word| word == u64::MAX);
        }
        words[..full_words].iter().all(|&word| word == u64::MAX)
            && words[full_words] == u64::MAX >> (64 - (self.size & 63))
    }

    /// Iterates over set-bit indices in ascending order.
    pub fn iter_ones(&self) -> impl Iterator<Item = usize> + '_ {
        self.words()
            .iter()
            .copied()
            .enumerate()
            .flat_map(|(word_index, mut word)| {
                std::iter::from_fn(move || {
                    if word == 0 {
                        None
                    } else {
                        let bit = word.trailing_zeros() as usize;
                        word &= word - 1;
                        Some((word_index << 6) | bit)
                    }
                })
            })
    }

    /// Counts set bits.
    #[inline]
    pub fn count_ones(&self) -> u64 {
        let words = self.words();
        #[cfg(target_arch = "x86_64")]
        if words.len() >= 8 {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vpopcntdq")
            {
                // SAFETY: blocks are aligned and feature detection checked both requirements.
                return unsafe { simd::count_ones_avx512(&self.bits) };
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                return unsafe { simd::count_ones_avx2(&self.bits) };
            }
        }
        words.iter().map(|word| word.count_ones() as u64).sum()
    }

    /// Counts unset bits.
    #[inline]
    pub fn count_zeros(&self) -> u64 {
        self.size as u64 - self.count_ones()
    }

    pub fn push(&mut self, b: bool) {
        if self.size & 511 == 0 {
            self.bits.push(Block::default());
        }
        if b {
            self.bits[self.size >> 9].0[self.size >> 6 & 7] |= 1 << (self.size & 63);
        }
        self.size += 1;
    }

    pub fn resize(&mut self, new_size: usize) {
        match self.size.cmp(&new_size) {
            Ordering::Less => self.bits.resize(new_size.div_ceil(512), Block::default()),
            Ordering::Equal => {}
            Ordering::Greater => self.bits.truncate(new_size.div_ceil(512)),
        }
        self.size = new_size;
        self.trim();
    }

    /// Assigns `self | (self << rhs)` to `self`.
    #[inline]
    pub fn shl_bitor_assign(&mut self, rhs: usize) {
        self.shift_left::<true>(rhs);
    }

    /// Assigns `self | (self >> rhs)` to `self`.
    #[inline]
    pub fn shr_bitor_assign(&mut self, rhs: usize) {
        self.shift_right::<true>(rhs);
    }

    /// Returns words in increasing bit-index order; unused high bits in the last word are zero.
    pub fn words(&self) -> &[u64] {
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts(self.bits.as_ptr().cast(), self.size.div_ceil(64)) }
    }

    /// Returns mutable words in increasing bit-index order.
    /// Callers must keep unused high bits in the last word zero.
    pub fn words_mut(&mut self) -> &mut [u64] {
        let len = self.size.div_ceil(64);
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts_mut(self.bits.as_mut_ptr().cast(), len) }
    }

    fn trim(&mut self) {
        let used_words = self.size.div_ceil(64) & 7;
        if let Some(last) = self.bits.last_mut() {
            if self.size & 63 != 0 {
                last.0[(self.size >> 6) & 7] &= u64::MAX >> (64 - (self.size & 63));
            }
            if used_words != 0 {
                last.0[used_words..].fill(0);
            }
        }
    }

    #[inline]
    fn bitop_assign<const OP: u8>(&mut self, rhs: &Self) {
        assert_eq!(
            self.size, rhs.size,
            "bitwise operations require equal lengths"
        );
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                unsafe { simd::bitop_avx512::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                unsafe { simd::bitop_avx2::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
        }
        for (lhs, &rhs) in self.words_mut().iter_mut().zip(rhs.words()) {
            *lhs = match OP {
                BIT_AND => *lhs & rhs,
                BIT_OR => *lhs | rhs,
                BIT_XOR => *lhs ^ rhs,
                _ => unreachable!(),
            };
        }
    }

    #[inline]
    fn shift_left<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_left_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                if self.size & 511 != 0 {
                    self.trim();
                }
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_left_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                if self.size & 63 != 0 {
                    self.trim();
                }
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in (0..bits.len() - word_shift).rev() {
                if OR_ASSIGN {
                    bits[i + word_shift] |= bits[i];
                } else {
                    bits[i + word_shift] = bits[i];
                }
            }
        } else {
            for i in (1..bits.len() - word_shift).rev() {
                let value = (bits[i] << bit_shift) | (bits[i - 1] >> (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i + word_shift] |= value;
                } else {
                    bits[i + word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[word_shift] |= bits[0] << bit_shift;
            } else {
                bits[word_shift] = bits[0] << bit_shift;
            }
        }
        if !OR_ASSIGN {
            bits[..word_shift].fill(0);
        }
        if self.size & 63 != 0 {
            self.trim();
        }
    }

    #[inline]
    fn shift_right<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_right_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_right_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in word_shift..bits.len() {
                if OR_ASSIGN {
                    bits[i - word_shift] |= bits[i];
                } else {
                    bits[i - word_shift] = bits[i];
                }
            }
        } else {
            for i in word_shift..bits.len() - 1 {
                let value = (bits[i] >> bit_shift) | (bits[i + 1] << (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i - word_shift] |= value;
                } else {
                    bits[i - word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[bits.len() - word_shift - 1] |= bits[bits.len() - 1] >> bit_shift;
            } else {
                bits[bits.len() - word_shift - 1] = bits[bits.len() - 1] >> bit_shift;
            }
        }
        if !OR_ASSIGN {
            let end = bits.len() - word_shift;
            bits[end..].fill(0);
        }
    }
}

impl Extend<bool> for BitSet {
    fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T) {
        for bit in iter {
            self.push(bit);
        }
    }
}

impl FromIterator<bool> for BitSet {
    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
        let mut set = BitSet::new(0);
        set.extend(iter);
        set
    }

pub fn len(&self) -> usize

Examples found in repository

crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 40)

    pub fn contains(&mut self, sum: usize) -> bool {
        self.rebuild();
        if sum < self.dp.len() {
            self.dp.get(sum)
        } else {
            false
        }
    }

    fn rebuild(&mut self) {
        if self.pending_weights.is_empty() {
            return;
        }
        let mut heap = BinaryHeap::from(take(&mut self.pending_weights));
        let (mut current_weight, mut count) = match heap.pop() {
            Some(Reverse(w)) => (w, 1),
            None => return,
        };
        while let Some(Reverse(weight)) = heap.pop() {
            if weight == current_weight {
                count += 1;
                if count >= 3 {
                    if let Some(w) = current_weight.checked_mul(2) {
                        heap.push(Reverse(w));
                    }
                    count -= 2;
                }
                continue;
            }
            for _ in 0..count {
                if self.size == !0 {
                    self.dp.resize(self.dp.len() + current_weight);
                }
                self.dp.shl_bitor_assign(current_weight);
            }
            (current_weight, count) = (weight, 1);
        }
        for _ in 0..count {
            if self.size == !0 {
                self.dp.resize(self.dp.len() + current_weight);
            }
            self.dp.shl_bitor_assign(current_weight);
        }
    }

crates/competitive/src/math/bit_matrix.rs (line 29)

    pub fn from_vec(data: Vec<BitSet>) -> Self {
        let shape = (data.len(), data.first().map_or(0, BitSet::len));
        assert!(data.iter().all(|row| row.len() == shape.1));
        Self { shape, data }
    }

    pub fn new_with(shape: (usize, usize), mut f: impl FnMut(usize, usize) -> bool) -> Self {
        let mut a = Self::zeros(shape);
        for (i, row) in a.data.iter_mut().enumerate() {
            for (w, word) in row.words_mut().iter_mut().enumerate() {
                for j in w * 64..shape.1.min((w + 1) * 64) {
                    *word |= u64::from(f(i, j)) << (j & 63);
                }
            }
        }
        a
    }

    pub fn eye(shape: (usize, usize)) -> Self {
        let mut a = Self::zeros(shape);
        for i in 0..shape.0.min(shape.1) {
            a[i].set(i, true);
        }
        a
    }

    pub fn transpose(&self) -> Self {
        let mut a = Self::zeros((self.shape.1, self.shape.0));
        for (i, row) in self.data.iter().enumerate() {
            for j in row.iter_ones() {
                a[j].set(i, true);
            }
        }
        a
    }

    /// Replaces the matrix with reduced row echelon form and returns its pivot columns.
    pub fn row_reduction(&mut self) -> Vec<usize> {
        self.eliminate(self.shape.1, true, false)
    }

    /// Replaces the matrix with row echelon form and returns its rank.
    pub fn rank(&mut self) -> usize {
        self.eliminate(self.shape.1, false, false).len()
    }

    /// Computes the determinant in place. The matrix must be square.
    pub fn determinant(&mut self) -> bool {
        assert_eq!(self.shape.0, self.shape.1);
        self.eliminate(self.shape.1, false, true).len() == self.shape.0
    }

    /// Returns the inverse, or `None` if singular. The matrix must be square.
    pub fn inverse(&self) -> Option<Self> {
        let (n, m) = self.shape;
        assert_eq!(n, m);
        let mut a = Self::zeros((n, 2 * n));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(n + i, true);
        }
        if a.eliminate(n, true, true).len() != n {
            return None;
        }
        for row in &mut a.data {
            *row >>= n;
        }
        let mut inverse = Self::zeros((n, n));
        for (row, source) in inverse.data.iter_mut().zip(&a.data) {
            let len = row.words().len();
            row.words_mut().copy_from_slice(&source.words()[..len]);
        }
        Some(inverse)
    }

    /// Returns a particular solution and a basis of the kernel, or `None` if inconsistent.
    /// `b.len()` must equal the number of rows.
    pub fn solve_system_of_linear_equations(&self, b: &BitSet) -> Option<BitMatrixSolution> {
        let (n, m) = self.shape;
        assert_eq!(b.len(), n);
        let mut a = Self::zeros((n, m + 1));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(m, b.get(i));
        }
        let pivots = a.eliminate(m, true, false);
        if a.data[pivots.len()..].iter().any(|row| row.get(m)) {
            return None;
        }
        let mut particular = BitSet::new(m);
        let mut free = BitSet::ones(m);
        for (i, &c) in pivots.iter().enumerate() {
            particular.set(c, a[i].get(m));
            free.set(c, false);
        }
        let columns: Vec<_> = free.iter_ones().collect();
        let mut basis: Vec<_> = columns
            .iter()
            .map(|&c| {
                let mut row = BitSet::new(m);
                row.set(c, true);
                row
            })
            .collect();
        for (i, &p) in pivots.iter().enumerate() {
            for (row, &c) in basis.iter_mut().zip(&columns) {
                row.words_mut()[p / 64] |= u64::from(a[i].get(c)) << (p & 63);
            }
        }
        Some(BitMatrixSolution { particular, basis })
    }

pub fn is_empty(&self) -> bool

pub fn from_binary(s: &str) -> Option<Self>

Parses ASCII 0 and 1, with the first character at bit index zero. Returns None if any other character occurs.

Examples found in repository

crates/library_checker/src/linear_algebra/matrix_rank_mod_2.rs (line 29)

pub fn matrix_rank_mod_2(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m);
    // Transpose very tall matrices to avoid allocating millions of short rows.
    let transpose = n / 2 > m;
    let mut a = BitMatrix::zeros(if transpose { (m, n) } else { (n, m) });
    if transpose && m >= 64 {
        let mut words = vec![0u64; m];
        for first in (0..n).step_by(64) {
            words.fill(0);
            for i in 0..64.min(n - first) {
                sc!(row: &str);
                for (word, b) in words.iter_mut().zip(row.bytes()) {
                    *word |= u64::from(b == b'1') << i;
                }
            }
            for (row, &word) in a.data.iter_mut().zip(&words) {
                row.words_mut()[first / 64] = word;
            }
        }
    } else {
        for i in 0..if m == 0 { 0 } else { n } {
            sc!(row: &str);
            if !transpose {
                a.data[i] = BitSet::from_binary(row).unwrap();
            } else {
                for (j, b) in row.bytes().enumerate() {
                    a[j].words_mut()[i / 64] |= u64::from(b == b'1') << (i % 64);
                }
            }
            if transpose
                && i == 63
                && BitMatrix::new_with((m, 64), |row, col| a[row].get(col)).rank() == m
            {
                pp!(m);
                return;
            }
        }
    }
    pp!(a.rank());
}

fn parse_binary_scalar(bytes: &[u8], words: &mut [u64]) -> bool

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 57)

    pub fn from_binary(s: &str) -> Option<Self> {
        let bytes = s.as_bytes();
        let mut bits = Self::new(bytes.len());
        let end = bytes.len() / 64 * 64;
        #[cfg(target_arch = "x86_64")]
        let parsed = if avx512_enabled() && is_x86_feature_detected!("avx512bw") {
            // SAFETY: AVX-512BW is available; each complete chunk contains 64 bytes.
            unsafe { simd::parse_binary_avx512(&bytes[..end], bits.words_mut()) }
        } else if is_x86_feature_detected!("avx2") {
            // SAFETY: AVX2 is available; each complete chunk contains 64 bytes.
            unsafe { simd::parse_binary_avx2(&bytes[..end], bits.words_mut()) }
        } else {
            Self::parse_binary_scalar(&bytes[..end], bits.words_mut())
        };
        #[cfg(not(target_arch = "x86_64"))]
        let parsed = Self::parse_binary_scalar(&bytes[..end], bits.words_mut());
        if !parsed {
            return None;
        }
        if end != bytes.len() {
            let mut word = 0;
            for (i, &b) in bytes[end..].iter().enumerate() {
                if b != b'0' && b != b'1' {
                    return None;
                }
                word |= u64::from(b & 1) << i;
            }
            bits.words_mut()[end / 64] = word;
        }
        Some(bits)
    }

pub fn to_binary(&self) -> String

Returns ASCII 0 and 1 in increasing bit-index order.

Examples found in repository

crates/library_checker/src/linear_algebra/inverse_matrix_mod_2.rs (line 11)

pub fn inverse_matrix_mod_2(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, a: [@BitSet::from_binary; n]);
    let a = BitMatrix::from_vec(a);
    if let Some(b) = a.inverse() {
        for row in b.data {
            pp!(row.to_binary());
        }
    } else {
        pp!(-1);
    }
}

crates/library_checker/src/linear_algebra/matrix_product_mod_2.rs (line 12)

pub fn matrix_product_mod_2(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m, _k, a: [@BitSet::from_binary; n], b: [@BitSet::from_binary; m]);
    let a = BitMatrix::from_vec(a);
    let b = BitMatrix::from_vec(b);
    let c = &a * &b;
    for row in c.data {
        pp!(row.to_binary());
    }
}

crates/library_checker/src/linear_algebra/system_of_linear_equations_mod_2.rs (line 12)

pub fn system_of_linear_equations_mod_2(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, _m, a: [@BitSet::from_binary; n], b: @BitSet::from_binary);
    let a = BitMatrix::from_vec(a);
    if let Some(sol) = a.solve_system_of_linear_equations(&b) {
        pp!(sol.basis.len());
        for row in std::iter::once(sol.particular).chain(sol.basis) {
            pp!(row.to_binary());
        }
    } else {
        pp!(-1);
    }
}

pub fn ones(size: usize) -> Self

Examples found in repository

crates/competitive/src/math/bit_matrix.rs (line 117)

    pub fn solve_system_of_linear_equations(&self, b: &BitSet) -> Option<BitMatrixSolution> {
        let (n, m) = self.shape;
        assert_eq!(b.len(), n);
        let mut a = Self::zeros((n, m + 1));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(m, b.get(i));
        }
        let pivots = a.eliminate(m, true, false);
        if a.data[pivots.len()..].iter().any(|row| row.get(m)) {
            return None;
        }
        let mut particular = BitSet::new(m);
        let mut free = BitSet::ones(m);
        for (i, &c) in pivots.iter().enumerate() {
            particular.set(c, a[i].get(m));
            free.set(c, false);
        }
        let columns: Vec<_> = free.iter_ones().collect();
        let mut basis: Vec<_> = columns
            .iter()
            .map(|&c| {
                let mut row = BitSet::new(m);
                row.set(c, true);
                row
            })
            .collect();
        for (i, &p) in pivots.iter().enumerate() {
            for (row, &c) in basis.iter_mut().zip(&columns) {
                row.words_mut()[p / 64] |= u64::from(a[i].get(c)) << (p & 63);
            }
        }
        Some(BitMatrixSolution { particular, basis })
    }

pub fn get(&self, i: usize) -> bool

Examples found in repository

crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 41)

    pub fn contains(&mut self, sum: usize) -> bool {
        self.rebuild();
        if sum < self.dp.len() {
            self.dp.get(sum)
        } else {
            false
        }
    }

crates/competitive/src/algorithm/automata_learning.rs (line 372)

    pub fn construct_dfa(&mut self) -> DeterministicFiniteAutomaton {
        let sigma = self.automaton.sigma();
        let mut dfa = DeterministicFiniteAutomaton {
            states: vec![],
            initial_state: 0,
        };
        let mut i_prefix = 0;
        while i_prefix < self.prefixes.len() {
            let mut delta = vec![];
            for x in 0..sigma {
                let prefix: Vec<usize> =
                    self.prefixes[i_prefix].iter().cloned().chain([x]).collect();
                let index = self.add_prefix(prefix);
                delta.push(index);
            }
            dfa.states.push(DfaState {
                delta,
                accept: self.table[i_prefix].get(0),
            });
            i_prefix += 1;
        }
        dfa
    }

crates/competitive/src/math/bit_matrix.rs (line 110)

    pub fn solve_system_of_linear_equations(&self, b: &BitSet) -> Option<BitMatrixSolution> {
        let (n, m) = self.shape;
        assert_eq!(b.len(), n);
        let mut a = Self::zeros((n, m + 1));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(m, b.get(i));
        }
        let pivots = a.eliminate(m, true, false);
        if a.data[pivots.len()..].iter().any(|row| row.get(m)) {
            return None;
        }
        let mut particular = BitSet::new(m);
        let mut free = BitSet::ones(m);
        for (i, &c) in pivots.iter().enumerate() {
            particular.set(c, a[i].get(m));
            free.set(c, false);
        }
        let columns: Vec<_> = free.iter_ones().collect();
        let mut basis: Vec<_> = columns
            .iter()
            .map(|&c| {
                let mut row = BitSet::new(m);
                row.set(c, true);
                row
            })
            .collect();
        for (i, &p) in pivots.iter().enumerate() {
            for (row, &c) in basis.iter_mut().zip(&columns) {
                row.words_mut()[p / 64] |= u64::from(a[i].get(c)) << (p & 63);
            }
        }
        Some(BitMatrixSolution { particular, basis })
    }

    pub fn pow(self, mut n: usize) -> Self {
        assert_eq!(self.shape.0, self.shape.1);
        let mut result = Self::eye(self.shape);
        let mut a = self;
        while n != 0 {
            if n & 1 != 0 {
                result = &result * &a;
            }
            n >>= 1;
            if n != 0 {
                a = &a * &a;
            }
        }
        result
    }

    fn eliminate(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        #[cfg(target_arch = "x86_64")]
        match simd_backend() {
            // SAFETY: the dispatcher checks the required CPU features.
            SimdBackend::Avx512 => {
                return unsafe { self.eliminate_avx512(cols, full, require_full_rank) };
            }
            // SAFETY: the dispatcher checks AVX2 support.
            SimdBackend::Avx2 => {
                return unsafe { self.eliminate_avx2(cols, full, require_full_rank) };
            }
            SimdBackend::Scalar => {}
        }
        self.eliminate_impl(cols, full, require_full_rank)
    }

    // Inlined into each target-feature entry point to vectorize the row operations.
    #[inline(always)]
    fn eliminate_impl(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut pivots = Vec::with_capacity(n.min(cols));
        if n < 32 {
            let mut c = 0;
            while c < cols {
                let r = pivots.len();
                if r == n {
                    break;
                }
                let Some(p) = (r..n).find(|&i| self[i].get(c)) else {
                    if require_full_rank {
                        return pivots;
                    }
                    c = self.next_column(r, c + 1, cols);
                    continue;
                };
                self.data.swap(r, p);
                let (upper, lower) = self.data.split_at_mut(r);
                let (pivot, lower) = lower.split_first_mut().unwrap();
                for row in lower
                    .iter_mut()
                    .chain(upper.iter_mut().take(if full { r } else { 0 }))
                {
                    if row.get(c) {
                        xor(&mut row.words_mut()[c / 64..], &pivot.words()[c / 64..]);
                    }
                }
                pivots.push(c);
                c += 1;
            }
            return pivots;
        }
        // Eliminating a shared leading coefficient preserves the two-coefficient bound.
        if self
            .data
            .iter()
            .all(|row| row.iter_ones().take_while(|&c| c < cols).take(3).count() <= 2)
        {
            return self.eliminate_sparse(cols, full, require_full_rank);
        }
        let block: usize = if n < 512 {
            4
        } else if n < 1536 {
            8
        } else {
            32
        };
        let mut table = vec![BitSet::new(self.shape.1); (1 << block.min(8)) * block.div_ceil(8)];
        let mut reduced = vec![0; n];
        let mut start = 0;
        while start < cols {
            let first = pivots.len();
            let word = start / 64;
            reduced.fill(first);
            let end = cols.min(start + block);
            let mut c = start;
            while c < end {
                let r = pivots.len();
                let mut pivot = None;
                for (i, reduced) in reduced.iter_mut().enumerate().skip(r) {
                    let (upper, lower) = self.data.split_at_mut(i);
                    let row = &mut lower[0];
                    for p in *reduced..r {
                        if row.get(pivots[p]) {
                            xor(&mut row.words_mut()[word..], &upper[p].words()[word..]);
                        }
                    }
                    *reduced = r;
                    if row.get(c) {
                        pivot = Some(i);
                        break;
                    }
                }
                if let Some(p) = pivot {
                    self.data.swap(r, p);
                    reduced.swap(r, p);
                    pivots.push(c);
                    c += 1;
                } else if require_full_rank {
                    return pivots;
                } else {
                    c = self.next_column(r, c + 1, end);
                }
            }
            let rank = pivots.len();
            if first == rank {
                let next = self.next_column(rank, start + block, cols);
                if next == cols {
                    break;
                }
                start = next / block * block;
                continue;
            }
            // Make the panel's pivot columns an identity matrix before indexing its table.
            for r in (first..rank).rev() {
                let (upper, lower) = self.data.split_at_mut(r);
                for row in &mut upper[first..] {
                    if row.get(pivots[r]) {
                        xor(&mut row.words_mut()[word..], &lower[0].words()[word..]);
                    }
                }
            }
            let mut indices = [[0usize; 256]; 4];
            let mut masks = [0usize; 4];
            for group in 0..block.div_ceil(8) {
                let mut keys = [0usize; 256];
                let mut count = 0;
                for (row, &c) in pivots[first..].iter().enumerate() {
                    if (c - start) / 8 != group {
                        continue;
                    }
                    let half = 1 << count;
                    count += 1;
                    for index in 0..half {
                        keys[index + half] = keys[index] | (1 << ((c - start) % 8));
                        let (lower, upper) = table.split_at_mut(group * 256 + index + half);
                        let target = &mut upper[0].words_mut()[word..];
                        let source = &lower[group * 256 + index].words()[word..];
                        let pivot = &self[first + row].words()[word..];
                        for ((x, y), z) in target.iter_mut().zip(source).zip(pivot) {
                            *x = y ^ z;
                        }
                    }
                }
                masks[group] = keys[(1 << count) - 1];
                for (i, &key) in keys[..1 << count].iter().enumerate() {
                    indices[group][key] = i;
                }
            }
            for i in (rank..n).chain(0..if full { first } else { 0 }) {
                let key = (self[i].words()[word] >> (start & 63)) as usize;
                let x = indices[0][key & masks[0]];
                if block <= 8 {
                    if x != 0 {
                        xor(&mut self[i].words_mut()[word..], &table[x].words()[word..]);
                    }
                    continue;
                }
                let y = indices[1][(key >> 8) & masks[1]];
                let z = indices[2][(key >> 16) & masks[2]];
                let w = indices[3][(key >> 24) & masks[3]];
                if x | y | z | w != 0 {
                    let p = &table[x].words()[word..];
                    let q = &table[256 + y].words()[word..];
                    let r = &table[512 + z].words()[word..];
                    let s = &table[768 + w].words()[word..];
                    for ((((x, y), z), r), s) in self[i].words_mut()[word..]
                        .iter_mut()
                        .zip(p)
                        .zip(q)
                        .zip(r)
                        .zip(s)
                    {
                        *x ^= y ^ z ^ r ^ s;
                    }
                }
            }
            if rank == n {
                break;
            }
            start += block;
        }
        pivots
    }

crates/library_checker/src/linear_algebra/matrix_rank_mod_2.rs (line 37)

pub fn matrix_rank_mod_2(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m);
    // Transpose very tall matrices to avoid allocating millions of short rows.
    let transpose = n / 2 > m;
    let mut a = BitMatrix::zeros(if transpose { (m, n) } else { (n, m) });
    if transpose && m >= 64 {
        let mut words = vec![0u64; m];
        for first in (0..n).step_by(64) {
            words.fill(0);
            for i in 0..64.min(n - first) {
                sc!(row: &str);
                for (word, b) in words.iter_mut().zip(row.bytes()) {
                    *word |= u64::from(b == b'1') << i;
                }
            }
            for (row, &word) in a.data.iter_mut().zip(&words) {
                row.words_mut()[first / 64] = word;
            }
        }
    } else {
        for i in 0..if m == 0 { 0 } else { n } {
            sc!(row: &str);
            if !transpose {
                a.data[i] = BitSet::from_binary(row).unwrap();
            } else {
                for (j, b) in row.bytes().enumerate() {
                    a[j].words_mut()[i / 64] |= u64::from(b == b'1') << (i % 64);
                }
            }
            if transpose
                && i == 63
                && BitMatrix::new_with((m, 64), |row, col| a[row].get(col)).rank() == m
            {
                pp!(m);
                return;
            }
        }
    }
    pp!(a.rank());
}

pub fn set(&mut self, i: usize, b: bool)

Examples found in repository

crates/competitive/src/math/bit_matrix.rs (line 48)

    pub fn eye(shape: (usize, usize)) -> Self {
        let mut a = Self::zeros(shape);
        for i in 0..shape.0.min(shape.1) {
            a[i].set(i, true);
        }
        a
    }

    pub fn transpose(&self) -> Self {
        let mut a = Self::zeros((self.shape.1, self.shape.0));
        for (i, row) in self.data.iter().enumerate() {
            for j in row.iter_ones() {
                a[j].set(i, true);
            }
        }
        a
    }

    /// Replaces the matrix with reduced row echelon form and returns its pivot columns.
    pub fn row_reduction(&mut self) -> Vec<usize> {
        self.eliminate(self.shape.1, true, false)
    }

    /// Replaces the matrix with row echelon form and returns its rank.
    pub fn rank(&mut self) -> usize {
        self.eliminate(self.shape.1, false, false).len()
    }

    /// Computes the determinant in place. The matrix must be square.
    pub fn determinant(&mut self) -> bool {
        assert_eq!(self.shape.0, self.shape.1);
        self.eliminate(self.shape.1, false, true).len() == self.shape.0
    }

    /// Returns the inverse, or `None` if singular. The matrix must be square.
    pub fn inverse(&self) -> Option<Self> {
        let (n, m) = self.shape;
        assert_eq!(n, m);
        let mut a = Self::zeros((n, 2 * n));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(n + i, true);
        }
        if a.eliminate(n, true, true).len() != n {
            return None;
        }
        for row in &mut a.data {
            *row >>= n;
        }
        let mut inverse = Self::zeros((n, n));
        for (row, source) in inverse.data.iter_mut().zip(&a.data) {
            let len = row.words().len();
            row.words_mut().copy_from_slice(&source.words()[..len]);
        }
        Some(inverse)
    }

    /// Returns a particular solution and a basis of the kernel, or `None` if inconsistent.
    /// `b.len()` must equal the number of rows.
    pub fn solve_system_of_linear_equations(&self, b: &BitSet) -> Option<BitMatrixSolution> {
        let (n, m) = self.shape;
        assert_eq!(b.len(), n);
        let mut a = Self::zeros((n, m + 1));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(m, b.get(i));
        }
        let pivots = a.eliminate(m, true, false);
        if a.data[pivots.len()..].iter().any(|row| row.get(m)) {
            return None;
        }
        let mut particular = BitSet::new(m);
        let mut free = BitSet::ones(m);
        for (i, &c) in pivots.iter().enumerate() {
            particular.set(c, a[i].get(m));
            free.set(c, false);
        }
        let columns: Vec<_> = free.iter_ones().collect();
        let mut basis: Vec<_> = columns
            .iter()
            .map(|&c| {
                let mut row = BitSet::new(m);
                row.set(c, true);
                row
            })
            .collect();
        for (i, &p) in pivots.iter().enumerate() {
            for (row, &c) in basis.iter_mut().zip(&columns) {
                row.words_mut()[p / 64] |= u64::from(a[i].get(c)) << (p & 63);
            }
        }
        Some(BitMatrixSolution { particular, basis })
    }

crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 14)

    pub fn new(size: usize) -> Self {
        let mut dp = BitSet::new(if size == !0 { 0 } else { size } + 1);
        dp.set(0, true);
        Self {
            size,
            dp,
            pending_weights: vec![],
        }
    }

pub fn reset(&mut self)

Clears all bits.

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 372)

    fn shift_left<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_left_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                if self.size & 511 != 0 {
                    self.trim();
                }
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_left_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                if self.size & 63 != 0 {
                    self.trim();
                }
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in (0..bits.len() - word_shift).rev() {
                if OR_ASSIGN {
                    bits[i + word_shift] |= bits[i];
                } else {
                    bits[i + word_shift] = bits[i];
                }
            }
        } else {
            for i in (1..bits.len() - word_shift).rev() {
                let value = (bits[i] << bit_shift) | (bits[i - 1] >> (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i + word_shift] |= value;
                } else {
                    bits[i + word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[word_shift] |= bits[0] << bit_shift;
            } else {
                bits[word_shift] = bits[0] << bit_shift;
            }
        }
        if !OR_ASSIGN {
            bits[..word_shift].fill(0);
        }
        if self.size & 63 != 0 {
            self.trim();
        }
    }

    #[inline]
    fn shift_right<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_right_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_right_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in word_shift..bits.len() {
                if OR_ASSIGN {
                    bits[i - word_shift] |= bits[i];
                } else {
                    bits[i - word_shift] = bits[i];
                }
            }
        } else {
            for i in word_shift..bits.len() - 1 {
                let value = (bits[i] >> bit_shift) | (bits[i + 1] << (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i - word_shift] |= value;
                } else {
                    bits[i - word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[bits.len() - word_shift - 1] |= bits[bits.len() - 1] >> bit_shift;
            } else {
                bits[bits.len() - word_shift - 1] = bits[bits.len() - 1] >> bit_shift;
            }
        }
        if !OR_ASSIGN {
            let end = bits.len() - word_shift;
            bits[end..].fill(0);
        }
    }

pub fn fill(&mut self, value: bool)

Sets all bits to value.

pub fn any(&self) -> bool

Tests whether any bit is set.

pub fn none(&self) -> bool

Tests whether all bits are unset.

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 173)

    pub fn any(&self) -> bool {
        !self.none()
    }

pub fn all(&self) -> bool

Tests whether all bits are set.

pub fn iter_ones(&self) -> impl Iterator<Item = usize> + '_

Iterates over set-bit indices in ascending order.

Examples found in repository

crates/competitive/src/math/bit_matrix.rs (line 56)

    pub fn transpose(&self) -> Self {
        let mut a = Self::zeros((self.shape.1, self.shape.0));
        for (i, row) in self.data.iter().enumerate() {
            for j in row.iter_ones() {
                a[j].set(i, true);
            }
        }
        a
    }

    /// Replaces the matrix with reduced row echelon form and returns its pivot columns.
    pub fn row_reduction(&mut self) -> Vec<usize> {
        self.eliminate(self.shape.1, true, false)
    }

    /// Replaces the matrix with row echelon form and returns its rank.
    pub fn rank(&mut self) -> usize {
        self.eliminate(self.shape.1, false, false).len()
    }

    /// Computes the determinant in place. The matrix must be square.
    pub fn determinant(&mut self) -> bool {
        assert_eq!(self.shape.0, self.shape.1);
        self.eliminate(self.shape.1, false, true).len() == self.shape.0
    }

    /// Returns the inverse, or `None` if singular. The matrix must be square.
    pub fn inverse(&self) -> Option<Self> {
        let (n, m) = self.shape;
        assert_eq!(n, m);
        let mut a = Self::zeros((n, 2 * n));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(n + i, true);
        }
        if a.eliminate(n, true, true).len() != n {
            return None;
        }
        for row in &mut a.data {
            *row >>= n;
        }
        let mut inverse = Self::zeros((n, n));
        for (row, source) in inverse.data.iter_mut().zip(&a.data) {
            let len = row.words().len();
            row.words_mut().copy_from_slice(&source.words()[..len]);
        }
        Some(inverse)
    }

    /// Returns a particular solution and a basis of the kernel, or `None` if inconsistent.
    /// `b.len()` must equal the number of rows.
    pub fn solve_system_of_linear_equations(&self, b: &BitSet) -> Option<BitMatrixSolution> {
        let (n, m) = self.shape;
        assert_eq!(b.len(), n);
        let mut a = Self::zeros((n, m + 1));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(m, b.get(i));
        }
        let pivots = a.eliminate(m, true, false);
        if a.data[pivots.len()..].iter().any(|row| row.get(m)) {
            return None;
        }
        let mut particular = BitSet::new(m);
        let mut free = BitSet::ones(m);
        for (i, &c) in pivots.iter().enumerate() {
            particular.set(c, a[i].get(m));
            free.set(c, false);
        }
        let columns: Vec<_> = free.iter_ones().collect();
        let mut basis: Vec<_> = columns
            .iter()
            .map(|&c| {
                let mut row = BitSet::new(m);
                row.set(c, true);
                row
            })
            .collect();
        for (i, &p) in pivots.iter().enumerate() {
            for (row, &c) in basis.iter_mut().zip(&columns) {
                row.words_mut()[p / 64] |= u64::from(a[i].get(c)) << (p & 63);
            }
        }
        Some(BitMatrixSolution { particular, basis })
    }

    pub fn pow(self, mut n: usize) -> Self {
        assert_eq!(self.shape.0, self.shape.1);
        let mut result = Self::eye(self.shape);
        let mut a = self;
        while n != 0 {
            if n & 1 != 0 {
                result = &result * &a;
            }
            n >>= 1;
            if n != 0 {
                a = &a * &a;
            }
        }
        result
    }

    fn eliminate(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        #[cfg(target_arch = "x86_64")]
        match simd_backend() {
            // SAFETY: the dispatcher checks the required CPU features.
            SimdBackend::Avx512 => {
                return unsafe { self.eliminate_avx512(cols, full, require_full_rank) };
            }
            // SAFETY: the dispatcher checks AVX2 support.
            SimdBackend::Avx2 => {
                return unsafe { self.eliminate_avx2(cols, full, require_full_rank) };
            }
            SimdBackend::Scalar => {}
        }
        self.eliminate_impl(cols, full, require_full_rank)
    }

    // Inlined into each target-feature entry point to vectorize the row operations.
    #[inline(always)]
    fn eliminate_impl(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut pivots = Vec::with_capacity(n.min(cols));
        if n < 32 {
            let mut c = 0;
            while c < cols {
                let r = pivots.len();
                if r == n {
                    break;
                }
                let Some(p) = (r..n).find(|&i| self[i].get(c)) else {
                    if require_full_rank {
                        return pivots;
                    }
                    c = self.next_column(r, c + 1, cols);
                    continue;
                };
                self.data.swap(r, p);
                let (upper, lower) = self.data.split_at_mut(r);
                let (pivot, lower) = lower.split_first_mut().unwrap();
                for row in lower
                    .iter_mut()
                    .chain(upper.iter_mut().take(if full { r } else { 0 }))
                {
                    if row.get(c) {
                        xor(&mut row.words_mut()[c / 64..], &pivot.words()[c / 64..]);
                    }
                }
                pivots.push(c);
                c += 1;
            }
            return pivots;
        }
        // Eliminating a shared leading coefficient preserves the two-coefficient bound.
        if self
            .data
            .iter()
            .all(|row| row.iter_ones().take_while(|&c| c < cols).take(3).count() <= 2)
        {
            return self.eliminate_sparse(cols, full, require_full_rank);
        }
        let block: usize = if n < 512 {
            4
        } else if n < 1536 {
            8
        } else {
            32
        };
        let mut table = vec![BitSet::new(self.shape.1); (1 << block.min(8)) * block.div_ceil(8)];
        let mut reduced = vec![0; n];
        let mut start = 0;
        while start < cols {
            let first = pivots.len();
            let word = start / 64;
            reduced.fill(first);
            let end = cols.min(start + block);
            let mut c = start;
            while c < end {
                let r = pivots.len();
                let mut pivot = None;
                for (i, reduced) in reduced.iter_mut().enumerate().skip(r) {
                    let (upper, lower) = self.data.split_at_mut(i);
                    let row = &mut lower[0];
                    for p in *reduced..r {
                        if row.get(pivots[p]) {
                            xor(&mut row.words_mut()[word..], &upper[p].words()[word..]);
                        }
                    }
                    *reduced = r;
                    if row.get(c) {
                        pivot = Some(i);
                        break;
                    }
                }
                if let Some(p) = pivot {
                    self.data.swap(r, p);
                    reduced.swap(r, p);
                    pivots.push(c);
                    c += 1;
                } else if require_full_rank {
                    return pivots;
                } else {
                    c = self.next_column(r, c + 1, end);
                }
            }
            let rank = pivots.len();
            if first == rank {
                let next = self.next_column(rank, start + block, cols);
                if next == cols {
                    break;
                }
                start = next / block * block;
                continue;
            }
            // Make the panel's pivot columns an identity matrix before indexing its table.
            for r in (first..rank).rev() {
                let (upper, lower) = self.data.split_at_mut(r);
                for row in &mut upper[first..] {
                    if row.get(pivots[r]) {
                        xor(&mut row.words_mut()[word..], &lower[0].words()[word..]);
                    }
                }
            }
            let mut indices = [[0usize; 256]; 4];
            let mut masks = [0usize; 4];
            for group in 0..block.div_ceil(8) {
                let mut keys = [0usize; 256];
                let mut count = 0;
                for (row, &c) in pivots[first..].iter().enumerate() {
                    if (c - start) / 8 != group {
                        continue;
                    }
                    let half = 1 << count;
                    count += 1;
                    for index in 0..half {
                        keys[index + half] = keys[index] | (1 << ((c - start) % 8));
                        let (lower, upper) = table.split_at_mut(group * 256 + index + half);
                        let target = &mut upper[0].words_mut()[word..];
                        let source = &lower[group * 256 + index].words()[word..];
                        let pivot = &self[first + row].words()[word..];
                        for ((x, y), z) in target.iter_mut().zip(source).zip(pivot) {
                            *x = y ^ z;
                        }
                    }
                }
                masks[group] = keys[(1 << count) - 1];
                for (i, &key) in keys[..1 << count].iter().enumerate() {
                    indices[group][key] = i;
                }
            }
            for i in (rank..n).chain(0..if full { first } else { 0 }) {
                let key = (self[i].words()[word] >> (start & 63)) as usize;
                let x = indices[0][key & masks[0]];
                if block <= 8 {
                    if x != 0 {
                        xor(&mut self[i].words_mut()[word..], &table[x].words()[word..]);
                    }
                    continue;
                }
                let y = indices[1][(key >> 8) & masks[1]];
                let z = indices[2][(key >> 16) & masks[2]];
                let w = indices[3][(key >> 24) & masks[3]];
                if x | y | z | w != 0 {
                    let p = &table[x].words()[word..];
                    let q = &table[256 + y].words()[word..];
                    let r = &table[512 + z].words()[word..];
                    let s = &table[768 + w].words()[word..];
                    for ((((x, y), z), r), s) in self[i].words_mut()[word..]
                        .iter_mut()
                        .zip(p)
                        .zip(q)
                        .zip(r)
                        .zip(s)
                    {
                        *x ^= y ^ z ^ r ^ s;
                    }
                }
            }
            if rank == n {
                break;
            }
            start += block;
        }
        pivots
    }

    fn next_column(&self, row: usize, mut start: usize, cols: usize) -> usize {
        while start < cols {
            let word = start / 64;
            let bits = self.data[row..]
                .iter()
                .fold(0, |x, row| x | row.words()[word])
                & (u64::MAX << (start & 63));
            if bits != 0 {
                return (word * 64 + bits.trailing_zeros() as usize).min(cols);
            }
            start = (word + 1) * 64;
        }
        cols
    }

    #[inline(always)]
    fn eliminate_sparse(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut basis = vec![n; cols];
        let mut pivots = Vec::new();
        for i in 0..n {
            loop {
                let Some(c) = self[i].iter_ones().next().filter(|&c| c < cols) else {
                    if require_full_rank {
                        return pivots;
                    }
                    break;
                };
                if basis[c] == n {
                    basis[c] = i;
                    pivots.push(c);
                    break;
                }
                let (upper, lower) = self.data.split_at_mut(i);
                xor(
                    &mut lower[0].words_mut()[c / 64..],
                    &upper[basis[c]].words()[c / 64..],
                );
            }
        }
        pivots.sort_unstable();
        self.data
            .sort_by_cached_key(|row| row.iter_ones().next().filter(|&c| c < cols).unwrap_or(cols));
        if full {
            for (i, &c) in pivots.iter().enumerate() {
                basis[c] = i;
            }
            for i in (0..pivots.len()).rev() {
                let next = self[i].iter_ones().take_while(|&c| c < cols).nth(1);
                if let Some(c) = next
                    && basis[c] != n
                {
                    let (upper, lower) = self.data.split_at_mut(basis[c]);
                    xor(
                        &mut upper[i].words_mut()[c / 64..],
                        &lower[0].words()[c / 64..],
                    );
                }
            }
        }
        pivots
    }

    #[inline(always)]
    fn mul_impl(&self, rhs: &Self) -> Self {
        let mut result = Self::zeros((self.shape.0, rhs.shape.1));
        let ones = self.data.iter().map(BitSet::count_ones).sum::<u64>();
        let size = self.shape.0 as u64 * self.shape.1 as u64;
        if self.shape.0 < 256 || self.shape.1 < 32 || ones <= size / 8 {
            for (a, c) in self.data.iter().zip(&mut result.data) {
                for j in a.iter_ones() {
                    xor(c.words_mut(), rhs[j].words());
                }
            }
            return result;
        }
        if size - ones <= size / 8 {
            let mut sum = BitSet::new(rhs.shape.1);
            for row in &rhs.data {
                sum ^= row;
            }
            for (a, c) in self.data.iter().zip(&mut result.data) {
                c.words_mut().copy_from_slice(sum.words());
                for j in (!a.clone()).iter_ones() {
                    xor(c.words_mut(), rhs[j].words());
                }
            }
            return result;
        }
        let width = rhs.shape.1.div_ceil(64);
        if width == 0 {
            return result;
        }

        // Separate the table groups by a cache line to avoid mapping them to the same sets.
        let group = 256 * width + 8;
        let mut storage = BitSet::new(8 * group * 64);
        let table = storage.words_mut();
        for start in (0..self.shape.1).step_by(64) {
            for (t, table) in table.chunks_exact_mut(group).enumerate() {
                let col = start + t * 8;
                for bit in 0..self.shape.1.saturating_sub(col).min(8) {
                    let row = rhs[col + bit].words();
                    let half = (1 << bit) * width;
                    let (lower, upper) = table.split_at_mut(half);
                    for (source, dest) in
                        lower.chunks_exact(width).zip(upper.chunks_exact_mut(width))
                    {
                        for ((x, y), z) in dest.iter_mut().zip(source).zip(row) {
                            *x = y ^ z;
                        }
                    }
                }
            }
            for (a, c) in self.data.iter().zip(&mut result.data) {
                let key = a.words()[start / 64];
                let offset = (key & 255) as usize * width;
                let p0 = &table[offset..offset + width];
                let offset = group + (key >> 8 & 255) as usize * width;
                let p1 = &table[offset..offset + width];
                let offset = 2 * group + (key >> 16 & 255) as usize * width;
                let p2 = &table[offset..offset + width];
                let offset = 3 * group + (key >> 24 & 255) as usize * width;
                let p3 = &table[offset..offset + width];
                let offset = 4 * group + (key >> 32 & 255) as usize * width;
                let p4 = &table[offset..offset + width];
                let offset = 5 * group + (key >> 40 & 255) as usize * width;
                let p5 = &table[offset..offset + width];
                let offset = 6 * group + (key >> 48 & 255) as usize * width;
                let p6 = &table[offset..offset + width];
                let offset = 7 * group + (key >> 56 & 255) as usize * width;
                let p7 = &table[offset..offset + width];
                for ((((((((x, p0), p1), p2), p3), p4), p5), p6), p7) in c
                    .words_mut()
                    .iter_mut()
                    .zip(p0)
                    .zip(p1)
                    .zip(p2)
                    .zip(p3)
                    .zip(p4)
                    .zip(p5)
                    .zip(p6)
                    .zip(p7)
                {
                    *x ^= p0 ^ p1 ^ p2 ^ p3 ^ p4 ^ p5 ^ p6 ^ p7;
                }
            }
        }
        result
    }

pub fn count_ones(&self) -> u64

Counts set bits.

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 275)

    pub fn count_zeros(&self) -> u64 {
        self.size as u64 - self.count_ones()
    }

pub fn count_zeros(&self) -> u64

Counts unset bits.

pub fn push(&mut self, b: bool)

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 497)

    fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T) {
        for bit in iter {
            self.push(bit);
        }
    }

crates/competitive/src/algorithm/automata_learning.rs (lines 344-347)

    fn add_suffix(&mut self, suffix: Vec<usize>) {
        if self.suffixes.contains(&suffix) {
            return;
        }
        for (prefix, table) in self.prefixes.iter_mut().zip(&mut self.table) {
            table.push(
                self.automaton
                    .behavior(prefix.iter().cloned().chain(suffix.iter().cloned())),
            );
        }
        self.suffixes.push(suffix);
        self.row_map.clear();
        for (i_prefix, row) in self.table.iter().enumerate() {
            self.row_map.insert(row.clone(), i_prefix);
        }
    }

pub fn resize(&mut self, new_size: usize)

Examples found in repository

crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 69)

    fn rebuild(&mut self) {
        if self.pending_weights.is_empty() {
            return;
        }
        let mut heap = BinaryHeap::from(take(&mut self.pending_weights));
        let (mut current_weight, mut count) = match heap.pop() {
            Some(Reverse(w)) => (w, 1),
            None => return,
        };
        while let Some(Reverse(weight)) = heap.pop() {
            if weight == current_weight {
                count += 1;
                if count >= 3 {
                    if let Some(w) = current_weight.checked_mul(2) {
                        heap.push(Reverse(w));
                    }
                    count -= 2;
                }
                continue;
            }
            for _ in 0..count {
                if self.size == !0 {
                    self.dp.resize(self.dp.len() + current_weight);
                }
                self.dp.shl_bitor_assign(current_weight);
            }
            (current_weight, count) = (weight, 1);
        }
        for _ in 0..count {
            if self.size == !0 {
                self.dp.resize(self.dp.len() + current_weight);
            }
            self.dp.shl_bitor_assign(current_weight);
        }
    }

pub fn shl_bitor_assign(&mut self, rhs: usize)

Assigns self | (self << rhs) to self.

Examples found in repository

crates/competitive/src/combinatorial_optimization/subset_sum_problem.rs (line 71)

    fn rebuild(&mut self) {
        if self.pending_weights.is_empty() {
            return;
        }
        let mut heap = BinaryHeap::from(take(&mut self.pending_weights));
        let (mut current_weight, mut count) = match heap.pop() {
            Some(Reverse(w)) => (w, 1),
            None => return,
        };
        while let Some(Reverse(weight)) = heap.pop() {
            if weight == current_weight {
                count += 1;
                if count >= 3 {
                    if let Some(w) = current_weight.checked_mul(2) {
                        heap.push(Reverse(w));
                    }
                    count -= 2;
                }
                continue;
            }
            for _ in 0..count {
                if self.size == !0 {
                    self.dp.resize(self.dp.len() + current_weight);
                }
                self.dp.shl_bitor_assign(current_weight);
            }
            (current_weight, count) = (weight, 1);
        }
        for _ in 0..count {
            if self.size == !0 {
                self.dp.resize(self.dp.len() + current_weight);
            }
            self.dp.shl_bitor_assign(current_weight);
        }
    }

pub fn shr_bitor_assign(&mut self, rhs: usize)

Assigns self | (self >> rhs) to self.

pub fn words(&self) -> &[u64]

Returns words in increasing bit-index order; unused high bits in the last word are zero.

Examples found in repository

crates/competitive/src/math/bit_matrix.rs (line 85)

    pub fn inverse(&self) -> Option<Self> {
        let (n, m) = self.shape;
        assert_eq!(n, m);
        let mut a = Self::zeros((n, 2 * n));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(n + i, true);
        }
        if a.eliminate(n, true, true).len() != n {
            return None;
        }
        for row in &mut a.data {
            *row >>= n;
        }
        let mut inverse = Self::zeros((n, n));
        for (row, source) in inverse.data.iter_mut().zip(&a.data) {
            let len = row.words().len();
            row.words_mut().copy_from_slice(&source.words()[..len]);
        }
        Some(inverse)
    }

    /// Returns a particular solution and a basis of the kernel, or `None` if inconsistent.
    /// `b.len()` must equal the number of rows.
    pub fn solve_system_of_linear_equations(&self, b: &BitSet) -> Option<BitMatrixSolution> {
        let (n, m) = self.shape;
        assert_eq!(b.len(), n);
        let mut a = Self::zeros((n, m + 1));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(m, b.get(i));
        }
        let pivots = a.eliminate(m, true, false);
        if a.data[pivots.len()..].iter().any(|row| row.get(m)) {
            return None;
        }
        let mut particular = BitSet::new(m);
        let mut free = BitSet::ones(m);
        for (i, &c) in pivots.iter().enumerate() {
            particular.set(c, a[i].get(m));
            free.set(c, false);
        }
        let columns: Vec<_> = free.iter_ones().collect();
        let mut basis: Vec<_> = columns
            .iter()
            .map(|&c| {
                let mut row = BitSet::new(m);
                row.set(c, true);
                row
            })
            .collect();
        for (i, &p) in pivots.iter().enumerate() {
            for (row, &c) in basis.iter_mut().zip(&columns) {
                row.words_mut()[p / 64] |= u64::from(a[i].get(c)) << (p & 63);
            }
        }
        Some(BitMatrixSolution { particular, basis })
    }

    pub fn pow(self, mut n: usize) -> Self {
        assert_eq!(self.shape.0, self.shape.1);
        let mut result = Self::eye(self.shape);
        let mut a = self;
        while n != 0 {
            if n & 1 != 0 {
                result = &result * &a;
            }
            n >>= 1;
            if n != 0 {
                a = &a * &a;
            }
        }
        result
    }

    fn eliminate(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        #[cfg(target_arch = "x86_64")]
        match simd_backend() {
            // SAFETY: the dispatcher checks the required CPU features.
            SimdBackend::Avx512 => {
                return unsafe { self.eliminate_avx512(cols, full, require_full_rank) };
            }
            // SAFETY: the dispatcher checks AVX2 support.
            SimdBackend::Avx2 => {
                return unsafe { self.eliminate_avx2(cols, full, require_full_rank) };
            }
            SimdBackend::Scalar => {}
        }
        self.eliminate_impl(cols, full, require_full_rank)
    }

    // Inlined into each target-feature entry point to vectorize the row operations.
    #[inline(always)]
    fn eliminate_impl(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut pivots = Vec::with_capacity(n.min(cols));
        if n < 32 {
            let mut c = 0;
            while c < cols {
                let r = pivots.len();
                if r == n {
                    break;
                }
                let Some(p) = (r..n).find(|&i| self[i].get(c)) else {
                    if require_full_rank {
                        return pivots;
                    }
                    c = self.next_column(r, c + 1, cols);
                    continue;
                };
                self.data.swap(r, p);
                let (upper, lower) = self.data.split_at_mut(r);
                let (pivot, lower) = lower.split_first_mut().unwrap();
                for row in lower
                    .iter_mut()
                    .chain(upper.iter_mut().take(if full { r } else { 0 }))
                {
                    if row.get(c) {
                        xor(&mut row.words_mut()[c / 64..], &pivot.words()[c / 64..]);
                    }
                }
                pivots.push(c);
                c += 1;
            }
            return pivots;
        }
        // Eliminating a shared leading coefficient preserves the two-coefficient bound.
        if self
            .data
            .iter()
            .all(|row| row.iter_ones().take_while(|&c| c < cols).take(3).count() <= 2)
        {
            return self.eliminate_sparse(cols, full, require_full_rank);
        }
        let block: usize = if n < 512 {
            4
        } else if n < 1536 {
            8
        } else {
            32
        };
        let mut table = vec![BitSet::new(self.shape.1); (1 << block.min(8)) * block.div_ceil(8)];
        let mut reduced = vec![0; n];
        let mut start = 0;
        while start < cols {
            let first = pivots.len();
            let word = start / 64;
            reduced.fill(first);
            let end = cols.min(start + block);
            let mut c = start;
            while c < end {
                let r = pivots.len();
                let mut pivot = None;
                for (i, reduced) in reduced.iter_mut().enumerate().skip(r) {
                    let (upper, lower) = self.data.split_at_mut(i);
                    let row = &mut lower[0];
                    for p in *reduced..r {
                        if row.get(pivots[p]) {
                            xor(&mut row.words_mut()[word..], &upper[p].words()[word..]);
                        }
                    }
                    *reduced = r;
                    if row.get(c) {
                        pivot = Some(i);
                        break;
                    }
                }
                if let Some(p) = pivot {
                    self.data.swap(r, p);
                    reduced.swap(r, p);
                    pivots.push(c);
                    c += 1;
                } else if require_full_rank {
                    return pivots;
                } else {
                    c = self.next_column(r, c + 1, end);
                }
            }
            let rank = pivots.len();
            if first == rank {
                let next = self.next_column(rank, start + block, cols);
                if next == cols {
                    break;
                }
                start = next / block * block;
                continue;
            }
            // Make the panel's pivot columns an identity matrix before indexing its table.
            for r in (first..rank).rev() {
                let (upper, lower) = self.data.split_at_mut(r);
                for row in &mut upper[first..] {
                    if row.get(pivots[r]) {
                        xor(&mut row.words_mut()[word..], &lower[0].words()[word..]);
                    }
                }
            }
            let mut indices = [[0usize; 256]; 4];
            let mut masks = [0usize; 4];
            for group in 0..block.div_ceil(8) {
                let mut keys = [0usize; 256];
                let mut count = 0;
                for (row, &c) in pivots[first..].iter().enumerate() {
                    if (c - start) / 8 != group {
                        continue;
                    }
                    let half = 1 << count;
                    count += 1;
                    for index in 0..half {
                        keys[index + half] = keys[index] | (1 << ((c - start) % 8));
                        let (lower, upper) = table.split_at_mut(group * 256 + index + half);
                        let target = &mut upper[0].words_mut()[word..];
                        let source = &lower[group * 256 + index].words()[word..];
                        let pivot = &self[first + row].words()[word..];
                        for ((x, y), z) in target.iter_mut().zip(source).zip(pivot) {
                            *x = y ^ z;
                        }
                    }
                }
                masks[group] = keys[(1 << count) - 1];
                for (i, &key) in keys[..1 << count].iter().enumerate() {
                    indices[group][key] = i;
                }
            }
            for i in (rank..n).chain(0..if full { first } else { 0 }) {
                let key = (self[i].words()[word] >> (start & 63)) as usize;
                let x = indices[0][key & masks[0]];
                if block <= 8 {
                    if x != 0 {
                        xor(&mut self[i].words_mut()[word..], &table[x].words()[word..]);
                    }
                    continue;
                }
                let y = indices[1][(key >> 8) & masks[1]];
                let z = indices[2][(key >> 16) & masks[2]];
                let w = indices[3][(key >> 24) & masks[3]];
                if x | y | z | w != 0 {
                    let p = &table[x].words()[word..];
                    let q = &table[256 + y].words()[word..];
                    let r = &table[512 + z].words()[word..];
                    let s = &table[768 + w].words()[word..];
                    for ((((x, y), z), r), s) in self[i].words_mut()[word..]
                        .iter_mut()
                        .zip(p)
                        .zip(q)
                        .zip(r)
                        .zip(s)
                    {
                        *x ^= y ^ z ^ r ^ s;
                    }
                }
            }
            if rank == n {
                break;
            }
            start += block;
        }
        pivots
    }

    fn next_column(&self, row: usize, mut start: usize, cols: usize) -> usize {
        while start < cols {
            let word = start / 64;
            let bits = self.data[row..]
                .iter()
                .fold(0, |x, row| x | row.words()[word])
                & (u64::MAX << (start & 63));
            if bits != 0 {
                return (word * 64 + bits.trailing_zeros() as usize).min(cols);
            }
            start = (word + 1) * 64;
        }
        cols
    }

    #[inline(always)]
    fn eliminate_sparse(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut basis = vec![n; cols];
        let mut pivots = Vec::new();
        for i in 0..n {
            loop {
                let Some(c) = self[i].iter_ones().next().filter(|&c| c < cols) else {
                    if require_full_rank {
                        return pivots;
                    }
                    break;
                };
                if basis[c] == n {
                    basis[c] = i;
                    pivots.push(c);
                    break;
                }
                let (upper, lower) = self.data.split_at_mut(i);
                xor(
                    &mut lower[0].words_mut()[c / 64..],
                    &upper[basis[c]].words()[c / 64..],
                );
            }
        }
        pivots.sort_unstable();
        self.data
            .sort_by_cached_key(|row| row.iter_ones().next().filter(|&c| c < cols).unwrap_or(cols));
        if full {
            for (i, &c) in pivots.iter().enumerate() {
                basis[c] = i;
            }
            for i in (0..pivots.len()).rev() {
                let next = self[i].iter_ones().take_while(|&c| c < cols).nth(1);
                if let Some(c) = next
                    && basis[c] != n
                {
                    let (upper, lower) = self.data.split_at_mut(basis[c]);
                    xor(
                        &mut upper[i].words_mut()[c / 64..],
                        &lower[0].words()[c / 64..],
                    );
                }
            }
        }
        pivots
    }

    #[inline(always)]
    fn mul_impl(&self, rhs: &Self) -> Self {
        let mut result = Self::zeros((self.shape.0, rhs.shape.1));
        let ones = self.data.iter().map(BitSet::count_ones).sum::<u64>();
        let size = self.shape.0 as u64 * self.shape.1 as u64;
        if self.shape.0 < 256 || self.shape.1 < 32 || ones <= size / 8 {
            for (a, c) in self.data.iter().zip(&mut result.data) {
                for j in a.iter_ones() {
                    xor(c.words_mut(), rhs[j].words());
                }
            }
            return result;
        }
        if size - ones <= size / 8 {
            let mut sum = BitSet::new(rhs.shape.1);
            for row in &rhs.data {
                sum ^= row;
            }
            for (a, c) in self.data.iter().zip(&mut result.data) {
                c.words_mut().copy_from_slice(sum.words());
                for j in (!a.clone()).iter_ones() {
                    xor(c.words_mut(), rhs[j].words());
                }
            }
            return result;
        }
        let width = rhs.shape.1.div_ceil(64);
        if width == 0 {
            return result;
        }

        // Separate the table groups by a cache line to avoid mapping them to the same sets.
        let group = 256 * width + 8;
        let mut storage = BitSet::new(8 * group * 64);
        let table = storage.words_mut();
        for start in (0..self.shape.1).step_by(64) {
            for (t, table) in table.chunks_exact_mut(group).enumerate() {
                let col = start + t * 8;
                for bit in 0..self.shape.1.saturating_sub(col).min(8) {
                    let row = rhs[col + bit].words();
                    let half = (1 << bit) * width;
                    let (lower, upper) = table.split_at_mut(half);
                    for (source, dest) in
                        lower.chunks_exact(width).zip(upper.chunks_exact_mut(width))
                    {
                        for ((x, y), z) in dest.iter_mut().zip(source).zip(row) {
                            *x = y ^ z;
                        }
                    }
                }
            }
            for (a, c) in self.data.iter().zip(&mut result.data) {
                let key = a.words()[start / 64];
                let offset = (key & 255) as usize * width;
                let p0 = &table[offset..offset + width];
                let offset = group + (key >> 8 & 255) as usize * width;
                let p1 = &table[offset..offset + width];
                let offset = 2 * group + (key >> 16 & 255) as usize * width;
                let p2 = &table[offset..offset + width];
                let offset = 3 * group + (key >> 24 & 255) as usize * width;
                let p3 = &table[offset..offset + width];
                let offset = 4 * group + (key >> 32 & 255) as usize * width;
                let p4 = &table[offset..offset + width];
                let offset = 5 * group + (key >> 40 & 255) as usize * width;
                let p5 = &table[offset..offset + width];
                let offset = 6 * group + (key >> 48 & 255) as usize * width;
                let p6 = &table[offset..offset + width];
                let offset = 7 * group + (key >> 56 & 255) as usize * width;
                let p7 = &table[offset..offset + width];
                for ((((((((x, p0), p1), p2), p3), p4), p5), p6), p7) in c
                    .words_mut()
                    .iter_mut()
                    .zip(p0)
                    .zip(p1)
                    .zip(p2)
                    .zip(p3)
                    .zip(p4)
                    .zip(p5)
                    .zip(p6)
                    .zip(p7)
                {
                    *x ^= p0 ^ p1 ^ p2 ^ p3 ^ p4 ^ p5 ^ p6 ^ p7;
                }
            }
        }
        result
    }

crates/competitive/src/data_structure/bitset.rs (line 112)

    pub fn to_binary(&self) -> String {
        const TABLE: [[u8; 8]; 256] = {
            let mut table = [[b'0'; 8]; 256];
            let mut i = 0;
            while i < 256 {
                let mut j = 0;
                while j < 8 {
                    table[i][j] |= ((i >> j) & 1) as u8;
                    j += 1;
                }
                i += 1;
            }
            table
        };
        let mut bytes = vec![b'0'; self.size.div_ceil(8) * 8];
        #[cfg(target_arch = "x86_64")]
        let end = if self.size >= 64 && avx512_enabled() && is_x86_feature_detected!("avx512bw") {
            let end = self.size / 64 * 64;
            // SAFETY: AVX-512BW is available; each output chunk holds one 64-bit word.
            unsafe {
                simd::write_binary_avx512(&mut bytes[..end], self.words());
            }
            end
        } else if self.size >= 64 && is_x86_feature_detected!("avx2") {
            let end = self.size / 64 * 64;
            // SAFETY: AVX2 is available; each output chunk holds one complete 64-bit word.
            unsafe {
                simd::write_binary_avx2(&mut bytes[..end], self.words());
            }
            end
        } else {
            0
        };
        #[cfg(not(target_arch = "x86_64"))]
        let end = 0;
        for (chunk, &word) in bytes[end..].chunks_mut(64).zip(&self.words()[end / 64..]) {
            for (i, byte) in chunk.as_chunks_mut::<8>().0.iter_mut().enumerate() {
                byte.copy_from_slice(&TABLE[(word >> (i * 8) & 255) as usize]);
            }
        }
        bytes.truncate(self.size);
        // SAFETY: every output byte is ASCII `0` or `1`.
        unsafe { String::from_utf8_unchecked(bytes) }
    }

    pub fn ones(size: usize) -> Self {
        let mut self_ = Self {
            size,
            bits: vec![Block([u64::MAX; 8]); size.div_ceil(512)],
        };
        self_.trim();
        self_
    }

    pub fn get(&self, i: usize) -> bool {
        self.bits[i >> 9].0[i >> 6 & 7] & (1 << (i & 63)) != 0
    }

    pub fn set(&mut self, i: usize, b: bool) {
        let word = &mut self.bits[i >> 9].0[i >> 6 & 7];
        if b {
            *word |= 1 << (i & 63);
        } else {
            *word &= !(1 << (i & 63));
        }
    }

    /// Clears all bits.
    pub fn reset(&mut self) {
        self.bits.fill(Block::default());
    }

    /// Sets all bits to `value`.
    pub fn fill(&mut self, value: bool) {
        self.bits.fill(Block([if value { u64::MAX } else { 0 }; 8]));
        self.trim();
    }

    /// Tests whether any bit is set.
    #[inline]
    pub fn any(&self) -> bool {
        !self.none()
    }

    /// Tests whether all bits are unset.
    #[inline]
    pub fn none(&self) -> bool {
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if self.bits[0].0[0] != 0 {
                return false;
            }
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                return unsafe { simd::none_avx512(&self.bits) };
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                return unsafe { simd::none_avx2(&self.bits) };
            }
        }
        self.words().iter().all(|&word| word == 0)
    }

    /// Tests whether all bits are set.
    #[inline(always)]
    pub fn all(&self) -> bool {
        let words = self.words();
        let full_words = self.size >> 6;
        #[cfg(target_arch = "x86_64")]
        if self.size >> 9 >= SIMD_MIN_BLOCKS {
            let full_blocks = self.size >> 9;
            if words[0] != u64::MAX {
                return false;
            }
            let full_blocks_are_set = if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                Some(unsafe { simd::all_avx512(&self.bits[..full_blocks]) })
            } else if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                Some(unsafe { simd::all_avx2(&self.bits[..full_blocks]) })
            } else {
                None
            };
            if let Some(full_blocks_are_set) = full_blocks_are_set {
                return full_blocks_are_set
                    && words[full_blocks * 8..full_words]
                        .iter()
                        .all(|&word| word == u64::MAX)
                    && (self.size & 63 == 0
                        || words[full_words] == u64::MAX >> (64 - (self.size & 63)));
            }
        }
        if self.size & 63 == 0 {
            return words.iter().all(|&word| word == u64::MAX);
        }
        words[..full_words].iter().all(|&word| word == u64::MAX)
            && words[full_words] == u64::MAX >> (64 - (self.size & 63))
    }

    /// Iterates over set-bit indices in ascending order.
    pub fn iter_ones(&self) -> impl Iterator<Item = usize> + '_ {
        self.words()
            .iter()
            .copied()
            .enumerate()
            .flat_map(|(word_index, mut word)| {
                std::iter::from_fn(move || {
                    if word == 0 {
                        None
                    } else {
                        let bit = word.trailing_zeros() as usize;
                        word &= word - 1;
                        Some((word_index << 6) | bit)
                    }
                })
            })
    }

    /// Counts set bits.
    #[inline]
    pub fn count_ones(&self) -> u64 {
        let words = self.words();
        #[cfg(target_arch = "x86_64")]
        if words.len() >= 8 {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vpopcntdq")
            {
                // SAFETY: blocks are aligned and feature detection checked both requirements.
                return unsafe { simd::count_ones_avx512(&self.bits) };
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                return unsafe { simd::count_ones_avx2(&self.bits) };
            }
        }
        words.iter().map(|word| word.count_ones() as u64).sum()
    }

    /// Counts unset bits.
    #[inline]
    pub fn count_zeros(&self) -> u64 {
        self.size as u64 - self.count_ones()
    }

    pub fn push(&mut self, b: bool) {
        if self.size & 511 == 0 {
            self.bits.push(Block::default());
        }
        if b {
            self.bits[self.size >> 9].0[self.size >> 6 & 7] |= 1 << (self.size & 63);
        }
        self.size += 1;
    }

    pub fn resize(&mut self, new_size: usize) {
        match self.size.cmp(&new_size) {
            Ordering::Less => self.bits.resize(new_size.div_ceil(512), Block::default()),
            Ordering::Equal => {}
            Ordering::Greater => self.bits.truncate(new_size.div_ceil(512)),
        }
        self.size = new_size;
        self.trim();
    }

    /// Assigns `self | (self << rhs)` to `self`.
    #[inline]
    pub fn shl_bitor_assign(&mut self, rhs: usize) {
        self.shift_left::<true>(rhs);
    }

    /// Assigns `self | (self >> rhs)` to `self`.
    #[inline]
    pub fn shr_bitor_assign(&mut self, rhs: usize) {
        self.shift_right::<true>(rhs);
    }

    /// Returns words in increasing bit-index order; unused high bits in the last word are zero.
    pub fn words(&self) -> &[u64] {
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts(self.bits.as_ptr().cast(), self.size.div_ceil(64)) }
    }

    /// Returns mutable words in increasing bit-index order.
    /// Callers must keep unused high bits in the last word zero.
    pub fn words_mut(&mut self) -> &mut [u64] {
        let len = self.size.div_ceil(64);
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts_mut(self.bits.as_mut_ptr().cast(), len) }
    }

    fn trim(&mut self) {
        let used_words = self.size.div_ceil(64) & 7;
        if let Some(last) = self.bits.last_mut() {
            if self.size & 63 != 0 {
                last.0[(self.size >> 6) & 7] &= u64::MAX >> (64 - (self.size & 63));
            }
            if used_words != 0 {
                last.0[used_words..].fill(0);
            }
        }
    }

    #[inline]
    fn bitop_assign<const OP: u8>(&mut self, rhs: &Self) {
        assert_eq!(
            self.size, rhs.size,
            "bitwise operations require equal lengths"
        );
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                unsafe { simd::bitop_avx512::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                unsafe { simd::bitop_avx2::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
        }
        for (lhs, &rhs) in self.words_mut().iter_mut().zip(rhs.words()) {
            *lhs = match OP {
                BIT_AND => *lhs & rhs,
                BIT_OR => *lhs | rhs,
                BIT_XOR => *lhs ^ rhs,
                _ => unreachable!(),
            };
        }
    }

pub fn words_mut(&mut self) -> &mut [u64]

Returns mutable words in increasing bit-index order. Callers must keep unused high bits in the last word zero.

Examples found in repository

crates/competitive/src/math/bit_matrix.rs (line 36)

    pub fn new_with(shape: (usize, usize), mut f: impl FnMut(usize, usize) -> bool) -> Self {
        let mut a = Self::zeros(shape);
        for (i, row) in a.data.iter_mut().enumerate() {
            for (w, word) in row.words_mut().iter_mut().enumerate() {
                for j in w * 64..shape.1.min((w + 1) * 64) {
                    *word |= u64::from(f(i, j)) << (j & 63);
                }
            }
        }
        a
    }

    pub fn eye(shape: (usize, usize)) -> Self {
        let mut a = Self::zeros(shape);
        for i in 0..shape.0.min(shape.1) {
            a[i].set(i, true);
        }
        a
    }

    pub fn transpose(&self) -> Self {
        let mut a = Self::zeros((self.shape.1, self.shape.0));
        for (i, row) in self.data.iter().enumerate() {
            for j in row.iter_ones() {
                a[j].set(i, true);
            }
        }
        a
    }

    /// Replaces the matrix with reduced row echelon form and returns its pivot columns.
    pub fn row_reduction(&mut self) -> Vec<usize> {
        self.eliminate(self.shape.1, true, false)
    }

    /// Replaces the matrix with row echelon form and returns its rank.
    pub fn rank(&mut self) -> usize {
        self.eliminate(self.shape.1, false, false).len()
    }

    /// Computes the determinant in place. The matrix must be square.
    pub fn determinant(&mut self) -> bool {
        assert_eq!(self.shape.0, self.shape.1);
        self.eliminate(self.shape.1, false, true).len() == self.shape.0
    }

    /// Returns the inverse, or `None` if singular. The matrix must be square.
    pub fn inverse(&self) -> Option<Self> {
        let (n, m) = self.shape;
        assert_eq!(n, m);
        let mut a = Self::zeros((n, 2 * n));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(n + i, true);
        }
        if a.eliminate(n, true, true).len() != n {
            return None;
        }
        for row in &mut a.data {
            *row >>= n;
        }
        let mut inverse = Self::zeros((n, n));
        for (row, source) in inverse.data.iter_mut().zip(&a.data) {
            let len = row.words().len();
            row.words_mut().copy_from_slice(&source.words()[..len]);
        }
        Some(inverse)
    }

    /// Returns a particular solution and a basis of the kernel, or `None` if inconsistent.
    /// `b.len()` must equal the number of rows.
    pub fn solve_system_of_linear_equations(&self, b: &BitSet) -> Option<BitMatrixSolution> {
        let (n, m) = self.shape;
        assert_eq!(b.len(), n);
        let mut a = Self::zeros((n, m + 1));
        for i in 0..n {
            a[i].words_mut()[..self[i].words().len()].copy_from_slice(self[i].words());
            a[i].set(m, b.get(i));
        }
        let pivots = a.eliminate(m, true, false);
        if a.data[pivots.len()..].iter().any(|row| row.get(m)) {
            return None;
        }
        let mut particular = BitSet::new(m);
        let mut free = BitSet::ones(m);
        for (i, &c) in pivots.iter().enumerate() {
            particular.set(c, a[i].get(m));
            free.set(c, false);
        }
        let columns: Vec<_> = free.iter_ones().collect();
        let mut basis: Vec<_> = columns
            .iter()
            .map(|&c| {
                let mut row = BitSet::new(m);
                row.set(c, true);
                row
            })
            .collect();
        for (i, &p) in pivots.iter().enumerate() {
            for (row, &c) in basis.iter_mut().zip(&columns) {
                row.words_mut()[p / 64] |= u64::from(a[i].get(c)) << (p & 63);
            }
        }
        Some(BitMatrixSolution { particular, basis })
    }

    pub fn pow(self, mut n: usize) -> Self {
        assert_eq!(self.shape.0, self.shape.1);
        let mut result = Self::eye(self.shape);
        let mut a = self;
        while n != 0 {
            if n & 1 != 0 {
                result = &result * &a;
            }
            n >>= 1;
            if n != 0 {
                a = &a * &a;
            }
        }
        result
    }

    fn eliminate(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        #[cfg(target_arch = "x86_64")]
        match simd_backend() {
            // SAFETY: the dispatcher checks the required CPU features.
            SimdBackend::Avx512 => {
                return unsafe { self.eliminate_avx512(cols, full, require_full_rank) };
            }
            // SAFETY: the dispatcher checks AVX2 support.
            SimdBackend::Avx2 => {
                return unsafe { self.eliminate_avx2(cols, full, require_full_rank) };
            }
            SimdBackend::Scalar => {}
        }
        self.eliminate_impl(cols, full, require_full_rank)
    }

    // Inlined into each target-feature entry point to vectorize the row operations.
    #[inline(always)]
    fn eliminate_impl(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut pivots = Vec::with_capacity(n.min(cols));
        if n < 32 {
            let mut c = 0;
            while c < cols {
                let r = pivots.len();
                if r == n {
                    break;
                }
                let Some(p) = (r..n).find(|&i| self[i].get(c)) else {
                    if require_full_rank {
                        return pivots;
                    }
                    c = self.next_column(r, c + 1, cols);
                    continue;
                };
                self.data.swap(r, p);
                let (upper, lower) = self.data.split_at_mut(r);
                let (pivot, lower) = lower.split_first_mut().unwrap();
                for row in lower
                    .iter_mut()
                    .chain(upper.iter_mut().take(if full { r } else { 0 }))
                {
                    if row.get(c) {
                        xor(&mut row.words_mut()[c / 64..], &pivot.words()[c / 64..]);
                    }
                }
                pivots.push(c);
                c += 1;
            }
            return pivots;
        }
        // Eliminating a shared leading coefficient preserves the two-coefficient bound.
        if self
            .data
            .iter()
            .all(|row| row.iter_ones().take_while(|&c| c < cols).take(3).count() <= 2)
        {
            return self.eliminate_sparse(cols, full, require_full_rank);
        }
        let block: usize = if n < 512 {
            4
        } else if n < 1536 {
            8
        } else {
            32
        };
        let mut table = vec![BitSet::new(self.shape.1); (1 << block.min(8)) * block.div_ceil(8)];
        let mut reduced = vec![0; n];
        let mut start = 0;
        while start < cols {
            let first = pivots.len();
            let word = start / 64;
            reduced.fill(first);
            let end = cols.min(start + block);
            let mut c = start;
            while c < end {
                let r = pivots.len();
                let mut pivot = None;
                for (i, reduced) in reduced.iter_mut().enumerate().skip(r) {
                    let (upper, lower) = self.data.split_at_mut(i);
                    let row = &mut lower[0];
                    for p in *reduced..r {
                        if row.get(pivots[p]) {
                            xor(&mut row.words_mut()[word..], &upper[p].words()[word..]);
                        }
                    }
                    *reduced = r;
                    if row.get(c) {
                        pivot = Some(i);
                        break;
                    }
                }
                if let Some(p) = pivot {
                    self.data.swap(r, p);
                    reduced.swap(r, p);
                    pivots.push(c);
                    c += 1;
                } else if require_full_rank {
                    return pivots;
                } else {
                    c = self.next_column(r, c + 1, end);
                }
            }
            let rank = pivots.len();
            if first == rank {
                let next = self.next_column(rank, start + block, cols);
                if next == cols {
                    break;
                }
                start = next / block * block;
                continue;
            }
            // Make the panel's pivot columns an identity matrix before indexing its table.
            for r in (first..rank).rev() {
                let (upper, lower) = self.data.split_at_mut(r);
                for row in &mut upper[first..] {
                    if row.get(pivots[r]) {
                        xor(&mut row.words_mut()[word..], &lower[0].words()[word..]);
                    }
                }
            }
            let mut indices = [[0usize; 256]; 4];
            let mut masks = [0usize; 4];
            for group in 0..block.div_ceil(8) {
                let mut keys = [0usize; 256];
                let mut count = 0;
                for (row, &c) in pivots[first..].iter().enumerate() {
                    if (c - start) / 8 != group {
                        continue;
                    }
                    let half = 1 << count;
                    count += 1;
                    for index in 0..half {
                        keys[index + half] = keys[index] | (1 << ((c - start) % 8));
                        let (lower, upper) = table.split_at_mut(group * 256 + index + half);
                        let target = &mut upper[0].words_mut()[word..];
                        let source = &lower[group * 256 + index].words()[word..];
                        let pivot = &self[first + row].words()[word..];
                        for ((x, y), z) in target.iter_mut().zip(source).zip(pivot) {
                            *x = y ^ z;
                        }
                    }
                }
                masks[group] = keys[(1 << count) - 1];
                for (i, &key) in keys[..1 << count].iter().enumerate() {
                    indices[group][key] = i;
                }
            }
            for i in (rank..n).chain(0..if full { first } else { 0 }) {
                let key = (self[i].words()[word] >> (start & 63)) as usize;
                let x = indices[0][key & masks[0]];
                if block <= 8 {
                    if x != 0 {
                        xor(&mut self[i].words_mut()[word..], &table[x].words()[word..]);
                    }
                    continue;
                }
                let y = indices[1][(key >> 8) & masks[1]];
                let z = indices[2][(key >> 16) & masks[2]];
                let w = indices[3][(key >> 24) & masks[3]];
                if x | y | z | w != 0 {
                    let p = &table[x].words()[word..];
                    let q = &table[256 + y].words()[word..];
                    let r = &table[512 + z].words()[word..];
                    let s = &table[768 + w].words()[word..];
                    for ((((x, y), z), r), s) in self[i].words_mut()[word..]
                        .iter_mut()
                        .zip(p)
                        .zip(q)
                        .zip(r)
                        .zip(s)
                    {
                        *x ^= y ^ z ^ r ^ s;
                    }
                }
            }
            if rank == n {
                break;
            }
            start += block;
        }
        pivots
    }

    fn next_column(&self, row: usize, mut start: usize, cols: usize) -> usize {
        while start < cols {
            let word = start / 64;
            let bits = self.data[row..]
                .iter()
                .fold(0, |x, row| x | row.words()[word])
                & (u64::MAX << (start & 63));
            if bits != 0 {
                return (word * 64 + bits.trailing_zeros() as usize).min(cols);
            }
            start = (word + 1) * 64;
        }
        cols
    }

    #[inline(always)]
    fn eliminate_sparse(&mut self, cols: usize, full: bool, require_full_rank: bool) -> Vec<usize> {
        let n = self.shape.0;
        let mut basis = vec![n; cols];
        let mut pivots = Vec::new();
        for i in 0..n {
            loop {
                let Some(c) = self[i].iter_ones().next().filter(|&c| c < cols) else {
                    if require_full_rank {
                        return pivots;
                    }
                    break;
                };
                if basis[c] == n {
                    basis[c] = i;
                    pivots.push(c);
                    break;
                }
                let (upper, lower) = self.data.split_at_mut(i);
                xor(
                    &mut lower[0].words_mut()[c / 64..],
                    &upper[basis[c]].words()[c / 64..],
                );
            }
        }
        pivots.sort_unstable();
        self.data
            .sort_by_cached_key(|row| row.iter_ones().next().filter(|&c| c < cols).unwrap_or(cols));
        if full {
            for (i, &c) in pivots.iter().enumerate() {
                basis[c] = i;
            }
            for i in (0..pivots.len()).rev() {
                let next = self[i].iter_ones().take_while(|&c| c < cols).nth(1);
                if let Some(c) = next
                    && basis[c] != n
                {
                    let (upper, lower) = self.data.split_at_mut(basis[c]);
                    xor(
                        &mut upper[i].words_mut()[c / 64..],
                        &lower[0].words()[c / 64..],
                    );
                }
            }
        }
        pivots
    }

    #[inline(always)]
    fn mul_impl(&self, rhs: &Self) -> Self {
        let mut result = Self::zeros((self.shape.0, rhs.shape.1));
        let ones = self.data.iter().map(BitSet::count_ones).sum::<u64>();
        let size = self.shape.0 as u64 * self.shape.1 as u64;
        if self.shape.0 < 256 || self.shape.1 < 32 || ones <= size / 8 {
            for (a, c) in self.data.iter().zip(&mut result.data) {
                for j in a.iter_ones() {
                    xor(c.words_mut(), rhs[j].words());
                }
            }
            return result;
        }
        if size - ones <= size / 8 {
            let mut sum = BitSet::new(rhs.shape.1);
            for row in &rhs.data {
                sum ^= row;
            }
            for (a, c) in self.data.iter().zip(&mut result.data) {
                c.words_mut().copy_from_slice(sum.words());
                for j in (!a.clone()).iter_ones() {
                    xor(c.words_mut(), rhs[j].words());
                }
            }
            return result;
        }
        let width = rhs.shape.1.div_ceil(64);
        if width == 0 {
            return result;
        }

        // Separate the table groups by a cache line to avoid mapping them to the same sets.
        let group = 256 * width + 8;
        let mut storage = BitSet::new(8 * group * 64);
        let table = storage.words_mut();
        for start in (0..self.shape.1).step_by(64) {
            for (t, table) in table.chunks_exact_mut(group).enumerate() {
                let col = start + t * 8;
                for bit in 0..self.shape.1.saturating_sub(col).min(8) {
                    let row = rhs[col + bit].words();
                    let half = (1 << bit) * width;
                    let (lower, upper) = table.split_at_mut(half);
                    for (source, dest) in
                        lower.chunks_exact(width).zip(upper.chunks_exact_mut(width))
                    {
                        for ((x, y), z) in dest.iter_mut().zip(source).zip(row) {
                            *x = y ^ z;
                        }
                    }
                }
            }
            for (a, c) in self.data.iter().zip(&mut result.data) {
                let key = a.words()[start / 64];
                let offset = (key & 255) as usize * width;
                let p0 = &table[offset..offset + width];
                let offset = group + (key >> 8 & 255) as usize * width;
                let p1 = &table[offset..offset + width];
                let offset = 2 * group + (key >> 16 & 255) as usize * width;
                let p2 = &table[offset..offset + width];
                let offset = 3 * group + (key >> 24 & 255) as usize * width;
                let p3 = &table[offset..offset + width];
                let offset = 4 * group + (key >> 32 & 255) as usize * width;
                let p4 = &table[offset..offset + width];
                let offset = 5 * group + (key >> 40 & 255) as usize * width;
                let p5 = &table[offset..offset + width];
                let offset = 6 * group + (key >> 48 & 255) as usize * width;
                let p6 = &table[offset..offset + width];
                let offset = 7 * group + (key >> 56 & 255) as usize * width;
                let p7 = &table[offset..offset + width];
                for ((((((((x, p0), p1), p2), p3), p4), p5), p6), p7) in c
                    .words_mut()
                    .iter_mut()
                    .zip(p0)
                    .zip(p1)
                    .zip(p2)
                    .zip(p3)
                    .zip(p4)
                    .zip(p5)
                    .zip(p6)
                    .zip(p7)
                {
                    *x ^= p0 ^ p1 ^ p2 ^ p3 ^ p4 ^ p5 ^ p6 ^ p7;
                }
            }
        }
        result
    }

crates/competitive/src/data_structure/bitset.rs (line 52)

    pub fn from_binary(s: &str) -> Option<Self> {
        let bytes = s.as_bytes();
        let mut bits = Self::new(bytes.len());
        let end = bytes.len() / 64 * 64;
        #[cfg(target_arch = "x86_64")]
        let parsed = if avx512_enabled() && is_x86_feature_detected!("avx512bw") {
            // SAFETY: AVX-512BW is available; each complete chunk contains 64 bytes.
            unsafe { simd::parse_binary_avx512(&bytes[..end], bits.words_mut()) }
        } else if is_x86_feature_detected!("avx2") {
            // SAFETY: AVX2 is available; each complete chunk contains 64 bytes.
            unsafe { simd::parse_binary_avx2(&bytes[..end], bits.words_mut()) }
        } else {
            Self::parse_binary_scalar(&bytes[..end], bits.words_mut())
        };
        #[cfg(not(target_arch = "x86_64"))]
        let parsed = Self::parse_binary_scalar(&bytes[..end], bits.words_mut());
        if !parsed {
            return None;
        }
        if end != bytes.len() {
            let mut word = 0;
            for (i, &b) in bytes[end..].iter().enumerate() {
                if b != b'0' && b != b'1' {
                    return None;
                }
                word |= u64::from(b & 1) << i;
            }
            bits.words_mut()[end / 64] = word;
        }
        Some(bits)
    }

    fn parse_binary_scalar(bytes: &[u8], words: &mut [u64]) -> bool {
        for (chunk, word) in bytes.as_chunks::<64>().0.iter().zip(words) {
            for (i, byte) in chunk.as_chunks::<8>().0.iter().enumerate() {
                let x = u64::from_le_bytes(*byte);
                if x & 0xfefe_fefe_fefe_fefe != 0x3030_3030_3030_3030 {
                    return false;
                }
                *word |= ((x & 0x0101_0101_0101_0101).wrapping_mul(0x0102_0408_1020_4080) >> 56)
                    << (i * 8);
            }
        }
        true
    }

    /// Returns ASCII `0` and `1` in increasing bit-index order.
    pub fn to_binary(&self) -> String {
        const TABLE: [[u8; 8]; 256] = {
            let mut table = [[b'0'; 8]; 256];
            let mut i = 0;
            while i < 256 {
                let mut j = 0;
                while j < 8 {
                    table[i][j] |= ((i >> j) & 1) as u8;
                    j += 1;
                }
                i += 1;
            }
            table
        };
        let mut bytes = vec![b'0'; self.size.div_ceil(8) * 8];
        #[cfg(target_arch = "x86_64")]
        let end = if self.size >= 64 && avx512_enabled() && is_x86_feature_detected!("avx512bw") {
            let end = self.size / 64 * 64;
            // SAFETY: AVX-512BW is available; each output chunk holds one 64-bit word.
            unsafe {
                simd::write_binary_avx512(&mut bytes[..end], self.words());
            }
            end
        } else if self.size >= 64 && is_x86_feature_detected!("avx2") {
            let end = self.size / 64 * 64;
            // SAFETY: AVX2 is available; each output chunk holds one complete 64-bit word.
            unsafe {
                simd::write_binary_avx2(&mut bytes[..end], self.words());
            }
            end
        } else {
            0
        };
        #[cfg(not(target_arch = "x86_64"))]
        let end = 0;
        for (chunk, &word) in bytes[end..].chunks_mut(64).zip(&self.words()[end / 64..]) {
            for (i, byte) in chunk.as_chunks_mut::<8>().0.iter_mut().enumerate() {
                byte.copy_from_slice(&TABLE[(word >> (i * 8) & 255) as usize]);
            }
        }
        bytes.truncate(self.size);
        // SAFETY: every output byte is ASCII `0` or `1`.
        unsafe { String::from_utf8_unchecked(bytes) }
    }

    pub fn ones(size: usize) -> Self {
        let mut self_ = Self {
            size,
            bits: vec![Block([u64::MAX; 8]); size.div_ceil(512)],
        };
        self_.trim();
        self_
    }

    pub fn get(&self, i: usize) -> bool {
        self.bits[i >> 9].0[i >> 6 & 7] & (1 << (i & 63)) != 0
    }

    pub fn set(&mut self, i: usize, b: bool) {
        let word = &mut self.bits[i >> 9].0[i >> 6 & 7];
        if b {
            *word |= 1 << (i & 63);
        } else {
            *word &= !(1 << (i & 63));
        }
    }

    /// Clears all bits.
    pub fn reset(&mut self) {
        self.bits.fill(Block::default());
    }

    /// Sets all bits to `value`.
    pub fn fill(&mut self, value: bool) {
        self.bits.fill(Block([if value { u64::MAX } else { 0 }; 8]));
        self.trim();
    }

    /// Tests whether any bit is set.
    #[inline]
    pub fn any(&self) -> bool {
        !self.none()
    }

    /// Tests whether all bits are unset.
    #[inline]
    pub fn none(&self) -> bool {
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if self.bits[0].0[0] != 0 {
                return false;
            }
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                return unsafe { simd::none_avx512(&self.bits) };
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                return unsafe { simd::none_avx2(&self.bits) };
            }
        }
        self.words().iter().all(|&word| word == 0)
    }

    /// Tests whether all bits are set.
    #[inline(always)]
    pub fn all(&self) -> bool {
        let words = self.words();
        let full_words = self.size >> 6;
        #[cfg(target_arch = "x86_64")]
        if self.size >> 9 >= SIMD_MIN_BLOCKS {
            let full_blocks = self.size >> 9;
            if words[0] != u64::MAX {
                return false;
            }
            let full_blocks_are_set = if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                Some(unsafe { simd::all_avx512(&self.bits[..full_blocks]) })
            } else if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                Some(unsafe { simd::all_avx2(&self.bits[..full_blocks]) })
            } else {
                None
            };
            if let Some(full_blocks_are_set) = full_blocks_are_set {
                return full_blocks_are_set
                    && words[full_blocks * 8..full_words]
                        .iter()
                        .all(|&word| word == u64::MAX)
                    && (self.size & 63 == 0
                        || words[full_words] == u64::MAX >> (64 - (self.size & 63)));
            }
        }
        if self.size & 63 == 0 {
            return words.iter().all(|&word| word == u64::MAX);
        }
        words[..full_words].iter().all(|&word| word == u64::MAX)
            && words[full_words] == u64::MAX >> (64 - (self.size & 63))
    }

    /// Iterates over set-bit indices in ascending order.
    pub fn iter_ones(&self) -> impl Iterator<Item = usize> + '_ {
        self.words()
            .iter()
            .copied()
            .enumerate()
            .flat_map(|(word_index, mut word)| {
                std::iter::from_fn(move || {
                    if word == 0 {
                        None
                    } else {
                        let bit = word.trailing_zeros() as usize;
                        word &= word - 1;
                        Some((word_index << 6) | bit)
                    }
                })
            })
    }

    /// Counts set bits.
    #[inline]
    pub fn count_ones(&self) -> u64 {
        let words = self.words();
        #[cfg(target_arch = "x86_64")]
        if words.len() >= 8 {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vpopcntdq")
            {
                // SAFETY: blocks are aligned and feature detection checked both requirements.
                return unsafe { simd::count_ones_avx512(&self.bits) };
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                return unsafe { simd::count_ones_avx2(&self.bits) };
            }
        }
        words.iter().map(|word| word.count_ones() as u64).sum()
    }

    /// Counts unset bits.
    #[inline]
    pub fn count_zeros(&self) -> u64 {
        self.size as u64 - self.count_ones()
    }

    pub fn push(&mut self, b: bool) {
        if self.size & 511 == 0 {
            self.bits.push(Block::default());
        }
        if b {
            self.bits[self.size >> 9].0[self.size >> 6 & 7] |= 1 << (self.size & 63);
        }
        self.size += 1;
    }

    pub fn resize(&mut self, new_size: usize) {
        match self.size.cmp(&new_size) {
            Ordering::Less => self.bits.resize(new_size.div_ceil(512), Block::default()),
            Ordering::Equal => {}
            Ordering::Greater => self.bits.truncate(new_size.div_ceil(512)),
        }
        self.size = new_size;
        self.trim();
    }

    /// Assigns `self | (self << rhs)` to `self`.
    #[inline]
    pub fn shl_bitor_assign(&mut self, rhs: usize) {
        self.shift_left::<true>(rhs);
    }

    /// Assigns `self | (self >> rhs)` to `self`.
    #[inline]
    pub fn shr_bitor_assign(&mut self, rhs: usize) {
        self.shift_right::<true>(rhs);
    }

    /// Returns words in increasing bit-index order; unused high bits in the last word are zero.
    pub fn words(&self) -> &[u64] {
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts(self.bits.as_ptr().cast(), self.size.div_ceil(64)) }
    }

    /// Returns mutable words in increasing bit-index order.
    /// Callers must keep unused high bits in the last word zero.
    pub fn words_mut(&mut self) -> &mut [u64] {
        let len = self.size.div_ceil(64);
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts_mut(self.bits.as_mut_ptr().cast(), len) }
    }

    fn trim(&mut self) {
        let used_words = self.size.div_ceil(64) & 7;
        if let Some(last) = self.bits.last_mut() {
            if self.size & 63 != 0 {
                last.0[(self.size >> 6) & 7] &= u64::MAX >> (64 - (self.size & 63));
            }
            if used_words != 0 {
                last.0[used_words..].fill(0);
            }
        }
    }

    #[inline]
    fn bitop_assign<const OP: u8>(&mut self, rhs: &Self) {
        assert_eq!(
            self.size, rhs.size,
            "bitwise operations require equal lengths"
        );
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                unsafe { simd::bitop_avx512::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                unsafe { simd::bitop_avx2::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
        }
        for (lhs, &rhs) in self.words_mut().iter_mut().zip(rhs.words()) {
            *lhs = match OP {
                BIT_AND => *lhs & rhs,
                BIT_OR => *lhs | rhs,
                BIT_XOR => *lhs ^ rhs,
                _ => unreachable!(),
            };
        }
    }

    #[inline]
    fn shift_left<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_left_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                if self.size & 511 != 0 {
                    self.trim();
                }
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_left_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                if self.size & 63 != 0 {
                    self.trim();
                }
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in (0..bits.len() - word_shift).rev() {
                if OR_ASSIGN {
                    bits[i + word_shift] |= bits[i];
                } else {
                    bits[i + word_shift] = bits[i];
                }
            }
        } else {
            for i in (1..bits.len() - word_shift).rev() {
                let value = (bits[i] << bit_shift) | (bits[i - 1] >> (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i + word_shift] |= value;
                } else {
                    bits[i + word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[word_shift] |= bits[0] << bit_shift;
            } else {
                bits[word_shift] = bits[0] << bit_shift;
            }
        }
        if !OR_ASSIGN {
            bits[..word_shift].fill(0);
        }
        if self.size & 63 != 0 {
            self.trim();
        }
    }

    #[inline]
    fn shift_right<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_right_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_right_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in word_shift..bits.len() {
                if OR_ASSIGN {
                    bits[i - word_shift] |= bits[i];
                } else {
                    bits[i - word_shift] = bits[i];
                }
            }
        } else {
            for i in word_shift..bits.len() - 1 {
                let value = (bits[i] >> bit_shift) | (bits[i + 1] << (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i - word_shift] |= value;
                } else {
                    bits[i - word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[bits.len() - word_shift - 1] |= bits[bits.len() - 1] >> bit_shift;
            } else {
                bits[bits.len() - word_shift - 1] = bits[bits.len() - 1] >> bit_shift;
            }
        }
        if !OR_ASSIGN {
            let end = bits.len() - word_shift;
            bits[end..].fill(0);
        }
    }
}

impl Extend<bool> for BitSet {
    fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T) {
        for bit in iter {
            self.push(bit);
        }
    }
}

impl FromIterator<bool> for BitSet {
    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
        let mut set = BitSet::new(0);
        set.extend(iter);
        set
    }
}

impl ShlAssign<usize> for BitSet {
    #[inline]
    fn shl_assign(&mut self, rhs: usize) {
        self.shift_left::<false>(rhs);
    }
}

impl Shl<usize> for BitSet {
    type Output = Self;
    fn shl(mut self, rhs: usize) -> Self::Output {
        self <<= rhs;
        self
    }
}

impl ShrAssign<usize> for BitSet {
    #[inline]
    fn shr_assign(&mut self, rhs: usize) {
        self.shift_right::<false>(rhs);
    }
}

impl Shr<usize> for BitSet {
    type Output = Self;
    fn shr(mut self, rhs: usize) -> Self::Output {
        self >>= rhs;
        self
    }
}

impl BitOrAssign<&BitSet> for BitSet {
    #[inline]
    fn bitor_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_OR>(rhs);
    }
}

impl BitOr<&BitSet> for BitSet {
    type Output = Self;
    fn bitor(mut self, rhs: &Self) -> Self::Output {
        self |= rhs;
        self
    }
}

impl BitOr<&BitSet> for &BitSet {
    type Output = BitSet;
    fn bitor(self, rhs: &BitSet) -> Self::Output {
        let mut res = self.clone();
        res |= rhs;
        res
    }
}

impl BitAndAssign<&BitSet> for BitSet {
    #[inline]
    fn bitand_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_AND>(rhs);
    }
}

impl BitAnd<&BitSet> for BitSet {
    type Output = Self;
    fn bitand(mut self, rhs: &Self) -> Self::Output {
        self &= rhs;
        self
    }
}

impl BitAnd<&BitSet> for &BitSet {
    type Output = BitSet;
    fn bitand(self, rhs: &BitSet) -> Self::Output {
        let mut res = self.clone();
        res &= rhs;
        res
    }
}

impl BitXorAssign<&BitSet> for BitSet {
    #[inline]
    fn bitxor_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_XOR>(rhs);
    }
}

impl BitXor<&BitSet> for BitSet {
    type Output = Self;
    fn bitxor(mut self, rhs: &Self) -> Self::Output {
        self ^= rhs;
        self
    }
}

impl BitXor<&BitSet> for &BitSet {
    type Output = BitSet;
    fn bitxor(self, rhs: &BitSet) -> Self::Output {
        let mut res = self.clone();
        res ^= rhs;
        res
    }
}

impl Not for BitSet {
    type Output = Self;
    fn not(mut self) -> Self::Output {
        for word in self.words_mut() {
            *word = !*word;
        }
        self.trim();
        self
    }

crates/library_checker/src/linear_algebra/matrix_rank_mod_2.rs (line 22)

pub fn matrix_rank_mod_2(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, m);
    // Transpose very tall matrices to avoid allocating millions of short rows.
    let transpose = n / 2 > m;
    let mut a = BitMatrix::zeros(if transpose { (m, n) } else { (n, m) });
    if transpose && m >= 64 {
        let mut words = vec![0u64; m];
        for first in (0..n).step_by(64) {
            words.fill(0);
            for i in 0..64.min(n - first) {
                sc!(row: &str);
                for (word, b) in words.iter_mut().zip(row.bytes()) {
                    *word |= u64::from(b == b'1') << i;
                }
            }
            for (row, &word) in a.data.iter_mut().zip(&words) {
                row.words_mut()[first / 64] = word;
            }
        }
    } else {
        for i in 0..if m == 0 { 0 } else { n } {
            sc!(row: &str);
            if !transpose {
                a.data[i] = BitSet::from_binary(row).unwrap();
            } else {
                for (j, b) in row.bytes().enumerate() {
                    a[j].words_mut()[i / 64] |= u64::from(b == b'1') << (i % 64);
                }
            }
            if transpose
                && i == 63
                && BitMatrix::new_with((m, 64), |row, col| a[row].get(col)).rank() == m
            {
                pp!(m);
                return;
            }
        }
    }
    pp!(a.rank());
}

fn trim(&mut self)

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 142)

    pub fn ones(size: usize) -> Self {
        let mut self_ = Self {
            size,
            bits: vec![Block([u64::MAX; 8]); size.div_ceil(512)],
        };
        self_.trim();
        self_
    }

    pub fn get(&self, i: usize) -> bool {
        self.bits[i >> 9].0[i >> 6 & 7] & (1 << (i & 63)) != 0
    }

    pub fn set(&mut self, i: usize, b: bool) {
        let word = &mut self.bits[i >> 9].0[i >> 6 & 7];
        if b {
            *word |= 1 << (i & 63);
        } else {
            *word &= !(1 << (i & 63));
        }
    }

    /// Clears all bits.
    pub fn reset(&mut self) {
        self.bits.fill(Block::default());
    }

    /// Sets all bits to `value`.
    pub fn fill(&mut self, value: bool) {
        self.bits.fill(Block([if value { u64::MAX } else { 0 }; 8]));
        self.trim();
    }

    /// Tests whether any bit is set.
    #[inline]
    pub fn any(&self) -> bool {
        !self.none()
    }

    /// Tests whether all bits are unset.
    #[inline]
    pub fn none(&self) -> bool {
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if self.bits[0].0[0] != 0 {
                return false;
            }
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                return unsafe { simd::none_avx512(&self.bits) };
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                return unsafe { simd::none_avx2(&self.bits) };
            }
        }
        self.words().iter().all(|&word| word == 0)
    }

    /// Tests whether all bits are set.
    #[inline(always)]
    pub fn all(&self) -> bool {
        let words = self.words();
        let full_words = self.size >> 6;
        #[cfg(target_arch = "x86_64")]
        if self.size >> 9 >= SIMD_MIN_BLOCKS {
            let full_blocks = self.size >> 9;
            if words[0] != u64::MAX {
                return false;
            }
            let full_blocks_are_set = if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                Some(unsafe { simd::all_avx512(&self.bits[..full_blocks]) })
            } else if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                Some(unsafe { simd::all_avx2(&self.bits[..full_blocks]) })
            } else {
                None
            };
            if let Some(full_blocks_are_set) = full_blocks_are_set {
                return full_blocks_are_set
                    && words[full_blocks * 8..full_words]
                        .iter()
                        .all(|&word| word == u64::MAX)
                    && (self.size & 63 == 0
                        || words[full_words] == u64::MAX >> (64 - (self.size & 63)));
            }
        }
        if self.size & 63 == 0 {
            return words.iter().all(|&word| word == u64::MAX);
        }
        words[..full_words].iter().all(|&word| word == u64::MAX)
            && words[full_words] == u64::MAX >> (64 - (self.size & 63))
    }

    /// Iterates over set-bit indices in ascending order.
    pub fn iter_ones(&self) -> impl Iterator<Item = usize> + '_ {
        self.words()
            .iter()
            .copied()
            .enumerate()
            .flat_map(|(word_index, mut word)| {
                std::iter::from_fn(move || {
                    if word == 0 {
                        None
                    } else {
                        let bit = word.trailing_zeros() as usize;
                        word &= word - 1;
                        Some((word_index << 6) | bit)
                    }
                })
            })
    }

    /// Counts set bits.
    #[inline]
    pub fn count_ones(&self) -> u64 {
        let words = self.words();
        #[cfg(target_arch = "x86_64")]
        if words.len() >= 8 {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vpopcntdq")
            {
                // SAFETY: blocks are aligned and feature detection checked both requirements.
                return unsafe { simd::count_ones_avx512(&self.bits) };
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                return unsafe { simd::count_ones_avx2(&self.bits) };
            }
        }
        words.iter().map(|word| word.count_ones() as u64).sum()
    }

    /// Counts unset bits.
    #[inline]
    pub fn count_zeros(&self) -> u64 {
        self.size as u64 - self.count_ones()
    }

    pub fn push(&mut self, b: bool) {
        if self.size & 511 == 0 {
            self.bits.push(Block::default());
        }
        if b {
            self.bits[self.size >> 9].0[self.size >> 6 & 7] |= 1 << (self.size & 63);
        }
        self.size += 1;
    }

    pub fn resize(&mut self, new_size: usize) {
        match self.size.cmp(&new_size) {
            Ordering::Less => self.bits.resize(new_size.div_ceil(512), Block::default()),
            Ordering::Equal => {}
            Ordering::Greater => self.bits.truncate(new_size.div_ceil(512)),
        }
        self.size = new_size;
        self.trim();
    }

    /// Assigns `self | (self << rhs)` to `self`.
    #[inline]
    pub fn shl_bitor_assign(&mut self, rhs: usize) {
        self.shift_left::<true>(rhs);
    }

    /// Assigns `self | (self >> rhs)` to `self`.
    #[inline]
    pub fn shr_bitor_assign(&mut self, rhs: usize) {
        self.shift_right::<true>(rhs);
    }

    /// Returns words in increasing bit-index order; unused high bits in the last word are zero.
    pub fn words(&self) -> &[u64] {
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts(self.bits.as_ptr().cast(), self.size.div_ceil(64)) }
    }

    /// Returns mutable words in increasing bit-index order.
    /// Callers must keep unused high bits in the last word zero.
    pub fn words_mut(&mut self) -> &mut [u64] {
        let len = self.size.div_ceil(64);
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts_mut(self.bits.as_mut_ptr().cast(), len) }
    }

    fn trim(&mut self) {
        let used_words = self.size.div_ceil(64) & 7;
        if let Some(last) = self.bits.last_mut() {
            if self.size & 63 != 0 {
                last.0[(self.size >> 6) & 7] &= u64::MAX >> (64 - (self.size & 63));
            }
            if used_words != 0 {
                last.0[used_words..].fill(0);
            }
        }
    }

    #[inline]
    fn bitop_assign<const OP: u8>(&mut self, rhs: &Self) {
        assert_eq!(
            self.size, rhs.size,
            "bitwise operations require equal lengths"
        );
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                unsafe { simd::bitop_avx512::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                unsafe { simd::bitop_avx2::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
        }
        for (lhs, &rhs) in self.words_mut().iter_mut().zip(rhs.words()) {
            *lhs = match OP {
                BIT_AND => *lhs & rhs,
                BIT_OR => *lhs | rhs,
                BIT_XOR => *lhs ^ rhs,
                _ => unreachable!(),
            };
        }
    }

    #[inline]
    fn shift_left<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_left_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                if self.size & 511 != 0 {
                    self.trim();
                }
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_left_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                if self.size & 63 != 0 {
                    self.trim();
                }
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in (0..bits.len() - word_shift).rev() {
                if OR_ASSIGN {
                    bits[i + word_shift] |= bits[i];
                } else {
                    bits[i + word_shift] = bits[i];
                }
            }
        } else {
            for i in (1..bits.len() - word_shift).rev() {
                let value = (bits[i] << bit_shift) | (bits[i - 1] >> (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i + word_shift] |= value;
                } else {
                    bits[i + word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[word_shift] |= bits[0] << bit_shift;
            } else {
                bits[word_shift] = bits[0] << bit_shift;
            }
        }
        if !OR_ASSIGN {
            bits[..word_shift].fill(0);
        }
        if self.size & 63 != 0 {
            self.trim();
        }
    }

    #[inline]
    fn shift_right<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_right_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_right_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in word_shift..bits.len() {
                if OR_ASSIGN {
                    bits[i - word_shift] |= bits[i];
                } else {
                    bits[i - word_shift] = bits[i];
                }
            }
        } else {
            for i in word_shift..bits.len() - 1 {
                let value = (bits[i] >> bit_shift) | (bits[i + 1] << (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i - word_shift] |= value;
                } else {
                    bits[i - word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[bits.len() - word_shift - 1] |= bits[bits.len() - 1] >> bit_shift;
            } else {
                bits[bits.len() - word_shift - 1] = bits[bits.len() - 1] >> bit_shift;
            }
        }
        if !OR_ASSIGN {
            let end = bits.len() - word_shift;
            bits[end..].fill(0);
        }
    }
}

impl Extend<bool> for BitSet {
    fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T) {
        for bit in iter {
            self.push(bit);
        }
    }
}

impl FromIterator<bool> for BitSet {
    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
        let mut set = BitSet::new(0);
        set.extend(iter);
        set
    }
}

impl ShlAssign<usize> for BitSet {
    #[inline]
    fn shl_assign(&mut self, rhs: usize) {
        self.shift_left::<false>(rhs);
    }
}

impl Shl<usize> for BitSet {
    type Output = Self;
    fn shl(mut self, rhs: usize) -> Self::Output {
        self <<= rhs;
        self
    }
}

impl ShrAssign<usize> for BitSet {
    #[inline]
    fn shr_assign(&mut self, rhs: usize) {
        self.shift_right::<false>(rhs);
    }
}

impl Shr<usize> for BitSet {
    type Output = Self;
    fn shr(mut self, rhs: usize) -> Self::Output {
        self >>= rhs;
        self
    }
}

impl BitOrAssign<&BitSet> for BitSet {
    #[inline]
    fn bitor_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_OR>(rhs);
    }
}

impl BitOr<&BitSet> for BitSet {
    type Output = Self;
    fn bitor(mut self, rhs: &Self) -> Self::Output {
        self |= rhs;
        self
    }
}

impl BitOr<&BitSet> for &BitSet {
    type Output = BitSet;
    fn bitor(self, rhs: &BitSet) -> Self::Output {
        let mut res = self.clone();
        res |= rhs;
        res
    }
}

impl BitAndAssign<&BitSet> for BitSet {
    #[inline]
    fn bitand_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_AND>(rhs);
    }
}

impl BitAnd<&BitSet> for BitSet {
    type Output = Self;
    fn bitand(mut self, rhs: &Self) -> Self::Output {
        self &= rhs;
        self
    }
}

impl BitAnd<&BitSet> for &BitSet {
    type Output = BitSet;
    fn bitand(self, rhs: &BitSet) -> Self::Output {
        let mut res = self.clone();
        res &= rhs;
        res
    }
}

impl BitXorAssign<&BitSet> for BitSet {
    #[inline]
    fn bitxor_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_XOR>(rhs);
    }
}

impl BitXor<&BitSet> for BitSet {
    type Output = Self;
    fn bitxor(mut self, rhs: &Self) -> Self::Output {
        self ^= rhs;
        self
    }
}

impl BitXor<&BitSet> for &BitSet {
    type Output = BitSet;
    fn bitxor(self, rhs: &BitSet) -> Self::Output {
        let mut res = self.clone();
        res ^= rhs;
        res
    }
}

impl Not for BitSet {
    type Output = Self;
    fn not(mut self) -> Self::Output {
        for word in self.words_mut() {
            *word = !*word;
        }
        self.trim();
        self
    }

fn bitop_assign<const OP: u8>(&mut self, rhs: &Self)

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 543)

    fn bitor_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_OR>(rhs);
    }
}

impl BitOr<&BitSet> for BitSet {
    type Output = Self;
    fn bitor(mut self, rhs: &Self) -> Self::Output {
        self |= rhs;
        self
    }
}

impl BitOr<&BitSet> for &BitSet {
    type Output = BitSet;
    fn bitor(self, rhs: &BitSet) -> Self::Output {
        let mut res = self.clone();
        res |= rhs;
        res
    }
}

impl BitAndAssign<&BitSet> for BitSet {
    #[inline]
    fn bitand_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_AND>(rhs);
    }
}

impl BitAnd<&BitSet> for BitSet {
    type Output = Self;
    fn bitand(mut self, rhs: &Self) -> Self::Output {
        self &= rhs;
        self
    }
}

impl BitAnd<&BitSet> for &BitSet {
    type Output = BitSet;
    fn bitand(self, rhs: &BitSet) -> Self::Output {
        let mut res = self.clone();
        res &= rhs;
        res
    }
}

impl BitXorAssign<&BitSet> for BitSet {
    #[inline]
    fn bitxor_assign(&mut self, rhs: &Self) {
        self.bitop_assign::<BIT_XOR>(rhs);
    }

fn shift_left<const OR_ASSIGN: bool>(&mut self, rhs: usize)

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 301)

    pub fn shl_bitor_assign(&mut self, rhs: usize) {
        self.shift_left::<true>(rhs);
    }

    /// Assigns `self | (self >> rhs)` to `self`.
    #[inline]
    pub fn shr_bitor_assign(&mut self, rhs: usize) {
        self.shift_right::<true>(rhs);
    }

    /// Returns words in increasing bit-index order; unused high bits in the last word are zero.
    pub fn words(&self) -> &[u64] {
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts(self.bits.as_ptr().cast(), self.size.div_ceil(64)) }
    }

    /// Returns mutable words in increasing bit-index order.
    /// Callers must keep unused high bits in the last word zero.
    pub fn words_mut(&mut self) -> &mut [u64] {
        let len = self.size.div_ceil(64);
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts_mut(self.bits.as_mut_ptr().cast(), len) }
    }

    fn trim(&mut self) {
        let used_words = self.size.div_ceil(64) & 7;
        if let Some(last) = self.bits.last_mut() {
            if self.size & 63 != 0 {
                last.0[(self.size >> 6) & 7] &= u64::MAX >> (64 - (self.size & 63));
            }
            if used_words != 0 {
                last.0[used_words..].fill(0);
            }
        }
    }

    #[inline]
    fn bitop_assign<const OP: u8>(&mut self, rhs: &Self) {
        assert_eq!(
            self.size, rhs.size,
            "bitwise operations require equal lengths"
        );
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                unsafe { simd::bitop_avx512::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                unsafe { simd::bitop_avx2::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
        }
        for (lhs, &rhs) in self.words_mut().iter_mut().zip(rhs.words()) {
            *lhs = match OP {
                BIT_AND => *lhs & rhs,
                BIT_OR => *lhs | rhs,
                BIT_XOR => *lhs ^ rhs,
                _ => unreachable!(),
            };
        }
    }

    #[inline]
    fn shift_left<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_left_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                if self.size & 511 != 0 {
                    self.trim();
                }
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_left_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                if self.size & 63 != 0 {
                    self.trim();
                }
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in (0..bits.len() - word_shift).rev() {
                if OR_ASSIGN {
                    bits[i + word_shift] |= bits[i];
                } else {
                    bits[i + word_shift] = bits[i];
                }
            }
        } else {
            for i in (1..bits.len() - word_shift).rev() {
                let value = (bits[i] << bit_shift) | (bits[i - 1] >> (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i + word_shift] |= value;
                } else {
                    bits[i + word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[word_shift] |= bits[0] << bit_shift;
            } else {
                bits[word_shift] = bits[0] << bit_shift;
            }
        }
        if !OR_ASSIGN {
            bits[..word_shift].fill(0);
        }
        if self.size & 63 != 0 {
            self.trim();
        }
    }

    #[inline]
    fn shift_right<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_right_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_right_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in word_shift..bits.len() {
                if OR_ASSIGN {
                    bits[i - word_shift] |= bits[i];
                } else {
                    bits[i - word_shift] = bits[i];
                }
            }
        } else {
            for i in word_shift..bits.len() - 1 {
                let value = (bits[i] >> bit_shift) | (bits[i + 1] << (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i - word_shift] |= value;
                } else {
                    bits[i - word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[bits.len() - word_shift - 1] |= bits[bits.len() - 1] >> bit_shift;
            } else {
                bits[bits.len() - word_shift - 1] = bits[bits.len() - 1] >> bit_shift;
            }
        }
        if !OR_ASSIGN {
            let end = bits.len() - word_shift;
            bits[end..].fill(0);
        }
    }
}

impl Extend<bool> for BitSet {
    fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T) {
        for bit in iter {
            self.push(bit);
        }
    }
}

impl FromIterator<bool> for BitSet {
    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
        let mut set = BitSet::new(0);
        set.extend(iter);
        set
    }
}

impl ShlAssign<usize> for BitSet {
    #[inline]
    fn shl_assign(&mut self, rhs: usize) {
        self.shift_left::<false>(rhs);
    }

fn shift_right<const OR_ASSIGN: bool>(&mut self, rhs: usize)

Examples found in repository

crates/competitive/src/data_structure/bitset.rs (line 307)

    pub fn shr_bitor_assign(&mut self, rhs: usize) {
        self.shift_right::<true>(rhs);
    }

    /// Returns words in increasing bit-index order; unused high bits in the last word are zero.
    pub fn words(&self) -> &[u64] {
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts(self.bits.as_ptr().cast(), self.size.div_ceil(64)) }
    }

    /// Returns mutable words in increasing bit-index order.
    /// Callers must keep unused high bits in the last word zero.
    pub fn words_mut(&mut self) -> &mut [u64] {
        let len = self.size.div_ceil(64);
        // SAFETY: `Block` is exactly eight contiguous `u64`s, with no trailing padding.
        unsafe { std::slice::from_raw_parts_mut(self.bits.as_mut_ptr().cast(), len) }
    }

    fn trim(&mut self) {
        let used_words = self.size.div_ceil(64) & 7;
        if let Some(last) = self.bits.last_mut() {
            if self.size & 63 != 0 {
                last.0[(self.size >> 6) & 7] &= u64::MAX >> (64 - (self.size & 63));
            }
            if used_words != 0 {
                last.0[used_words..].fill(0);
            }
        }
    }

    #[inline]
    fn bitop_assign<const OP: u8>(&mut self, rhs: &Self) {
        assert_eq!(
            self.size, rhs.size,
            "bitwise operations require equal lengths"
        );
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled() && is_x86_feature_detected!("avx512f") {
                // SAFETY: blocks are 64-byte aligned and feature detection checked AVX-512F.
                unsafe { simd::bitop_avx512::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: 64-byte alignment also satisfies AVX2 and feature detection checked it.
                unsafe { simd::bitop_avx2::<OP>(&mut self.bits, &rhs.bits) };
                return;
            }
        }
        for (lhs, &rhs) in self.words_mut().iter_mut().zip(rhs.words()) {
            *lhs = match OP {
                BIT_AND => *lhs & rhs,
                BIT_OR => *lhs | rhs,
                BIT_XOR => *lhs ^ rhs,
                _ => unreachable!(),
            };
        }
    }

    #[inline]
    fn shift_left<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_left_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                if self.size & 511 != 0 {
                    self.trim();
                }
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_left_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                if self.size & 63 != 0 {
                    self.trim();
                }
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in (0..bits.len() - word_shift).rev() {
                if OR_ASSIGN {
                    bits[i + word_shift] |= bits[i];
                } else {
                    bits[i + word_shift] = bits[i];
                }
            }
        } else {
            for i in (1..bits.len() - word_shift).rev() {
                let value = (bits[i] << bit_shift) | (bits[i - 1] >> (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i + word_shift] |= value;
                } else {
                    bits[i + word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[word_shift] |= bits[0] << bit_shift;
            } else {
                bits[word_shift] = bits[0] << bit_shift;
            }
        }
        if !OR_ASSIGN {
            bits[..word_shift].fill(0);
        }
        if self.size & 63 != 0 {
            self.trim();
        }
    }

    #[inline]
    fn shift_right<const OR_ASSIGN: bool>(&mut self, rhs: usize) {
        if rhs == 0 {
            return;
        }
        if rhs >= self.size {
            if !OR_ASSIGN {
                self.reset();
            }
            return;
        }
        #[cfg(target_arch = "x86_64")]
        if self.bits.len() >= SIMD_MIN_BLOCKS {
            if avx512_enabled()
                && is_x86_feature_detected!("avx512f")
                && is_x86_feature_detected!("avx512vbmi2")
            {
                // SAFETY: blocks are aligned and feature detection checked AVX-512F and VBMI2.
                unsafe { simd::shift_right_avx512::<OR_ASSIGN>(&mut self.bits, rhs) };
                return;
            }
            if is_x86_feature_detected!("avx2") {
                // SAFETY: feature detection checked AVX2 support.
                unsafe { simd::shift_right_avx2::<OR_ASSIGN>(self.words_mut(), rhs) };
                return;
            }
        }

        let bits = self.words_mut();
        let word_shift = rhs >> 6;
        let bit_shift = rhs & 63;
        if bit_shift == 0 {
            for i in word_shift..bits.len() {
                if OR_ASSIGN {
                    bits[i - word_shift] |= bits[i];
                } else {
                    bits[i - word_shift] = bits[i];
                }
            }
        } else {
            for i in word_shift..bits.len() - 1 {
                let value = (bits[i] >> bit_shift) | (bits[i + 1] << (64 - bit_shift));
                if OR_ASSIGN {
                    bits[i - word_shift] |= value;
                } else {
                    bits[i - word_shift] = value;
                }
            }
            if OR_ASSIGN {
                bits[bits.len() - word_shift - 1] |= bits[bits.len() - 1] >> bit_shift;
            } else {
                bits[bits.len() - word_shift - 1] = bits[bits.len() - 1] >> bit_shift;
            }
        }
        if !OR_ASSIGN {
            let end = bits.len() - word_shift;
            bits[end..].fill(0);
        }
    }
}

impl Extend<bool> for BitSet {
    fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T) {
        for bit in iter {
            self.push(bit);
        }
    }
}

impl FromIterator<bool> for BitSet {
    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
        let mut set = BitSet::new(0);
        set.extend(iter);
        set
    }
}

impl ShlAssign<usize> for BitSet {
    #[inline]
    fn shl_assign(&mut self, rhs: usize) {
        self.shift_left::<false>(rhs);
    }
}

impl Shl<usize> for BitSet {
    type Output = Self;
    fn shl(mut self, rhs: usize) -> Self::Output {
        self <<= rhs;
        self
    }
}

impl ShrAssign<usize> for BitSet {
    #[inline]
    fn shr_assign(&mut self, rhs: usize) {
        self.shift_right::<false>(rhs);
    }

Trait Implementations

impl BitAnd<&BitSet> for BitSet

type Output = BitSet

The resulting type after applying the & operator.

fn bitand(self, rhs: &Self) -> Self::Output

Performs the & operation.

impl BitAnd<&BitSet> for &BitSet

type Output = BitSet

The resulting type after applying the & operator.

fn bitand(self, rhs: &BitSet) -> Self::Output

Performs the & operation.

impl BitAndAssign<&BitSet> for BitSet

fn bitand_assign(&mut self, rhs: &Self)

Performs the &= operation.

impl BitOr<&BitSet> for BitSet

type Output = BitSet

The resulting type after applying the | operator.

fn bitor(self, rhs: &Self) -> Self::Output

Performs the | operation.

impl BitOr<&BitSet> for &BitSet

type Output = BitSet

The resulting type after applying the | operator.

fn bitor(self, rhs: &BitSet) -> Self::Output

Performs the | operation.

impl BitOrAssign<&BitSet> for BitSet

fn bitor_assign(&mut self, rhs: &Self)

Performs the |= operation.

impl BitXor<&BitSet> for BitSet

type Output = BitSet

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: &Self) -> Self::Output

Performs the ^ operation.

impl BitXor<&BitSet> for &BitSet

type Output = BitSet

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: &BitSet) -> Self::Output

Performs the ^ operation.

impl BitXorAssign<&BitSet> for BitSet

fn bitxor_assign(&mut self, rhs: &Self)

Performs the ^= operation.

impl Clone for BitSet

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BitSet

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for BitSet

fn default() -> Self

Returns the “default value” for a type.

impl Eq for BitSet

impl Extend<bool> for BitSet

fn extend<T: IntoIterator<Item = bool>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl FromIterator<bool> for BitSet

fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self

Creates a value from an iterator.

impl Hash for BitSet

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Not for BitSet

type Output = BitSet

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl Not for &BitSet

type Output = BitSet

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl Ord for BitSet

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

fn clamp_to<R>(self, range: R) -> Self

where Self: Sized, R: ClampBounds<Self>,

🔬This is a nightly-only experimental API. (clamp_to)

Restrict a value to a certain range.

impl PartialEq for BitSet

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl PartialOrd for BitSet

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Shl<usize> for BitSet

type Output = BitSet

The resulting type after applying the << operator.

fn shl(self, rhs: usize) -> Self::Output

Performs the << operation.

impl ShlAssign<usize> for BitSet

fn shl_assign(&mut self, rhs: usize)

Performs the <<= operation.

impl Shr<usize> for BitSet

type Output = BitSet

The resulting type after applying the >> operator.

fn shr(self, rhs: usize) -> Self::Output

Performs the >> operation.

impl ShrAssign<usize> for BitSet

fn shr_assign(&mut self, rhs: usize)

Performs the >>= operation.

impl StructuralPartialEq for BitSet