C / C ++ битовый массив или битовый вектор
https://stackoverflow.com/questions/4604130
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я изучаю программирование C / C ++ и столкнулся с использованием «битных массивов» или «битных векторов». Я не могу понять их цели? Вот мои сомнения -
- Они используются как логические флаги?
- Можно одно использовать
intвместо этого массивы? (Больше памяти конечно, но ..) - Что эта концепция битовой маскировки?
- Если битовая маскировка - простые битные операции, чтобы получить подходящий флаг, как для них одна программа? Нетрудно сделать эту операцию в голове, чтобы увидеть, что будет флаг, как приложение к десятичным числам?
Я ищу приложения, чтобы я мог понять лучше. например,
Q. Вам дан файл, содержащий целые числа в диапазоне (от 1 до 1 миллиона). Есть некоторые дубликаты и, следовательно, некоторые номера отсутствуют. Найдите самый быстрый способ найти недостающие номера?
Для приведенного выше вопроса я прочитал решения, которые говорят мне использовать битные массивы. Как бы один магазин каждая целое число немного?
Решение
Я думаю, что вы не запутались между массивами и цифрами, в частности, что значит манипулировать двоичными числами.
Я пойду об этом настоятельно. Скажем, у вас есть несколько сообщений об ошибках, и вы хотите вернуть их в возвращаемое значение из функции. Теперь вы можете отметить ваши ошибки 1,2,3,4 ... что имеет смысл вашему разуму, но затем, как вы, учитывая только один номер, работают, какие ошибки произошли?
Теперь попробуйте маркировать ошибки 1,2,4,8,16 ... Увеличение мощностей двух, в основном. Почему эта работа? Ну, когда вы работаете на базе 2, вы манипулируете номером, как 00000000 где каждая цифра соответствует мощности 2, умноженной на его положение справа. Итак, скажем, ошибки 1, 4 и 8 происходят. Ну, то это можно было представить как 00001101. Отказ В обратном направлении первая цифра = 1 * 2 ^ 0, третья цифра 1 * 2 ^ 2 и четвертая цифра 1 * 2 ^ 3. Добавляя их все вверх дает вам 13.
Теперь мы можем проверить, произойдет такая ошибка, нанесение бита. Например, если вы хотели работать, если ошибка 8 произошло, используйте битное представление 8 = 00001000. Отказ Теперь, чтобы извлечь, будет ли эта ошибка, используйте двоичный и вроде:
00001101
& 00001000
= 00001000
Я уверен, что вы знаете, как и работает или выбирают его из вышеупомянутой цифры, если любые две цифры являются как 1, результат - это 1, еще это 0.
Теперь в C:
int func(...)
{
int retval = 0;
if ( sometestthatmeans an error )
{
retval += 1;
}
if ( sometestthatmeans an error )
{
retval += 2;
}
return retval
}
int anotherfunc(...)
{
uint8_t x = func(...)
/* binary and with 8 and shift 3 plaes to the right
* so that the resultant expression is either 1 or 0 */
if ( ( ( x & 0x08 ) >> 3 ) == 1 )
{
/* that error occurred */
}
}
Сейчас к практике. Когда память была редкой, и протоколы не имели роскоши Verbose XML и т. Д., Было распространено, чтобы разделить поле как настолько много битов. В этом поле вы назначаете различные биты (флаги, полномочия 2) к определенному значению и применять двоичные операции для вывода, если они установлены, а затем работают на них.
Я также должен добавить, что двоичные операции близки в идее в основную электронику компьютера. Представьте себе, если битовые поля соответствовали выходу различных цепей (несущий ток или нет). Используя достаточно комбинаций указанных цепей, вы делаете ... компьютер.
Другие советы
Что касается использования массива битов:
Если вы знаете, что есть «только» 1 миллион номеров - вы используете массив из 1 миллиона битов. В начале все биты будут нулевыми и каждый раз, когда вы читаете номер - используйте этот номер как индекс и измените бит в этом индексе, чтобы быть одним (если это еще не одно).
После прочтения всех чисел - пропущенные номера являются индексами нулей в массиве.
Например, если бы у нас были только цифры между 0 - 4, массив будет выглядеть так, как это будет выглядеть в начале: 0 0 0 0 0. Если читаем номера: 3, 2, 2 массив будет выглядеть так: Read 3 - > 0 0 0 1 0. Прочитайте 3 (опять же) -> 0 0 0 1 0. Прочитайте 2 -> 0 0 1 1 0. Проверьте индексы Zeroes: 0,1,4 - это отсутствующие номера
Кстати, конечно, вы можете использовать целые числа вместо битов, но это может предпринять (зависит от системы) 32 раз память
Сиван
Битовые массивы или битовые векторы могут быть хоть и как Массив логических ценностей. Отказ Обычно логическая переменная потребности должна по меньшей мере одного байтового хранилища, но в битовом массиве / векторе требуется только один бит. Это удобно, если у вас есть много таких данных, поэтому вы сохраняете память в целом.
Другое использование - если у вас есть номера, которые не совсем не вписываются в стандартные переменные которые имеют 8,16,32 или 64 бит по размеру. Вы сможете так много хранить в немного векторе 16-битного номера, который состоит из 4 битов, тот, который составляет 2 бит и один, который составляет 10 битов в размере. Обычно вам придется использовать 3 переменных с размерами 8,8 и 16 бит, поэтому у вас есть только 50% от потраченной впустую.
Но все эти применения очень редко используются в репликациях для бизнеса, часто используются при взаимодействии драйверов через Pinvoke / Interop. функции и делают Программирование низкого уровня.
Битовые массивы битовых векторов используются в качестве отображения из положения до некоторого значения бит. Да, это в основном то же самое, что и массив Bool, но типичная реализация Bool составляет от одного до четырех байтов, и он использует слишком много места.
Мы можем хранить ту же величину данных гораздо более эффективно, используя массивы слов и операций двоичных маскировков и сдвиги для хранения и извлечения их (менее общей использованной памяти, меньше доступ к памяти, меньшими промывками кэша, меньшей страницы памяти). Код для доступа к индивидуальным битам все еще довольно просто.
Есть также некоторые битовые полевые поддержки встроены в языке C (вы пишете такие вещи, как int i:1; Сказать «только потреблять один бит»), но он не доступен для массивов, и у вас меньше контроля над общим результатом (детали реализации зависит от вопросов компилятора и выравнивания).
Ниже приведен возможность ответить на ваш вопрос «поиск пропущенных номеров». Я зафиксировал размер INT до 32 битов, чтобы сохранить вещи простыми, но его можно было записать с помощью SIZEOF (INT), чтобы сделать его портативным. И (в зависимости от компилятора и целевого процессора) код может быть сделан только более быстрым, используя >> 5 вместо / 32 а также & 31 вместо % 32, но это просто чтобы дать идею.
#include <stdio.h>
#include <errno.h>
#include <stdint.h>
int main(){
/* put all numbers from 1 to 1000000 in a file, except 765 and 777777 */
{
printf("writing test file\n");
int x = 0;
FILE * f = fopen("testfile.txt", "w");
for (x=0; x < 1000000; ++x){
if (x == 765 || x == 777760 || x == 777791){
continue;
}
fprintf(f, "%d\n", x);
}
fprintf(f, "%d\n", 57768); /* this one is a duplicate */
fclose(f);
}
uint32_t bitarray[1000000 / 32];
/* read file containing integers in the range [1,1000000] */
/* any non number is considered as separator */
/* the goal is to find missing numbers */
printf("Reading test file\n");
{
unsigned int x = 0;
FILE * f = fopen("testfile.txt", "r");
while (1 == fscanf(f, " %u",&x)){
bitarray[x / 32] |= 1 << (x % 32);
}
fclose(f);
}
/* find missing number in bitarray */
{
int x = 0;
for (x=0; x < (1000000 / 32) ; ++x){
int n = bitarray[x];
if (n != (uint32_t)-1){
printf("Missing number(s) between %d and %d [%x]\n",
x * 32, (x+1) * 32, bitarray[x]);
int b;
for (b = 0 ; b < 32 ; ++b){
if (0 == (n & (1 << b))){
printf("missing number is %d\n", x*32+b);
}
}
}
}
}
}
Это используется для хранения битовых флагов, а также для разбора различных полей двоичных протоколов, где 1 байт разделен на ряд битовых полей. Это широко используется в протоколах, таких как TCP / IP, до кодировков ASN.1, пакеты OpenPGP и так далее.
