почему BitSet использует long[] размера 6 / Java

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Java [игнор отключен] [закрыт для гостей] / почему BitSet использует long[] размера 6

25 сообщений из 26, страница 1 из 2

все

почему BitSet использует long[] размера 6

#39391093

questioner

Гость

Стыдно, но не могу вспомнить теорию, позволяющую понять

почему BitSet-у достаточно шести лонгов, чтобы хранить массив размера 2^31-1 битов.

судя по тому, что
2 бита позволяют закодировать 4 разных числа
3 бита - 8, то
(2^31)-1 битов, то нам нужно число диапазона 2^((2^31)-1 ).

Как это вяжется с шестью 64 битными лонгами - не понимаю.

ну или пойти с другой стороны:

лонг это 64 бита, 6 лонгов это 64*8 битов.

это ведь всяко много меньше (2^31)-1

Объясните пожалуйста

...

Рейтинг:

0 / 0

25.01.2017, 13:44

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391114

Blazkowicz

Участник

Сообщения: 25 080

Рейтинг: 0 / 0

questionerпочему BitSet-у достаточно шести лонгов, чтобы хранить массив размера 2^31-1 битов.

Подтверждено эксперементально?

questionerлонг это 64 бита, 6 лонгов это 64*8 битов.

Что-то с арифметикой тут тоже не так.

...

Рейтинг:

0 / 0

25.01.2017, 13:57

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391281

Сергей Арсеньев

Участник

Сообщения: 4 121

Рейтинг: 0 / 0

BlazkowiczПодтверждено эксперементально?
Наверно человек так понял
java.util.BitSet/*
* BitSets are packed into arrays of "words." Currently a word is
* a long, which consists of 64 bits, requiring 6 address bits.
* The choice of word size is determined purely by performance concerns.
*/

...

Рейтинг:

0 / 0

25.01.2017, 16:01

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391285

questioner

Гость

Сергей АрсеньевBlazkowiczПодтверждено эксперементально?
Наверно человек так понял
java.util.BitSet/*
* BitSets are packed into arrays of "words." Currently a word is
* a long, which consists of 64 bits, requiring 6 address bits.
* The choice of word size is determined purely by performance concerns.
*/

Да, вы правы,а как это правильно истолковать?

Blazkowicz Что-то с арифметикой тут тоже не так.

Очепятка 64*6 конечно

...

Рейтинг:

0 / 0

25.01.2017, 16:03

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391300

Сергей Арсеньев

Участник

Сообщения: 4 121

Рейтинг: 0 / 0

questioner,

Ну примерно так.
Хранится в массиве long[]
Для того чтобы узнать в каком по счету long хранится бит
делается следующая операция

Код: java

1.
2.
3.

 private static int  wordIndex(int bitIndex) {
         return bitIndex >> ADDRESS_BITS_PER_WORD;
     }

Собственно установка бита делается (если упростить для понимания, откинув всякие expand)

Код: java

words[wordIndex(bitIndex)] |= (1L << bitIndex);

...

Рейтинг:

0 / 0

25.01.2017, 16:22

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391328

questioner

Гость

Сергей Арсеньевquestioner,

Собственно установка бита делается (если упростить для понимания, откинув всякие expand)

Код: java

words[wordIndex(bitIndex)] |= (1L << bitIndex);

|=

а что за операция такая?

long h |= (1L << 2);

так например нельзя написать

...

Рейтинг:

0 / 0

25.01.2017, 16:49

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391330

Сергей Арсеньев

Участник

Сообщения: 4 121

Рейтинг: 0 / 0

questioner,

http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

...

Рейтинг:

0 / 0

25.01.2017, 16:51

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391334

Сергей Арсеньев

Участник

Сообщения: 4 121

Рейтинг: 0 / 0

questioner,

для |= надо иметь предыдущее значение.
это эквивалент h = h |

...

Рейтинг:

0 / 0

25.01.2017, 16:52

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391337

questioner

Гость

Сергей Арсеньевquestioner,

для |= надо иметь предыдущее значение.
это эквивалент h = h |

аа понятно это OR

Теперь по поводу выбора нужного long.

Почему смещение именно на 6 ?

