java.util.BitSet - set () не работает должным образом

Question

Я что-то упускаю до боли? Или просто никто в мире не использует java.util.BitSet?

Следующий тест не пройден:

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

Мне действительно непонятно, почему я не получаю BitSet длины 2 и значения 10. Я заглянул в источник для java.util.BitSet, и при случайной проверке кажется, что он не может провести достаточного различия между битом, который был установлен в ложь, и битом, который никогда не был установлен в какое-либо значение ...

(Обратите внимание, что явная установка размера BitSet в конструкторе не имеет никакого эффекта, например ::

BitSet b = new BitSet(2);

Answer 1

Ваш старший установленный бит (как в «set to 1») - это бит 0. Таким образом, длина должна быть 1.

См. JavaDoc для длины :

public int length ()

Возвращает «логический размер» этого BitSet: индекс самого высокого установленного бита в BitSet плюс один. Возвращает ноль, если BitSet не содержит установленных битов.

Может быть, вы ищете размер , хотя возможно, что он может быть выше , чем два, если биты выделяются с определенным разрешением (скажем, 16-битные границы)?

Answer 2

Люди используют BitSet; однако они используют это для чего-то другого, чем то, что вы намереваетесь. Вероятно, лучше всего думать о BitSet как о очень компактной, экономичной по форме памяти форме Set<Integer>, которая обладает особым свойством, что вы не можете помещать в нее отрицательные числа.

Очень часто с BitSet s их используют по шаблону

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

после того, как вы что-то сделаете, чтобы заполнить их. Это эквивалентно итерации по элементам Set.

Answer 3

Это меня тоже озадачило, не будучи уверенным в обоснованности нынешней довольно неожиданной функциональности BitSet. Однако, поскольку он не окончательный, мы можем использовать некоторые тактики объятия и расширения и сделать следующее, чтобы получить фиксированный BitSet с семантикой длины, как и ожидалось:

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

Учитывая, что набор битов поддерживается long [], минимальный размер равен 64 (потому что 1 long равен 64 битам). Размер увеличивается на кратное 64, и по какой-то причине они не сохранили количество бит, которое вы намеревались представить, когда вы используете конструктор, который принимает int.

Answer 5

// Абхай Дандекар

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() );

    }
}

Простая Java-программа, показывающая, что происходит внутри. Некоторые моменты, на которые стоит обратить внимание:

1. BitSet поддерживается длинным

2. Все значения по умолчанию ложны

3. Возвращая длину, он возвращает индекс + 1 самого высокого «истинного» значения в наборе.

Вывод ниже должен быть в состоянии объяснить себя:

State 0 : 64 : 0

State 1 : 64 : 2

State 2 : 64 : 2

State 3 : 64 : 5

Итак, нужно сделать вывод:

1. Не используйте длину для определения количества битов, измененных

2. Может использоваться в сценариях, таких как фильтры Блума. Подробнее о фильтрах Блума можно гуглить ..;)

Надеюсь, это поможет

С уважением,

Абхай Дандекар

Answer 6

Добрый Каспер! Ваше небольшое улучшение действительно должно было присутствовать в оригинальной версии Java BitSet! Я также предлагаю это (append () и concat () полезны для различного использования)

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);
  }

}