bit-operations – Packing a large number of numbers, a compressed array of bit numbers

Question:

There is this code that packs a number into a number (example in the comment), the problem is in the bit shift, even if the value is specifically in the string:

  //Упаковка в 16 бит\число
unsigned setnum(const unsigned &pack, const char &hiegth_bit_max_dec, const unsigned &num, const unsigned &wordnum)
{
    unsigned count_words = wordnum*hiegth_bit_max_dec;
    count_words %= int(floor(16 / hiegth_bit_max_dec)*hiegth_bit_max_dec);
    unsigned maskword = ((1 << hiegth_bit_max_dec) - 1) << count_words;//создаем маску числа на место слова
    cout << ((wordnum*hiegth_bit_max_dec) % count_words)<< '=' << endl <<bitset<32>(maskword) << endl;
    maskword ^= (1 << 16) - 1; //переворачиваем маску
    return ((pack & maskword) | (num << (wordnum*hiegth_bit_max_dec)));
};

//Распаковка из 16 бит\число
unsigned getnum(const unsigned &pack, const char &hiegth_bit_max_dec, const unsigned &wordnum)
{
    unsigned count_words = wordnum*hiegth_bit_max_dec;
    count_words %= int(floor(16 / hiegth_bit_max_dec)*hiegth_bit_max_dec);
    unsigned maskword = ((1 << hiegth_bit_max_dec) - 1) << (count_words);//создаем маску числа на место слова
    return ((pack & maskword) >> (wordnum*hiegth_bit_max_dec));//очищаем все по маске, кроме слова, сдвигаем и получаем число
};

I found an error and cited it according to the advice https://ru.stackoverflow.com/users/10105/vladd and the following code of the main functions turned out (the error was in the shift, but not in what I checked):

const size_t bits_in_byte = 8;
const size_t bits_in_variable = sizeof(unsigned)* bits_in_byte;
//Упаковка в bits_in_variable бит\число
void setnum(unsigned &pack, const char &hiegth_bit_max_dec, const unsigned &num, const unsigned &wordnum)
{
    unsigned count_words = wordnum*hiegth_bit_max_dec;
    count_words %= int(floor(bits_in_variable / hiegth_bit_max_dec)*hiegth_bit_max_dec);
    unsigned maskword = ((1 << hiegth_bit_max_dec) - 1) << count_words;//создаем маску числа на место слова
    maskword ^= (1 << bits_in_variable) - 1; //переворачиваем маску
    pack = ((pack & maskword) | (num << count_words));
};

//Распаковка из bits_in_variable бит\число
unsigned getnum(const unsigned &pack, const char &hiegth_bit_max_dec, const unsigned &wordnum)
{
    unsigned count_words = wordnum*hiegth_bit_max_dec;
    count_words %= int(floor(bits_in_variable / hiegth_bit_max_dec)*hiegth_bit_max_dec);
    unsigned maskword = ((1 << hiegth_bit_max_dec) - 1) << (count_words);//создаем маску числа на место слова
    return ((pack & maskword) >> (count_words));//очищаем все по маске, кроме слова, сдвигаем и получаем число
};

the main function demonstrating the work of the packer (enter the number of numbers that we will pack and the maximum number for packing)

int main()
{
    unsigned n, maxd;

    cout << "Enter count of Dec="; cin >> n; cout << endl;
    cout << "Enter Maximum Dec="; cin >> maxd; cout << endl;
    cout << "MAX Bit=" << (hibit(maxd)) << "\tof\tMAX Number=" << maxd << endl;

    int count_words_in_variable = bits_in_variable / hibit(maxd);

    unsigned *arrayn = new unsigned[n / (count_words_in_variable) + n % (count_words_in_variable)];
    cout << n / (count_words_in_variable) + n % (count_words_in_variable) << endl;
    for (int i = 0; i < (n / (count_words_in_variable) + n % (count_words_in_variable)); i++)
        arrayn[i] = 0;

    for (int i = 0; i < (n); i++)
        setnum(arrayn[int(floor(i / (count_words_in_variable)))], hibit(maxd), maxd, i);

    for (int i = 0; i < (n); i++)
    {
        cout << getnum((arrayn[int(floor(i / (count_words_in_variable)))]), hibit(maxd), i) << '=';
        cout << int(floor(i / (count_words_in_variable))) << " in ";
        cout << bitset <bits_in_variable>(arrayn[int(floor(i / (count_words_in_variable)))]) << endl;
    };

    delete []  arrayn;

    system("pause>>void");
    return 0;
};

and of course all of this is highlighted in a separate class:

class packetbit
{
private:
    size_t *_arrayns; //Array
    size_t _sizearray;//Size of Array
    size_t _word;       //count words in bits_in_variable bits
    char _size_word_in_bit;     //Size of Word
    size_t _count; //need to write all words

