Работа с длинными списками битов

Я совершенно не знаком с работой с отдельными битами. Этот вопрос является скорее проверкой здравомыслия, чем что-либо еще:

Мне нужен список, скажем, из миллиона отдельных битов. Для этого я должен создать список 1000000/16 unsigned ints. Затем, перебирая эти unsigned ints, я могу использовать побитовые операторы, чтобы установить для отдельных битов нужные мне значения.

Это правильно, или я действительно туплю? Если я на правильном пути, всегда ли мне гарантируется, что unsigned int будет 16-битным?


c bit-manipulation bit low-level
person providence    schedule 18.11.2011    source источник
comment
Не всегда гарантируется, что unsigned int будет 16-битным, но на большинстве платформ он обычно 32-битный, но это также не гарантируется.   -  person Christian Rau    schedule 19.11.2011

Ответы (3)


arrow_upward
3
arrow_downward

Нет, нет никакой гарантии, что unsigned int будет иметь ширину 16 бит. Вместо этого используйте uint16_t.

Когда вы говорите «список», вы имеете в виду массив или связанный список? Почти наверняка имеет смысл использовать массив, а не связанный список. Это приведет к гораздо лучшему использованию памяти и обеспечит произвольный доступ к отдельным словам/битам.

Если вам нужно, чтобы ваш «длинный список» динамически увеличивался, возможно, имеет смысл рассмотреть двухуровневую структуру, такую ​​как растущий массив (или связанный список) указателей на массивы фиксированного размера из uint16_t. .

Наконец, учитывая, что большинство современных машин являются 32- или 64-разрядными, для этого может быть более эффективно использовать 32- или 64-разрядные слова.

person NPE    schedule 18.11.2011
comment
Извините, не уточнил. На самом деле я смотрел на связанный список, потому что я буду читать/писать только последовательно. Однако память важнее всего, поэтому я переключусь на массивы. Спасибо и за совет uint16_t. - person providence; 19.11.2011

arrow_upward
2
arrow_downward

Это предполагает, что в unsigned int 16 бит. На самом деле это не может быть гарантировано, плюс в большинстве современных систем это будет не менее 32. Вы можете сделать sizeof( int ) * CHAR_BITS, чтобы получить количество битов в int.

person K-ballo    schedule 18.11.2011

arrow_upward
1
arrow_downward

Вы всегда можете проверить размер беззнакового целого числа или использовать uint16_t, определенный в файле cstdint. Кроме того, использование массива вместо списка будет быстрее, поскольку вы устраните поиск. В идеале вы должны получить правильное целое число за постоянное время.

person perreal    schedule 18.11.2011