Как реализовать бит в C

Question

Нижеприведенный код, который создает и использует битовый набор, приведен в следующем учебнике "Intro to Bit Vectors". Я переписываю этот код, чтобы попытаться узнать и понять больше о C-структурах и указателях.

#include <stdio.h> 
#include <stdlib.h> 

#define WORDSIZE 32 
#define BITS_WORDSIZE 5 
#define MASK 0x1f 

// Create a bitset 
int initbv(int **bv, int val) { 
    *bv = calloc(val/WORDSIZE + 1, sizeof(int)); 
    return *bv != NULL; 
} 

// Place int 'i' in the biset 
void set(int bv[], int i) { 
    bv[i>>BITS_WORDSIZE] |= (1 << (i & MASK)); 
} 

// Return true if integer 'i' is a member of the bitset 
int member(int bv[], int i) { 
    int boolean = bv[i>>BITS_WORDSIZE] & (1 << (i & MASK)); 
    return boolean; 
} 

int main() { 
    int *bv, i; 

    int s1[] = {32, 5, 0}; 
    int s2[] = {32, 4, 5, 0}; 

    initbv(&bv, 32); 

    // Fill bitset with s1 
    for(i = 0; s1[i]; i++) { 
    set(bv, s1[i]); 
    } 

    // Print intersection of bitset (s1) and s2 
    for(i = 0; s2[i]; i++) { 
    if(member(bv, s2[i])) { 
     printf("%d\n", s2[i]); 
    } 
    } 

    free(bv); 
    return 0; 
} 

Ниже приведен текст, который я переписал, чтобы использовать структуры.

#include <stdio.h> 
#include <stdlib.h> 

#define WORDSIZE 32 
#define BITS_WS 5 
#define MASK 0x1f 

struct bitset { 
    int *bv; 
}; 

/* Create bitset that can hold 'size' items */ 
struct bitset * bitset_new(int size) { 
    struct bitset * set = malloc(sizeof(struct bitset)); 

    set->bv = calloc(size/WORDSIZE + 1, sizeof(int)); 

    return set; 
} 

/* Add an item to a bitset */ 
int bitset_add(struct bitset * this, int item) { 
    return this->bv[item>>BITS_WS] |= (1 << (item & MASK)); 
} 

/* Check if an item is in the bitset */ 
int bitset_lookup(struct bitset * this, int item) { 
int boolean = this->bv[item>>BITS_WS] & (1 << (item & MASK)); 
    printf("%d\n", boolean); 
    return boolean; 
} 

int main() { 
    struct bitset * test = bitset_new(32); 

    int num = 5; 
    bitset_add(test, num); 

    printf("%d\n", bitset_lookup(test, num)); 

    return 0; 
} 

То, что я переписал, не работает должным образом. Чтобы проверить реализацию, в main() я пытаюсь использовать bitet_lookup и ожидать возвращаемое значение 0 или 1, но я получаю значение 32. Я считаю, что это должно быть связано с моим использованием указателей, хотя я не вижу, что я я делаю неправильно.

Любая помощь оценена!

Answer 1

Это не учебник, в лучшем случае это вводящие в заблуждение примеры.

Прежде всего используйте неподписанный тип. Я рекомендую unsigned long (по разным причинам, ни один из них не критичен). Заголовочный файл <limits.h> определяет константу CHAR_BIT, а количество бит, которое вы можете использовать в любом беззнаковом целочисленном типе, всегда равно CHAR_BIT * sizeof (unsigned_type).

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

выше сводится к

#include <stdlib.h> 
#include <limits.h> 

#define ULONG_BITS (CHAR_BIT * sizeof (unsigned long)) 

typedef struct { 
    size_t   ulongs; 
    unsigned long *ulong; 
} bitset; 

#define BITSET_INIT { 0, NULL } 

void bitset_init(bitset *bset) 
{ 
    if (bset) { 
     bset->ulongs = 0; 
     bset->ulong = NULL; 
    } 
} 

void bitset_free(bitset *bset) 
{ 
    if (bset) { 
     free(bset->ulong); 
     bset->ulongs = 0; 
     bset->ulong = NULL; 
    } 
} 

/* Returns: 0 if successfully set 
      -1 if bs is NULL 
      -2 if out of memory. */ 
int bitset_set(bitset *bset, const size_t bit) 
{ 
    if (bset) { 
     const size_t i = bit/ULONG_BITS; 

     /* Need to grow the bitset? */ 
     if (i >= bset->ulongs) { 
      const size_t ulongs = i + 1; /* Use better strategy! */ 
      unsigned long *ulong; 
      size_t   n = bset->ulongs; 

      ulong = realloc(bset->ulong, ulongs * sizeof bset->ulong[0]); 
      if (!ulong) 
       return -2; 

      /* Update the structure to reflect the changes */ 
      bset->ulongs = ulongs; 
      bset->ulong = ulong; 

      /* Clear the newly acquired part of the ulong array */ 
      while (n < ulongs) 
       ulong[n++] = 0UL; 
     } 

     bset->ulong[i] |= 1UL << (bit % ULONG_BITS); 

     return 0; 
    } else 
     return -1; 
} 

/* Returns: 0 if SET 
      1 if UNSET 
      -1 if outside the bitset */ 
int bitset_get(bitset *bset, const size_t bit) 
{ 
    if (bset) { 
     const size_t i = bit/ULONG_BITS; 

     if (i >= bset->ulongs) 
      return -1; 

     return !(bset->ulong[i] & (1UL << (bit % ULONG_BITS))); 
    } else 
     return -1; 
} 

В bitset структуре ulong является динамически распределяемой массив ulongsunsigned long с. Таким образом, он хранит ulongs * ULONG_BITS бит.

BITSET_INIT - макрос препроцессора, который можно использовать для инициализации пустого битового набора. Если вы не можете или не хотите его использовать, вы можете использовать bitset_init() для инициализации битового набора. Эти два эквивалента.

bitset_free() освобождает динамическую память, выделенную для битового набора. После вызова бит устанавливается, и используемая переменная повторно инициализируется. (Обратите внимание, что вполне нормально звонить bitset_free() на неиспользуемый, но инициализированный бит, потому что вызов free(NULL) совершенно безопасен и ничего не делает.)

Поскольку ОС/ядро ​​автоматически освобождает всю память, используемую программой (за исключением определенных типов сегментов разделяемой памяти), нет необходимости вызывать bitset_free() непосредственно перед выходом программы. Но, если вы используете битовые множества как часть некоторого алгоритма, очевидно, что хорошей практикой является освобождение памяти, которая больше не нужна, так что приложение может потенциально работать неограниченно без «утечки» (потери) памяти.

bitset_set() автоматически увеличивает бит при необходимости, но только на столько, сколько необходимо.Это не обязательно хорошая политика перераспределения: /realloc() и т. Д. Звонки относительно медленны, и если вам посчастливилось позвонить bitset_set() в порядке возрастания (увеличивая число бит), вы в конечном итоге вызываете realloc() за каждые ULONG_BITS. Вместо этого часто рекомендуется настраивать новый размер (ulongs) вверх - точная формула, которую вы используете для этого , - ваша политика перераспределения - но предлагая хорошую политику, потребуется практическое тестирование с использованием практических программ. Показанный один работает и достаточно прочен, но может быть немного медленным в некоторых ситуациях. (Вы должны использовать по крайней мере десятки тысяч бит, хотя.)

Возвращаемого значение bitset_get() функции фанка, потому что я хотел функцию, чтобы вернуть аналогичное значение для обоих «сняты с охраной» и " вне битового набора «, потому что они логически похожи. (То есть, я считаю, что набор бит, набор установленных бит;., В этом случае логично думать все биты вне множества, как отключенного)

Гораздо более традиционного определения

int bitset_get(bitset *bset, const size_t bit) 
{ 
    if (bset) { 
     const size_t i = bit/ULONG_BITS; 

     if (i >= bset->ulongs) 
      return 0; 

     return !!(bset->ulong[i] & (1UL << (bit % ULONG_BITS))); 
    } else 
     return 0; 
} 

, который возвращает 1 только для бит, и 0 для бит вне набора.

Примечание !!. Это всего лишь два не оператора, ничего странного; что делает его не оператором. !!x равно 0, если x равно нулю, а 1, если x отличное от нуля.

(Один не оператор, !x, дает 1, если x равен нулю, и 0, если x не равен нулю. Применяя не в два раза приводит к не-я не было объяснено выше.)

Для использования выше, попытайтесь, например,

int main(void) 
{ 
    bitset train = BITSET_INIT; 

    printf("bitset_get(&train, 5) = %d\n", bitset_get(&train, 5)); 

    if (bitset_set(&train, 5)) { 
     printf("Oops; we ran out of memory.\n"); 
     return EXIT_FAILURE; 
    } else 
     printf("Called bitset_set(&train, 5) successfully\n"); 

    printf("bitset_get(&train, 5) = %d\n"); 

    bitset_free(&train); 

    return EXIT_SUCCESS; 
} 

Потому что мы не делаем никаких предположений относительно аппаратного обеспечения или системы, которую мы работаем (если я не goofed где-то, если вы заметите, что я сделал, дайте мне знать в комментариях, так что я могу исправить мой лох!), И только на том, что стандарт C говорит, что мы можем положиться, это должно работать на все, что вы можете скомпилировать с помощью стандартного компилятора. Windows, Linux, BSD, старые Unix, macOS и другие.

С некоторыми изменениями, это может быть сделано для работы на микроконтроллерах, даже. Я не уверен, что все библиотеки разработки имеют realloc(); даже malloc() может быть недоступен. Помимо этого, на таких вещах, как 32-битные ARM, это должно работать как-то прекрасно; на 8-битных AVR и, таким образом, было бы целесообразно использовать unsigned char и CHAR_BIT, вместо этого, поскольку они имеют тенденцию эмулировать более крупные типы, а не поддерживать их в оборудовании. (Код выше работал бы, но был бы медленнее, чем необходимо.)

Answer 2

Возвращаемое значение от bitset_lookup должно рассматриваться как двоичное значение истины (т. Е. Да на нет), а не числовое значение. Если он равен нулю, бит не установлен; если он не равен нулю, бит устанавливается. Действительно, эта функция должна возвращать boolean != 0, что вынуждает ее к нулю или одному, истинному булевому, а не текущему нулю или чему-либо (ну, собственно, (1 << (item & MASK))). C/C++, не имеющий истинного булева, может вызвать такую ​​путаницу.