    //Размер числа в битах учитывая младшие
    friend int hibit(const unsigned &num);

    //Упаковка в bits_in_variable бит\число
    friend void setnum(unsigned &pack, const char &hiegth_bit_max_dec, const unsigned &num, const unsigned &wordnum);

    //Распаковка из bits_in_variable бит\число
    friend unsigned getnum(const unsigned &pack, const char &hiegth_bit_max_dec, const unsigned &wordnum);

public:
    packetbit(const unsigned &SizeArray, const unsigned MaxDec)
    {
        _sizearray = SizeArray;
        _size_word_in_bit = hibit(MaxDec);
        _word = floor(bits_in_variable / _size_word_in_bit);
        _count = (_sizearray / _word + _sizearray % _word);
        _arrayns = new size_t [_count];
        for (int I = 0; I < _count; I++) _arrayns[I] = 0;
    };

    ~packetbit()
    {
        delete [] _arrayns;
    };

    //записывает в bits_in_variable бит \ число
    void setn(const unsigned &num, const unsigned &wordnum)
    {
        setnum(_arrayns[int(floor(wordnum / _word))], _size_word_in_bit, num, wordnum);
    };
    //считывает из bits_in_variable бит \ число
    unsigned getn(const unsigned &wordnum)
    {
        return getnum(_arrayns[int(floor(wordnum / _word))], _size_word_in_bit, wordnum);
    };
};

Answer:

And now, it seems, I understand. I thought you wanted a packed array of bits , but you wanted a more complex thing.

Then things change a little. You need to know two things: how long is your "word" and how long is your one entry. (For example, word = 32 bits and write = 3 bits). Now: the entry can go over the word boundary. In principle, even a few words. Therefore, the code turns out something like this:

size_t bits_in_record;

// ======================
// входящие: size_t array_size_in_records, record_t maxval

typedef unsigned word_t;
typedef unsigned record_t;

const size_t bits_in_byte = 8;
const size_t bits_in_word = (sizeof(word_t) / sizeof(char)) * bits_in_byte;

bits_in_record = (size_t)ceil(log(maxval) / log(2));
const size_t array_size_in_bits = array_size_in_records * bits_in_record;
const size_t array_size_in_words =
                 (size_t)ceil((double)array_size_in_bits / bits_in_word);

_arrayns = new unsigned[required_words];

// ======================
// теперь операции
size_t start_bit_number_for_index(size_t n)
{
    return n * bits_in_record;
}

size_t start_word_number_for_index(size_t n)
{
    return start_bit_number_for_index(n) / bits_in_word;
}

size_t start_bit_number_in_word_for_index(size_t n)
{
    return start_bit_number_for_index(n) % bits_in_word;
}

public:
void setvalue(size_t index, word_t value)
{
    size_t word_index = start_word_number_for_index(index);
    size_t start_bit_number = start_bit_number_in_word_for_index(index);
    size_t remaining_bits = bits_in_record;

    while (remaining_bits > 0) // цикл по словам, которые содержат нашу запись
    {
        // мы не можем перенести за раз всё, мы упираемся в конец слова
        size_t end_bit_number = min(start_bit_number + remaining_bits, bits_in_word);
        // вот столько бит получится за эту итерацию:
        size_t number_of_bits_to_transfer = end_bit_number - start_bit_number;
        size_t mask = (((word_t)1) << number_of_bits_to_transfer) - 1;
        mask <<= start_bit_number;
        _arrayns[word_index] &= ~mask; // очистить старое значение
        _arrayns[word_index] |= (value << start_bit_number) & mask;
                                       // установить новое

        start_bit_number = 0; // после начального куска, начинаем от нулевого бита
        value >>= number_of_bits_to_transfer; // убираем переданные биты
        remaining_bits -= number_of_bits_to_transfer;
        word_index++;
    }
}

word_t getvalue(size_t index)
{
    record_t total_value = 0;

    size_t word_index = start_word_number_for_index(index);
    size_t start_bit_number = start_bit_number_in_word_for_index(index);
    size_t remaining_bits = bits_in_record;

    size_t target_bit = 0;

    while (remaining_bits > 0)
    {
        size_t end_bit_number = min(start_bit_number + remaining_bits, bits_in_word);
        size_t number_of_bits_to_transfer = end_bit_number - start_bit_number;
        size_t mask = (((word_t)1) << number_of_bits_to_transfer) - 1;
        mask <<= start_bit_number;

        record_t curr_value = (_arrayns[word_index] & mask) >> start_bit_number;

        total_value |= curr_value << target_bit;

        target_bit += number_of_bits_to_transfer;
        start_bit_number = 0; // после начального куска, начинаем от нулевого бита
        remaining_bits -= number_of_bits_to_transfer;
        word_index++;
    }

    return total_value;
}

Ask, I hope I named the variables clearly.

Scroll to Top