C/C++ битовый массив или битовый вектор
Я изучаю программирование на C/C++ и столкнулся с использованием "Битовых массивов" или "Битовых векторов". Не в состоянии понять их цель? вот мои сомнения -
- Они используются в качестве логических флагов?
- Можно ли использовать
intвместо массивов? (больше памяти конечно, но..) - Что это за концепция бит-маскировки?
- Если битовая маскировка - это простые битовые операции, чтобы получить соответствующий флаг, как одна программа для них? не сложно ли сделать эту операцию в голове, чтобы увидеть, каким будет флаг, в отличие от десятичных чисел?
Я ищу приложения, чтобы я мог лучше понять. например,
В. Вам предоставляется файл, содержащий целые числа в диапазоне (от 1 до 1 миллиона). Есть некоторые дубликаты и, следовательно, некоторые цифры отсутствуют. Найти самый быстрый способ найти пропущенные номера?
Для вышеупомянутого вопроса я прочитал решения, говорящие мне использовать битовые массивы. Как можно хранить каждое целое число в бите?
5 ответов
Я думаю, что вы запутались между массивами и числами, в частности, что это означает манипулировать двоичными числами.
Я пойду об этом на примере. Скажем, у вас есть несколько сообщений об ошибках, и вы хотите вернуть их в виде возвращаемого значения из функции. Теперь вы можете обозначить свои ошибки 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 */
}
}
Теперь о практичности. Когда памяти было мало, а протоколы не могли позволить себе роскошь многословного 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. проверить индексы нулей: 0,1,4 - это пропущенные числа
Кстати, вы можете использовать целые числа вместо битов, но это может занять (зависит от системы) 32 раза памяти
Сиван
Битовые массивы или битовые векторы могут быть представлены в виде массива логических значений. Обычно для логической переменной требуется как минимум одно байтовое хранилище, но в битовом массиве / векторе требуется только один бит. Это удобно, если у вас много таких данных, поэтому вы экономите память в целом.
Другое использование, если у вас есть числа, которые не вписываются в стандартные переменные размером 8,16,32 или 64 бита. Таким образом, вы можете сохранить в битовом векторе 16-битное число, которое состоит из 4 бит, один из которых является 2-битным, а другой - размером 10 бит. Обычно вам придется использовать 3 переменные с размерами 8,8 и 16 бит, так что вы потеряете только 50% памяти.
Но все эти применения очень редко используются в бизнес-приложениях, которые часто используются при взаимодействии драйверов через функции pinvoke/interop и при низкоуровневом программировании.
Битовые массивы битовых векторов используются в качестве отображения от позиции к некоторому битовому значению. Да, это в основном то же самое, что и массив Bool, но типичная реализация Bool имеет длину от одного до четырех байтов и занимает слишком много места.
Мы можем хранить тот же объем данных гораздо более эффективно, используя массивы слов и двоичные маскирующие операции и сдвиги для их хранения и извлечения (меньше общего объема используемой памяти, меньше обращений к памяти, меньше пропусков кэш-памяти, меньше подкачки страниц памяти). Код для доступа к отдельным битам все еще довольно прост.
Существует также поддержка битовых полей, встроенная в язык Си (вы пишете такие вещи, как 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 и т. Д.