C взломать для хранения бит, который занимает 1 бит пространства?

Ответ 1

В С++ вы можете использовать std::vector<bool>, если размер является динамическим (это частный случай std::vector, см. this) в противном случае существует std::bitset (предпочтительнее std::bitset, если это возможно.) Также существует boost::dynamic_bitset, если вам нужно установить/изменить размер во время выполнения. Вы можете найти информацию об этом здесь, это довольно круто!

В C (и С++) вы можете вручную реализовать это с помощью побитовых операторов. Хорошее резюме общих операций здесь. Одна вещь, которую я хочу упомянуть, - это хорошая идея использовать целые числа без знака, когда вы выполняете бит-операции. << и >> являются undefined при смещении отрицательных целых чисел. Вам нужно будет выделить массивы некоторого целостного типа типа uint32_t. Если вы хотите сохранить бит N, это займет N/32 этих uint32_t s. Бит i хранится в i % 32 'th бит i / 32' th uint32_t. Возможно, вы захотите использовать интегральный тип разного размера в зависимости от вашей архитектуры и других ограничений. Примечание: предпочитайте использовать существующую реализацию (например, как описано в первом абзаце для С++, искать решения Google для C) по сравнению с вашим собственным (если вы специально этого не хотите, и в этом случае я предлагаю узнать больше о бинарные/бит-манипуляции из других источников, прежде чем решать это.) Такие вещи были сделаны до смерти, и есть "хорошие" решения.

Существует несколько трюков, которые, возможно, будут потреблять только один бит: например. массивы битовых полей (применимы также к C), но используется ли меньшее пространство для компилятора. См. эту ссылку.

Обратите внимание: что бы вы ни делали, вы почти наверняка никогда не сможете использовать точно N бит для хранения N бит информации - ваш компьютер, скорее всего, не сможет выделить менее 8 бит: if вам нужно 7 бит, вам придется потратить 1 бит, и если вам нужно 9, вам придется взять 16 бит и отбросить 7 из них. Даже если ваш компьютер (CPU + RAM и т.д.) Может "работать" на одном бите, если вы работаете в ОС с помощью malloc/new, для вашего распределителя не будет разумно отслеживать данные до такого небольшого точность из-за накладных расходов. Эта последняя квалификация была довольно глупой - вы не найдете используемую архитектуру, которая позволяет вам работать на менее чем 8 бит за один раз, когда я представляю себе:)

Ответ 2

Вы должны использовать std::bitset.

std::bitset функционирует как массив bool (фактически как std::array, поскольку он копирует по значению), но использует только 1 бит памяти для каждого элемента.

Другая опция vector<bool>, которую я не рекомендую, потому что:

• Он использует медленную указательную область и память кучи, чтобы разрешить изменение размера, которое вам не нужно.
• Этот тип часто замалчивается стандартами-пуристами, потому что он утверждает, что является стандартным контейнером, но не может придерживаться определения стандартного контейнера *.

* Например, стандартно-совместимая функция может ожидать, что &container.front() создаст указатель на первый элемент любого типа контейнера, который не с std::vector<bool>. Возможно, это ниппель для вашего случая использования, но все же стоит знать о нем.

Ответ 3

На самом деле! std::vector<bool> имеет специализацию для этого: http://en.cppreference.com/w/cpp/container/vector_bool

См. документ, он сохраняет его как можно более эффективно.

Изменить: как сказал кто-то еще, std::bitset также доступен: http://en.cppreference.com/w/cpp/utility/bitset

Ответ 4

Если вы хотите записать его на C, укажите массив из char длиной 67601 бит (67601/8 = 8451), а затем включите/выключите соответствующий бит для каждого значения.

Ответ 5

Другие дали правильную идею. Вот моя собственная реализация bitsarr, или 'array' бит. Беззнаковый char представляет собой один байт, поэтому он представляет собой массив беззнаковых символов, который хранит информацию в отдельных битах. Я добавил возможность хранения двоичных значений TWO или FOUR в дополнение к значениям бит ONE, поскольку они делят 8 (размер байта) и будут полезны, если вы хотите сохранить огромное количество целых чисел, которое будет находиться в диапазоне от 0 -3 или 0-15.

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

Кроме того, пользователь несет ответственность за то, чтобы не передать значение, чтобы установить слишком большое значение, иначе оно приведет к другим значениям. Он может быть изменен таким образом, что переполнение будет повторяться до 0, но это просто сделает его более запутанным, поэтому я решил доверять себе.

#include<stdio.h>
#include <stdlib.h>
#define BYTE 8

typedef enum {ONE=1, TWO=2, FOUR=4} numbits;

typedef struct bitsarr{
    unsigned char* buckets;
    numbits n;
} bitsarr;


bitsarr new_bitsarr(int size, numbits n)
{
    int b = sizeof(unsigned char)*BYTE;
    int numbuckets = (size*n + b - 1)/b;
    bitsarr ret;  
    ret.buckets = malloc(sizeof(ret.buckets)*numbuckets);
    ret.n = n;
    return ret;
}
void bitsarr_delete(bitsarr xp)
{
    free(xp.buckets);
}

void bitsarr_set(bitsarr *xp, int index, int value)
{
    int buckdex, innerdex;
    buckdex = index/(BYTE/xp->n);
    innerdex = index%(BYTE/xp->n);
    xp->buckets[buckdex] = (value << innerdex*xp->n) | ((~(((1 << xp->n) - 1) << innerdex*xp->n)) & xp->buckets[buckdex]);

    //longer version

    /*unsigned int width, width_in_place, zeros, old, newbits, new;
    width = (1 << xp->n) - 1; 
    width_in_place = width << innerdex*xp->n;
    zeros = ~width_in_place;
    old = xp->buckets[buckdex];
    old = old & zeros;
    newbits = value << innerdex*xp->n;
    new = newbits | old;
    xp->buckets[buckdex] = new; */

}

int bitsarr_get(bitsarr *xp, int index)
{
    int buckdex, innerdex;
    buckdex = index/(BYTE/xp->n);
    innerdex = index%(BYTE/xp->n);
    return ((((1 << xp->n) - 1) << innerdex*xp->n) & (xp->buckets[buckdex])) >> innerdex*xp->n;

    //longer version

    /*unsigned int width = (1 << xp->n) - 1; 
    unsigned int width_in_place = width << innerdex*xp->n;
    unsigned int val = xp->buckets[buckdex];
    unsigned int retshifted = width_in_place & val;
    unsigned int ret = retshifted >> innerdex*xp->n;
    return ret; */
}

int main()
{
    bitsarr x = new_bitsarr(100, FOUR);
    for(int i = 0; i<16; i++)
        bitsarr_set(&x, i, i);
    for(int i = 0; i<16; i++)
        printf("%d\n", bitsarr_get(&x, i));
    for(int i = 0; i<16; i++)
        bitsarr_set(&x, i, 15-i);
    for(int i = 0; i<16; i++)
        printf("%d\n", bitsarr_get(&x, i));
    bitsarr_delete(x);
}