Как использовать бит-поля для сохранения памяти?

Ответ 1

Как отмечено в обширных комментариях, использование битового поля - не выход. Вы можете использовать только 128 байт памяти для вашего набора, содержащего значения 1..1024. Вам нужно будет сопоставить значение N с битом N-1 (так что у вас есть бит 0..1023 для работы). Вам также необходимо решить, какие операции вам нужны для вашего набора. Этот код поддерживает "create", "destroy", "insert", "delete" и "in_set". Он не поддерживает итерацию над элементами в наборе; который может быть добавлен, если вы этого хотите.

sets.h

#ifndef SETS_H_INCLUDED
#define SETS_H_INCLUDED

typedef struct Set Set;
enum { MAX_ELEMENTS = 1024 };

extern Set *create(void);
extern void destroy(Set *set);
extern void insert(Set *set, int value);
extern void delete(Set *set, int value);
extern int in_set(Set *set, int value);

#endif /* SETS_H_INCLUDED */

sets.c

#include "sets.h"
#include <assert.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long Bits;
#define BITS_C(n)  ((Bits)(n))
enum { ARRAY_SIZE = MAX_ELEMENTS / (sizeof(Bits) * CHAR_BIT) };

struct Set
{
     Bits set[ARRAY_SIZE];
};

Set *create(void)
{
    Set *set = malloc(sizeof(*set));
    if (set != 0)
        memset(set, 0, sizeof(*set));
    return set;
}

void destroy(Set *set)
{
    free(set);
}

void insert(Set *set, int value)
{
    assert(value >= 1 && value <= MAX_ELEMENTS);
    value--;  /* 0..1023 */
    int index = value / (sizeof(Bits) * CHAR_BIT);
    int bitnum = value % (sizeof(Bits) * CHAR_BIT);
    Bits mask = BITS_C(1) << bitnum;
    /* printf("I: %d (%d:%d:0x%.2lX)\n", value+1, index, bitnum, mask); */
    set->set[index] |= mask;
}

void delete(Set *set, int value)
{
    assert(value >= 1 && value <= MAX_ELEMENTS);
    value--;  /* 0..1023 */
    int index = value / (sizeof(Bits) * CHAR_BIT);
    int bitnum = value % (sizeof(Bits) * CHAR_BIT);
    Bits mask = BITS_C(1) << bitnum;
    /* printf("D: %d (%d:%d:0x%.2lX)\n", value+1, index, bitnum, mask); */
    set->set[index] &= ~mask;
}

/* C90 does not support <stdbool.h> */
int in_set(Set *set, int value)
{
    assert(value >= 1 && value <= MAX_ELEMENTS);
    value--;  /* 0..1023 */
    int index = value / (sizeof(Bits) * CHAR_BIT);
    int bitnum = value % (sizeof(Bits) * CHAR_BIT);
    Bits mask = BITS_C(1) << bitnum;
    /* printf("T: %d (%d:%d:0x%.2lX) = %d\n", value+1, index, bitnum, mask,
              (set->set[index] & mask) != 0); */
    return (set->set[index] & mask) != 0;
}

#include <stdio.h>

enum { NUMBERS_PER_LINE = 15 };

int main(void)
{
    Set *set = create();
    if (set != 0)
    {
        int i;
        int n = 0;
        for (i = 1; i <= MAX_ELEMENTS; i += 4)
             insert(set, i);
        for (i = 3; i <= MAX_ELEMENTS; i += 6)
             delete(set, i);

        for (i = 1; i <= MAX_ELEMENTS; i++)
        {
             if (in_set(set, i))
             {
                 printf(" %4d", i);
                 if (++n % NUMBERS_PER_LINE == 0)
                 {
                     putchar('\n');
                     n = 0;
                 }
             }
        }
        if (n % NUMBERS_PER_LINE != 0)
            putchar('\n');
        destroy(set);
    }
    return 0;
}

На самом деле функции должны иметь системный префикс, например set_. Макрос BITS_C основан на макросе INT64_C (и других связанных макросах), определенных в <stdint.h> в C99 и более поздних версиях, который также не является частью C90.

Ответ 2

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

Примечание. Вы можете легко изменить тип элемента массива (без знака char) и поэкспериментировать с типами, которые могут содержать больше битов (например, unsigned int) и проверить, работают ли они лучше с точки зрения скорости. Вы также можете изменить код, чтобы он обрабатывал элементы размером более одного бита.

#include <stdio.h>
#include <limits.h>

unsigned int get_el(unsigned char* array, unsigned int index)
{
    unsigned int bits_per_arr_el = sizeof(unsigned char)*CHAR_BIT;
    unsigned int arr_index = index / bits_per_arr_el;
    unsigned int bit_offset = index % bits_per_arr_el;
    unsigned int bitmask = 1 << bit_offset;
    unsigned int retval;

    // printf("index=%u\n", index);
    // printf("bits_per_arr_el=%u\n", bits_per_arr_el);
    // printf("arr_index=%u\n", arr_index);
    // printf("bit_offset=%u\n", bit_offset);

    retval = array[arr_index] & bitmask ? 1 : 0; // can be simpler if only True/False is needed
    return(retval);
}

#define MAX_SIZE 10
unsigned char bitarray[MAX_SIZE];

int main()
{
    bitarray[1] = 3; // 00000011
    printf("array[7]=%u, array[8]=%u, array[9]=%u, array[10]=%u\n",
            get_el(bitarray, 7),
            get_el(bitarray, 8),
            get_el(bitarray, 9),
            get_el(bitarray,10));

    return 0;
}

выходы

array[7]=0, array[8]=1, array[9]=1, array[10]=0

Ответ 3

typedef struct set
{
    unsigned short var:10; // uint var:1 will be padded to 32 bits
} SET;                     // ushort var:10 (which is max<=1024) padded to 16 bits

Как комментировал @Jonathan Leffler использовать массив (unsigned short []) и определить битмаски

#define bitZer 0x00  //(unsigned)(0 == 0)? true:true;
#define bitOne 0x10  // so from (both inclusive)0-1023 = 1024
...                  // added for clarification  
#define bitTen 0x0A

чтобы просмотреть бит каждого элемента. http://www.catb.org/esr/structure-packing/ подробный

Ответ 4

1) Правильное решение для этого вопроса - использовать бит-массив

Вопрос предоставил решение с битными полями с помощью Struct. Существует два типичных способа экономии памяти для проблем, связанных с битами, другой - использование Бит-массива. Для этого конкретного случая в вопросе лучшим способом является использование бит-массива (показано ниже).

• Если это так, как чисто независимые битовые флаги, для Бит-массив
• Если существует группа релевантных битов, таких как IP-адрес или определение управляющего слова, тогда лучше комбинировать их со структурой, то есть использовать Поля бит со Sturct

2) Пример кода только для демонстрационного битового массива

#include<limits.h>
#define BITS_OF_INT (sizeof(int)*CHAR_BIT)  
void SetBit(int A[], int k)
     {
       //Set the bit at the k-th position
       A[k/BITS_OF_INT] |= 1 <<(k%BITS_OF_INT);
     } 
void ClearBit(int A[], int k)
     {
       //RESET the bit at the k-th position
       A[k/BITS_OF_INT] &= ~(1 <<(k%BITS_OF_INT)) ;
     }  
int TestBit(int A[], int k)
     {
       // Return TRUE if bit set    
       return ((A[k/BITS_OF_INT] & (1 <<(k%BITS_OF_INT)))!= 0) ;
     }

#define MAX_SIZE 1024
int main()
{
    int A[MAX_SIZE/BITS_OF_INT];
    int i;
    int pos = 100; // position

    for (i = 0; i < MAX_SIZE/BITS_OF_INT; i++)
        A[i] = 0; 

    SetBit(A, pos);
    if (TestBit(A, pos)){//do something}
    ClearBit(A, pos); 
}

3) Кроме того, целесообразным обсуждением этого вопроса является

Как выбрать правильное решение между "Бит-матрицей" и "Бит-полями со структурой"?

Вот несколько ссылок на эту тему.

• Когда использовать бит-поля в C?

• Считываемые и поддерживаемые битовые поля в C

Ответ 5

Чтобы сохранить значение от 0 до 1023 (или от 1 до 1024, что по сути то же самое и только включает в себя добавление/вычитание 1), вам нужно минимум 10 бит.

Это означает, что для 32-битных (беззнаковых) целых чисел вы можете упаковать 3 значения в 30 бит, что дает 2 бита бесполезной прокладки.

Пример:

%define ELEMENTS 100

uint32_t myArray[ (ELEMENTS + 2) / 3 ];

void setValue(int n, int value) {
    uint32_t temp;
    uint32_t mask = (1 << 10) - 1;

    if(n >= ELEMENTS) return;
    value--;                        // Convert "1 to 1024" into "0 to 1023"
    temp = myArray[n / 3];
    mask = mask << (n % 3)*10;
    temp = (temp & ~mask) | (value << (n % 3)*10);
    myArray[n / 3] = temp; 
}

int getValue(int n) {
    uint32_t temp;
    uint32_t mask = (1 << 10) - 1;

    if(n >= ELEMENTS) return 0;
    temp = myArray[n / 3];
    temp >>= (n % 3)*10;
    return (temp & ~mask) + 1;
}

Вы можете сделать это с помощью битовых полей вместо этого, но код для получения/установки отдельных значений будет заканчиваться использованием ветвей (например, switch( n%3 )), которые на практике будут более медленными.

Удаление этих двух бит дополнений будет стоить немного сложнее и немного больше накладных расходов. Например:

%define ELEMENTS 100

uint32_t myArray[ (ELEMENTS*10 + 31) / 32 ];

int getValue(int n) {
    uint64_t temp;
    uint64_t mask = (1 << 10) - 1;

    if(n >= ELEMENTS) return 0;

    temp = myArray[n*10/32 + 1];
    temp = (temp << 32) | myArray[n*10/32];

    temp >>= (n*10 % 32);

    return (temp & ~mask) + 1;
}

Это невозможно сделать с битовыми полями. Это самый эффективный способ хранения массива значений от 1 до 1024.

Ответ 6

Если вы храните "массив логических значений" или устанавливаете флаги, это может быть полезно. Например, вы можете инициализировать или сравнивать до 64 значений за раз.

Эти макросы будут работать для unsigned char, short, int, long long... но значительно упрощается, если вы просто выбираете тип (чтобы вы могли использовать более безопасную статическую встроенную функцию)

#define getbit(x,n) x[n/(sizeof(*x)*8)]  &  (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) 
#define setbit(x,n) x[n/(sizeof(*x)*8)] |=  (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) 
#define flpbit(x,n) x[n/(sizeof(*x)*8)] ^=  (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) 
#define clrbit(x,n) x[n/(sizeof(*x)*8)] &= ~( (typeof(*x))1 << (n&((sizeof(*x)*8)-1)) ) 

чтобы инициализировать большой массив логических элементов, все, что вам нужно сделать, это: char cbits[]={0,0xF,0,0xFF};

или для всех нулей char cbits[4]={0};

или int int: int ibits[]={0xF0F0F0F0,~0};

//1111000011110000111100001111000011111111111111111111111111111111

Если вы будете получать доступ только к 1 типу массива, возможно, лучше сделать макросы правильными функциями, например:

static inline unsigned char getbit(unsigned char *x, unsigned n){ 
  return x[n>>3]  &  1 << (n&7); 
}
//etc... similar for other types and functions from macros above

Вы также можете сравнивать несколько флагов одновременно с помощью '|' с флагами вместе и с помощью '&' ed mask; однако, это немного усложняется, если вы превысите собственные типы

Для вашего конкретного экземпляра вы можете инициализировать все нули с помощью:

unsigned char flags[128]={0};

или все 1:

uint64_t flags[128] = {~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0,~0};

Вы даже можете использовать перечисления для обозначения своих флагов

enum{
  WHITE, //0
  RED, //1
  BLUE, //2
  GREEN, //3
  ...
  BLACK //1023
}

if (getbit(flags,WHITE) && getbit(flags,RED) && getbit(flags,BLUE))
  printf("red, white and blue\n");