BitSet
BitSet implementa un conjunto de bits compacto sobre una capacidad fija, respaldado por un array de palabras de 64 bits, con operaciones de conjunto.
Construcción
| Sintaxis | Descripción |
|---|---|
BitSet(n) | Crea un conjunto de bits con capacidad para n bits, todos inicialmente en cero |
BitSet.fromArray(arr) | Crea un conjunto de bits con los bits de las posiciones en arr activados |
fromArray requiere un argumento usize[]. Las posiciones de bits están indexadas desde 0 hasta n - 1.
Métodos
| Método | Firma | Retorno | Descripción |
|---|---|---|---|
set | (index: usize, value?: boolean) => void | void | Activa, desactiva o define condicionalmente el bit en index (por defecto: true) |
flip | (index: usize) => void | void | Alterna el bit en index |
get | (index: usize) => boolean | boolean | Si el bit en index está activado |
count | () => usize | usize | Número de bits activados |
isEmpty | () => boolean | boolean | Si no hay bits activados |
isSubset | (other: BitSet) => boolean | boolean | Si todo bit activado también está activado en other |
isSuperset | (other: BitSet) => boolean | boolean | Si todo bit activado en other también está activado |
union | (other: BitSet) => BitSet | BitSet | Conjunto de bits con todos los bits de ambos conjuntos |
intersection | (other: BitSet) => BitSet | BitSet | Conjunto de bits con los bits activados en ambos |
difference | (other: BitSet) => BitSet | BitSet | Conjunto de bits con bits activados aquí pero no en other |
complement | () => BitSet | BitSet | Conjunto de bits con cada bit alternado sobre la capacidad |
clear | () => void | void | Limpia todos los bits |
union, intersection, difference y complement devuelven un BitSet nuevo propiedad del llamador; se libera automáticamente cuando la variable sale del ámbito.
Complejidad
| Operación | Complejidad de Tiempo |
|---|---|
set | O(1) |
flip | O(1) |
get | O(1) |
count | O(n), número de palabras de máquina |
isEmpty | O(n), número de palabras de máquina |
isSubset | O(n), número de palabras de máquina |
isSuperset | O(n), número de palabras de máquina |
union | O(n), número de palabras de máquina |
intersection | O(n), número de palabras de máquina |
difference | O(n), número de palabras de máquina |
complement | O(n), número de palabras de máquina |
clear | O(n), número de palabras de máquina |
Ejemplos
Construcción
tyrus
import { BitSet } from "tyrus:algorithm";
const bs = BitSet(100);set y get
tyrus
const bs = BitSet(100);
bs.set(5);
bs.set(10, true);
bs.set(3, false);
print(bs.get(5)); // true
print(bs.get(3)); // false
print(bs.get(10)); // trueflip
tyrus
const bs = BitSet(100);
bs.set(3);
print(bs.get(3)); // true
bs.flip(3);
print(bs.get(3)); // falsecount e isEmpty
tyrus
const bs = BitSet(100);
print(bs.count()); // 0
print(bs.isEmpty()); // true
bs.set(1);
bs.set(2);
print(bs.count()); // 2
print(bs.isEmpty()); // falseisSubset y isSuperset
tyrus
const a = BitSet(100);
a.set(1);
a.set(3);
const b = BitSet(100);
b.set(1);
b.set(3);
b.set(5);
print(a.isSubset(b)); // true
print(b.isSuperset(a)); // true
print(b.isSubset(a)); // falseunion, intersection y difference
tyrus
const a = BitSet(100);
a.set(1);
a.set(3);
a.set(5);
const b = BitSet(100);
b.set(3);
b.set(5);
b.set(7);
print(a.union(b).count()); // 4
print(a.intersection(b).count()); // 2
print(a.difference(b).count()); // 1complement
tyrus
const bs = BitSet(100);
bs.set(3);
bs.set(5);
bs.set(7);
print(bs.complement().count()); // 97
print(bs.complement().get(1)); // truefromArray
tyrus
const indexes: usize[] = [3, 5, 10];
const bs = BitSet.fromArray(indexes);
print(bs.count()); // 3
print(bs.get(10)); // true
print(bs.get(4)); // falseclear
tyrus
const bs = BitSet(100);
bs.set(1);
bs.set(2);
print(bs.isEmpty()); // false
bs.clear();
print(bs.isEmpty()); // true