Skip to content

BitSet ​

BitSet implementa um conjunto de bits compacto sobre uma capacidade fixa, apoiado em um array de palavras de 64 bits, com operações de conjunto.

Construção ​

SintaxeDescrição
BitSet(n)Cria um conjunto de bits com capacidade para n bits, todos inicialmente zerados
BitSet.fromArray(arr)Cria um conjunto de bits com os bits das posições em arr ligados

fromArray exige um argumento usize[]. As posições de bits são indexadas a partir de 0 até n - 1.

Métodos ​

MétodoAssinaturaRetornoDescrição
set(index: usize, value?: boolean) => voidvoidLiga, desliga ou define condicionalmente o bit em index (padrão: true)
flip(index: usize) => voidvoidAlterna o bit em index
get(index: usize) => booleanbooleanSe o bit em index está ligado
count() => usizeusizeNúmero de bits ligados
isEmpty() => booleanbooleanSe nenhum bit está ligado
isSubset(other: BitSet) => booleanbooleanSe todo bit ligado também está ligado em other
isSuperset(other: BitSet) => booleanbooleanSe todo bit ligado em other também está ligado
union(other: BitSet) => BitSetBitSetConjunto de bits com todos os bits de ambos os conjuntos
intersection(other: BitSet) => BitSetBitSetConjunto de bits com os bits ligados em ambos
difference(other: BitSet) => BitSetBitSetConjunto de bits com os bits ligados aqui mas não em other
complement() => BitSetBitSetConjunto de bits com cada bit alternado sobre a capacidade
clear() => voidvoidZera todos os bits

union, intersection, difference e complement retornam um BitSet novo de posse do chamador; ele é liberado automaticamente quando a variável sai de escopo.

Complexidade ​

OperaçãoComplexidade de Tempo
setO(1)
flipO(1)
getO(1)
countO(n), número de palavras de máquina
isEmptyO(n), número de palavras de máquina
isSubsetO(n), número de palavras de máquina
isSupersetO(n), número de palavras de máquina
unionO(n), número de palavras de máquina
intersectionO(n), número de palavras de máquina
differenceO(n), número de palavras de máquina
complementO(n), número de palavras de máquina
clearO(n), número de palavras de máquina

Exemplos ​

Construção ​

tyrus
import { BitSet } from "tyrus:algorithm";

const bs = BitSet(100);

set e 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));  // true

flip ​

tyrus
const bs = BitSet(100);

bs.set(3);

print(bs.get(3));  // true

bs.flip(3);

print(bs.get(3));  // false

count 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());  // false

isSubset e 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));    // false

union, intersection e 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());   // 1

complement ​

tyrus
const bs = BitSet(100);
bs.set(3);
bs.set(5);
bs.set(7);

print(bs.complement().count());  // 97
print(bs.complement().get(1));   // true

fromArray ​

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));   // false

clear ​

tyrus
const bs = BitSet(100);
bs.set(1);
bs.set(2);

print(bs.isEmpty());  // false

bs.clear();

print(bs.isEmpty());  // true