...

Рейтинг:

0 / 0

25.01.2017, 16:55

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391339

Сергей Арсеньев

Участник

Сообщения: 4 121

Рейтинг: 0 / 0

questioner,

2^6=?

...

Рейтинг:

0 / 0

25.01.2017, 16:56

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391368

Blazkowicz

Участник

Сообщения: 25 080

Рейтинг: 0 / 0

questioner,

long это "слово" в реализации BitSet его размер 64 бита
Чтобы получить бит по индексу надо произвести две операции
1. Получить индекс long-а в массиве
2. Получить индекс бит-а внутри long-а

индекс long-а это индекс бита делённый на 64
64 = 2^6
деление на 64 эквивалентно сдвигу на 6 позиций
вот и выходит
индекс long-а это индекс бита >> 6

Код: java

1.
2.
3.

private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
}

Индекс бита внутри лонга это остаток от деления индекса бита на 64. Но нам особо не нужен, так как long это не массив - по индексу не адресуешь.

Для того чтобы проверить или установить значение бита нужно наложить маску на этот бит. Для получения маски берём единицу 1L и сдвигаем влево на нужную позицию. Сдвиг цикличный, поэтому не паримся на счет границ.

...

Рейтинг:

0 / 0

25.01.2017, 17:21

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391437

questioner

Гость

Blazkowicz,

Спасибо, разжевали.

Один момент только не уловил:

Код: java

1L << bitIndex

пуска у нас индекс попал в первый лонг (он же нулевой)

и пусть это будет 20(аргумент метода set).

1 это же

0...[63 штуки]1

1<<20

это ведь будет 0...[39 штук] 10...[20 штук]

и получится, что мы установили 40 бит вместо 20

...

Рейтинг:

0 / 0

25.01.2017, 18:14

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391444

questioner

Гость

или они с конца пронумерованы?

...

Рейтинг:

0 / 0

25.01.2017, 18:23

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391446

Blazkowicz

Участник

Сообщения: 25 080

Рейтинг: 0 / 0

questioner,

Код: java

1.
2.
3.
4.
5.

        System.out.println(Long.toBinaryString(1L));
        System.out.println(Long.toBinaryString(1L << 20));

1
100000000000000000000

...

Рейтинг:

0 / 0

25.01.2017, 18:24

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391447

Alexey Tomin

Участник

Откуда: Самара

Сообщения: 1 715

Рейтинг: 0 / 0

questioner1<<20
это ведь будет 0...[39 штук] 10...[20 штук]
и получится, что мы установили 40 бит вместо 20

Какая разница? Число никто не видит. А get так же сработает.

...

Рейтинг:

0 / 0

25.01.2017, 18:25

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391448

Blazkowicz

Участник

Сообщения: 25 080

Рейтинг: 0 / 0

questionerили они с конца пронумерованы?
А есть принципиальная разница?

...

Рейтинг:

0 / 0

25.01.2017, 18:25

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391450

questioner

Гость

Blazkowiczquestionerили они с конца пронумерованы?
А есть принципиальная разница?

это объясняет почему используется сдвиг единицы влево. Для клиента класса разницы никакой.

...

Рейтинг:

0 / 0

25.01.2017, 18:26

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391454

Blazkowicz

Участник

Сообщения: 25 080

Рейтинг: 0 / 0

questioner,

Я прогнал. Сдвиг в Java не цикличиный. Просто при сдвиге не используются значения дальше размера типа. Для сдвига int только 5 бит, а для сдвига long только 6.

...

Рейтинг:

0 / 0

25.01.2017, 18:30

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391459

questioner

Гость

Blazkowiczquestioner,

Я прогнал. Сдвиг в Java не цикличиный. Просто при сдвиге не используются значения дальше размера типа. Для сдвига int только 5 бит, а для сдвига long только 6.

а что подразумевается под размером типа?(а то у меня в голове цифры 32 и 64 бита соответственно)

допустим прилетоло нам число 70.

мы выяснили, что оно во втором long

дальше идёт операция 1L<< 70

Код: java

1.
2.

System.out.println(1L<< 70);
1000000

похож прям на цикличный

...

Рейтинг:

0 / 0

