Как получить доступ к диапазону бит в битах? - PullRequest
Новая
       39

Как получить доступ к диапазону бит в битах?

0 голосов
/ 25 января 2019

У меня есть набор битов, который очень большой, скажем, 10 миллиардов бит.

Что я хотел бы сделать, это записать это в файл. Однако использование .to_string() фактически останавливает мой компьютер.

Что я хотел бы сделать, так это перебирать биты и брать по 64 бита за раз, превращать его в uint64 и затем записывать его в файл.

Однако я не знаю, как получить доступ к различным диапазонам набора битов. Как бы я это сделал? Я новичок в c ++ и не знаю, как получить доступ к лежащему в основе bitset :: reference, поэтому приведите пример ответа.

Я пытался использовать указатель, но не получил то, что ожидал. Вот пример того, что я пытаюсь сделать до сих пор. 

#include <iostream>
#include <bitset>
#include <cstring>
using namespace std;

int main()
{
    bitset<50> bit_array(302332342342342323);
    cout<<bit_array << "\n";
    bitset<50>* p;
    p = &bit_array;
    p++;
    int some_int;
    memcpy(&some_int, p , 2);
    cout << &bit_array << "\n";
    cout << &p << "\n";
    cout << some_int << "\n";

    return 0;
}

выход 

10000110011010100111011101011011010101011010110011
0x7ffe8aa2b090                                                                                                                          
0x7ffe8aa2b098
17736

Последнее число меняется при каждом запуске, что не соответствует ожиданиям.

Ответы [ 2 ]

0 голосов
/ 25 января 2019

Для доступа к диапазонам bitset, вы должны взглянуть на предоставленный интерфейс.Отсутствие что-то вроде bitset::data() указывает на то, что не следует пытаться получить прямой доступ к базовым данным.Выполнение этого, даже если это казалось работающим, хрупкое, хакерское и, вероятно, неопределенное поведение какого-то рода.

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

Вторая возможность - использовать побитовые операторы и to_ullong().Недостатком этого подхода является то, что он номинально использует вспомогательное пространство памяти, а именно два дополнительных набора битов того же размера, что и ваш оригинал.Я говорю «номинально», потому что компилятор может быть достаточно умен, чтобы оптимизировать их.Может быть.Возможно, нет.И вы имеете дело с размерами более гигабайта каждый.Реально, побитовый подход, вероятно, является подходящим вариантом, но я думаю, что этот пример интересен на теоретическом уровне. 

#include <iostream>
#include <iomanip>
#include <bitset>
#include <cstdint>
using namespace std;

constexpr size_t FULL_SIZE = 120; // Some large number
constexpr size_t CHUNK_SIZE = 64; // Currently the mask assumes 64. Otherwise, this code just
                                  // assumes CHUNK_SIZE is nonzero and at most the number of
                                  // bits in long long (which is at least 64).

int main()
{
    // Generate some large bitset. This is just test data, so don't read too much into this.
    bitset<FULL_SIZE> bit_array(302332342342342323);
    bit_array |= bit_array << (FULL_SIZE/2);
    cout << "Source: " << bit_array << "\n";

    // The mask avoids overflow in to_ullong().
    // The mask should be have exactly its CHUNK_SIZE low-order bits set.
    // As long as we're dealing with 64-bit chunks, there's a handy constant to handle this.
    constexpr bitset<FULL_SIZE> mask64(UINT64_MAX);
    cout << "Mask:   " << mask64 << "\n";

    // Extract chunks.
    const size_t num_chunks = (FULL_SIZE + CHUNK_SIZE - 1)/CHUNK_SIZE; // Round up.
    for ( size_t i = 0; i < num_chunks; ++i ) {
        // Extract the next CHUNK_SIZE bits, then convert to an integer.
        const bitset<FULL_SIZE> chunk_set{(bit_array >> (CHUNK_SIZE * i)) & mask64};
        unsigned long long chunk_val = chunk_set.to_ullong();
        // NOTE: as long as CHUNK_SIZE <= 64, chunk_val can be converted safely to the desired uint64_t.
        cout << "Chunk " << dec << i << ": 0x" << hex << setfill('0') << setw(16) << chunk_val << "\n";
    }

    return 0;
}

Вывод: 

Source: 010000110010000110011010100111011101011011010101011010110011010000110010000110011010100111011101011011010101011010110011
Mask:   000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
Chunk 0: 0x343219a9dd6d56b3
Chunk 1: 0x0043219a9dd6d56b
0 голосов
/ 25 января 2019

В программе есть пара ошибок.Максимальное значение, которое может хранить bitset<50>, равно 1125899906842623, и это намного меньше того значения, которое bit_array было инициализировано в программе.

some_int должно быть определено как unsigned long и проверьте,unsigned long имеет 64 бита на вашей платформе.

После этого протестируйте каждый бит bit_array в цикле, а затем выполните соответствующие побитовые операции (ИЛИ и сдвиг) и сохраните результат в some_int.

std::size_t start_bit = 0;
std::size_t end_bit = 64;
for (std::size_t i = start_bit; i < end_bit; i++) {
    if (bit_array[i])
       some_int |= mask;
    mask <<= 1;
}

Вы можете соответствующим образом изменить значения start_bit и end_bit при навигации по большому набору битов.

См. DEMO .

...