o java.util.BitSet — set() não funciona como esperado

Question

Eu estou faltando alguma coisa dolorosamente óbvio?Não apenas ninguém no mundo, na verdade, usam o java.util.BitSet?

O teste seguinte falha:

@Test
public void testBitSet() throws Exception {
    BitSet b = new BitSet();
    b.set(0, true);
    b.set(1, false);
    assertEquals(2, b.length());
}

É muito claro para mim o porquê de eu não acabar com um BitSet de comprimento 2 e o valor 10.Eu olhei na fonte para java.util.BitSet, e no casual inspeção parece não conseguir fazer o suficiente distinção entre um bit que foi definida falso e um bit que nunca foi definido para qualquer valor de...

(Note que definir explicitamente o tamanho da BitSet no construtor não tem nenhum efeito, por exemplo:

BitSet b = new BitSet(2);

Answer 1

As pessoas usam BitSet; No entanto, eles o usam para algo diferente do que você pretende. Provavelmente é melhor pensar em BitSet como uma forma muito compacta e eficiente de memória de Set<Integer> Isso tem a propriedade peculiar de que você não pode colocar números negativos nela.

É muito comum com BitSets para usá -los no padrão de

for (int id = set.nextSetBit(0); id >= 0; id = set.nextSetBit(id + 1)) {
  // do stuff to a set index
}

Depois de fazer algo para preenchê -los. Isso é equivalente a iterar sobre os elementos do Set.

Answer 2

Seu conjunto de bits mais alto (como em "Set To 1") é Bit 0. Portanto, o comprimento deve ser 1.

Veja o Javadoc por comprimento:

Public int comprimento ()

Retorna o "tamanho lógico" deste bitset: o índice do bit mais alto no bitset mais um. Retorna zero se o bitset não contiver bits definidos.

Talvez você esteja procurando Tamanho Embora seja possível que possa ser mais alto Dois dois se os bits são alocados em uma determinada resolução (digamos, limites de 16 bits)?

Answer 3

Isso me intrigou também, não tenho certeza da lógica por trás da funcionalidade atual e inesperada de Bitset. No entanto, como não é final, podemos usar algumas táticas de abraçar e ampliar e fazer o seguinte para obter um bitset fixo com semântica de comprimento conforme o esperado:

import java.util.BitSet;

/**
 * Variation of BitSet which does NOT interpret the highest bit synonymous with
 * its length.
 *
 * @author casper.bang@gmail.com
 */
public class FixedBitSet extends BitSet{

    int fixedLength;

    public FixedBitSet(int fixedLength){
        super(fixedLength);
        this.fixedLength = fixedLength;
    }

    @Override
    public int length() {
        return fixedLength;
    }
}

Answer 4

Dado que o bitset é apoiado por um longo [], o tamanho mínimo é de 64 (porque 1 comprimento é de 64 bits). O tamanho é incrementado por um múltiplo de 64 e, por algum motivo, eles não mantiveram o número de bits que você pretendia representar quando usa o construtor que leva um Int.

Answer 5

// Abhay Dandekar

import java.util.BitSet;

public class TestBitSet {

    public static void main(String[] args) {

        BitSet bitSet = new BitSet();
        System.out.println("State 0 : " + bitSet.size() + " : " + bitSet.length() );

        bitSet.set(0, true);
        bitSet.set(1, true);
        System.out.println("State 1 : " + bitSet.size() + " : " + bitSet.length() );

        bitSet.set(2, false);
        bitSet.set(3, false);
        System.out.println("State 2 : " + bitSet.size() + " : " + bitSet.length() );

        bitSet.set(4, true);
        System.out.println("State 3 : " + bitSet.size() + " : " + bitSet.length() );

    }
}

Um simples programa em java para mostrar o que acontece dentro.Alguns pontos a observar :

1. BitSet é apoiado por um longo

2. Todos os valores padrão são falsas

3. Ao devolver a duração, ele retorna o índice+1 do mais alto valor "true" em conjunto.

A saída, abaixo, deve ser capaz de explicar a si mesma :

State 0 : 64 : 0

State 1 : 64 : 2

State 2 : 64 : 2

State 3 : 64 : 5

Isso aponta para concluir :

1. Não use o comprimento para concluir o nº de bits modificados

2. Pode ser usado em cenários como filtros de bloom.Mais sobre filtros de bloom pode ser pesquisei ..;)

Espero que isso ajude

Cumprimentos,

Abhay Dandekar

Answer 6

Bom Casper! Sua pequena melhoria deveria estar presente no Bitset Java Def! Eu também sugiro que isso (append () e concat () sejam úteis para vários usos)

import java.util.BitSet;

public class fixBitSet extends BitSet {

  public int fsize = 0;

  public void set(int k, boolean value) {
    if (k >= fsize)
      fsize = k + 1;
    super.set(k, value);
  }

  public void append(fixBitSet bs) {
    for (int k = 0; k < bs.fsize; k++)
      super.set(fsize + k, bs.get(k));
    fsize += bs.fsize;
  }

  public static fixBitSet concat(fixBitSet[] vbs) {
    final fixBitSet bs = new fixBitSet();
    for (fixBitSet xbs : vbs)
      bs.append(xbs);
    return (bs);
  }

}