25.01.2017, 18:37

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391543

Blazkowicz

Участник

Сообщения: 25 080

Рейтинг: 0 / 0

questioner,

Почитай определение операции сдвига в JLS.
Размер int - 32 = 2^5 бита. То есть 5 бит достаточно чтобы адресовать номер бита в int. Поэтому для сдвига используется только 5 бит от значения указывающее на количество сдвигов.
То есть 1L << 70 эквивалентно 1L << 6, потому что 64 это уже 7й бит в значении 70. Он не используется. Для long используется только 6 бит от числа справа (70).

...

Рейтинг:

0 / 0

25.01.2017, 19:45

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391679

questioner

Гость

Blazkowicz,

Подтверждается тем, что

Код: java

1.
2.
3.
4.
5.

   
        System.out.println(1L << 127);
        System.out.println(1L << 191);
        System.out.println(1L << 255);
        System.out.println(1L << 511);

возвращает одно и то же

...

Рейтинг:

0 / 0

26.01.2017, 00:11

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391851

Сергей Арсеньев

Участник

Сообщения: 4 121

Рейтинг: 0 / 0

questionerили они с конца пронумерованы?

YouTube Video

...

Рейтинг:

0 / 0

26.01.2017, 10:45

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391862

Blazkowicz

Участник

Сообщения: 25 080

Рейтинг: 0 / 0

questionerПодтверждается тем, что
...
возвращает одно и то же
Правильно. JLS нам не указ. Эксперимент - наше всё.

...

Рейтинг:

0 / 0

26.01.2017, 10:55

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391881

questioner

Гость

BlazkowiczquestionerПодтверждается тем, что
...
возвращает одно и то же
Правильно. JLS нам не указ. Эксперимент - наше всё.

Нельзя же никому на слово верить)))

...

Рейтинг:

0 / 0

26.01.2017, 11:09

| Ответить | Цитировать | Написать

почему BitSet использует long[] размера 6

#39391896

Сергей Арсеньев

Участник

Сообщения: 4 121

Рейтинг: 0 / 0

questionerпохож прям на цикличный
Похож но не ёж.
Другими словами в качестве аргумента для количества бит на которые сдвигать неявным образом используется остаток от деления на максимальную размерность того числа которое указано.
Другими словами сдвиг на 33 бита это тоже самое что сдвиг на 1.

При циклическом сдвиге влево справа вылезает левый бит. При не циклическом, заранее установленный (0 или например знак отрицательного числа, если двигаем вправо).

на примере int

Код: java

1.
2.
3.
4.
5.
6.
7.
8.
9.

  System.out.println("10000000000000010000000000000001<<1  :"+Integer.toBinaryString(0x80010001<<1));
  System.out.println("1<<31                                :"+Integer.toBinaryString(1<<31));
  System.out.println("1<<32                                :"+Integer.toBinaryString(1<<32));
  System.out.println("10000000000000010000000000000001>>1  :"+Integer.toBinaryString(0x80010001>>1));
  System.out.println("10000000000000010000000000000001>>>1 :"+Integer.toBinaryString(0x80010001>>>1));
  System.out.println("10000000000000000000000000000001>>31 :"+Integer.toBinaryString(0x80000001>>31));
  System.out.println("10000000000000000000000000000001>>>31:"+Integer.toBinaryString(0x80000001>>>31));
  System.out.println("10000000000000000000000000000001>>32 :"+Integer.toBinaryString(0x80000001>>32));
  System.out.println("10000000000000000000000000000001>>>32:"+Integer.toBinaryString(0x80000001>>>32));

...

Рейтинг:

0 / 0

26.01.2017, 11:18

| Ответить | Цитировать | Написать

25 сообщений из 26, страница 1 из 2

все

Форумы / Java [игнор отключен] [закрыт для гостей] / почему BitSet использует long[] размера 6

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=59&msg=39391448&tid=2123214]:	0ms
get settings:	8ms
get forum list:	12ms
check forum access:	2ms
check topic access:	2ms
track hit:	54ms
get topic data:	7ms
get forum data:	1ms
get page messages:	46ms
get tp. blocked users:	1ms
others:	236ms

total:	369ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы