C / C ++ битовый массив или битовый вектор

Question

Я изучаю программирование на C / C ++ и столкнулся с использованием «Битовых массивов» или «Битовых векторов». Не в состоянии понять их цель? вот мои сомнения -

1. Они используются в качестве логических флагов?
2. Можно ли вместо этого использовать int массивы? (больше памяти конечно, но ..)
3. Что это за концепция маскировки битов?
4. Если битовая маскировка - это простые битовые операции для получения соответствующего флага, то как для них запрограммировать одну программу? не трудно ли сделать эту операцию в голове, чтобы увидеть, каким будет флаг, в отличие от десятичных чисел?

Я ищу приложения, чтобы лучше понять. например, -

Q. Вам предоставляется файл, содержащий целые числа в диапазоне (от 1 до 1 миллиона). Есть некоторые дубликаты и, следовательно, некоторые цифры отсутствуют. Найти самый быстрый способ найти пропавших без вести цифры?

Для ответа на поставленный выше вопрос я прочитал решения, предлагающие использовать битовые массивы. Как можно хранить каждое целое число в битах?

Answer 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 */
    }
}

Теперь, к практическим соображениям.Когда памяти было мало, а протоколы не могли позволить себе роскошь многословного xml и т. Д., Было обычным делить поле на ширину в несколько бит.В этом поле вы назначаете различные биты (флаги, степени 2) определенному значению и применяете бинарные операции, чтобы определить, установлены ли они, а затем оперировать ими.

Я также должен добавить, что бинарные операции близкив идее к базовой электронике компьютера.Представьте, соответствуют ли битовые поля выходным сигналам различных цепей (ток или нет).Используя достаточное количество комбинаций указанных цепей, вы делаете ... компьютер.

Answer 2

относительно использования массива битов:

если вы знаете, что существует «только» 1 миллион чисел - вы используете массив из 1 миллиона бит. в начале все биты будут равны нулю, и каждый раз, когда вы читаете число - используйте это число в качестве индекса и измените бит в этом индексе на единицу (если он еще не один).

после прочтения всех чисел - пропущенные числа являются индексами нулей в массиве.

например, если бы у нас были только числа от 0 до 4, массив вначале выглядел бы так: 0 0 0 0 0. если мы читаем цифры: 3, 2, 2 массив будет выглядеть так: читать 3 -> 0 0 0 1 0. читать 3 (снова) -> 0 0 0 1 0. читать 2 -> 0 0 1 1 0. проверять индексы нулей: 0,1,4 - это пропущенные числа

Кстати, конечно, вы можете использовать целые числа вместо битов, но это может занять (зависит от системы) 32 раза памяти

Сиван

Answer 3

Битовые массивы или битовые векторы могут быть как массив логических значений .Обычно для логической переменной требуется как минимум одно байтовое хранилище, но в битовом массиве / векторе требуется только один бит.Это удобно, если у вас много таких данных, поэтому вы экономите память в целом.

Другое использование - если у вас есть числа, которые не совсем соответствуют стандартным переменным , которые равны 8,16,32 или 64 бит в размере.Таким образом, вы можете сохранить в битовом векторе 16-битное число, которое состоит из 4 бит, один из которых является 2-битным, а другой - размером 10 бит.Обычно вам придется использовать 3 переменные с размерами 8,8 и 16 бит, так что у вас тратится всего 50% памяти.

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

Answer 4

Битовые массивы битовых векторов используются в качестве отображения от позиции к некоторому битовому значению. Да, это в основном то же самое, что и массив 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);
                    }
                }
            }
        }
    }
}

Answer 5

Используется для хранения битовых флагов, а также для анализа различных полей двоичных протоколов, где 1 байт делится на несколько битовых полей.Это широко используется в таких протоколах, как TCP / IP, вплоть до кодировок ASN.1, пакетов OpenPGP и т. Д.