Бит-бит C/C++ или бит-вектор

Question

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

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

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

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 - те недостающие номера

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

Сиван

Answer 3

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

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

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

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

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