Как эффективно преобразовать 8 17-битных целых в 17 8-битных

Question

Хорошо, у меня есть следующая проблема: у меня есть набор из 8 (без знака) чисел, все из которых являются 17-битными (иначе ни один из них не больше, чем 131071).Поскольку работа с 17-битными номерами раздражает (держать их в 32-битном int - пустая трата места), я хотел бы превратить их в 17-битные числа, например, так:

Если у меня есть эти8 17-разрядных целых чисел:

[25409, 23885, 24721, 23159, 25409, 23885, 24721, 23159]

Я бы превратил их в базовое представление 2L

["00110001101000001", "00101110101001101", "00110000010010001", "00101101001110111", "00110001101000001", "00101110101001101", "00110000010010001", "00101101001110111"]

Затем соединил бы это в одну большую строку:

"0011000110100000100101110101001101001100000100100010010110100111011100110001101000001001011101010011010011000001001000100101101001110111"

Затем разделите его на 17 строк, каждая из которых содержит 8 символов:

["00110001", "10100000", "10010111", "01010011", "01001100", "00010010", "00100101", "10100111", "01110011", "00011010", "00001001", "01110101", "00110100", "11000001", "00100010", "01011010", "01110111"]

И, наконец, преобразуйте двоичные представления обратно в целые числа

[49, 160, 151, 83, 76, 18, 37, 167, 115, 26, 9, 117, 52, 193, 34, 90, 119]

Этот метод работает, но он не очень эффективенЯ ищу что-то более эффективное, чем это, предпочтительно кодируется в C ++, так как это язык, с которым я работаю.Я просто не могу придумать, как сделать это более эффективным, и с 17-разрядными числами работать не совсем просто (с 16-разрядными числами было бы гораздо приятнее работать).

Заранее спасибо, xfbs

Answer 1

Сохраните младшие 16 битов каждого числа как есть (то есть в двух байтах).Это оставляет самый значимый бит каждого числа.Поскольку существует восемь таких чисел, просто объедините восемь битов в один дополнительный байт.

Для этого потребуется точно такой же объем памяти, что и для вашего метода, но потребуется гораздо меньше операций с битами.

PS Независимо от способа хранения, вы должны использовать операторы битовых манипуляций (<<, >>, &, | и т. Д.);не должно быть никаких промежуточных строковых представлений.

Answer 2

Посмотрите на std::bitset<N>.Может быть, вы можете вставить их в это?

Answer 3

Эффективно? Тогда не используйте строковые преобразования, битовые поля и т. Д. Управляйте сдвигами, чтобы достичь этого. (Обратите внимание, что массивы должны быть unsigned, чтобы у нас не возникало проблем при переключении).

uint32 A[8]; //Your input, unsigned int
ubyte B[17]; //Output, unsigned byte
B[0] = (ubyte)A[0];
B[1] = (ubyte)(A[0] >> 8);
B[2] = (ubyte)A[1];
B[3] = (ubyte)(A[1] >> 8);
.
:

И, наконец, мы делаем то, что сказал ajx. Мы берем самую значимую цифру каждого числа (сдвигая их на 16 бит вправо, оставляя 17-ю цифру), и заполняем биты нашего вывода, сдвигая каждую из наиболее значимых цифр от 0 до 7 влево:

B[16] = (A[0] >> 16)  | ((A[1] >> 16) << 1) | ((A[2] >> 16) << 2) | ((A[3] >> 16) << 3) | ... | ((A[7] >> 16) << 7);

Ну, "эффективным" было это. Существуют и другие более простые методы.

Answer 4

Хотя вы говорите, что это 17-разрядные числа, они должны храниться в массиве 32-разрядных целых чисел, где используются только менее значимые 17-разрядные числа.Вы можете извлечь из первых непосредственно два байта (dst[0] = src[0] >> 9 - первый, dst[1] = (src[0] >> 1) & 0xff - второй);затем вы «толкаете» первый бит как 18-й бит второго, так что

  dst[2] = (src[0] & 1) << 7 | src[1] >> 10;
  dst[3] = (src[1] >> 2) & 0xff;

если вы его обобщите, вы увидите, что эта «формула» может применяться

   dst[2*i] = src[i] >> (9+i) | (src[i-1] & BITS(i)) << (8-i);
   dst[2*i + 1] = (src[i] >> (i+1)) & 0xff;

и для последнего: dst[16] = src[7] & 0xff;.

Весь код может выглядеть следующим образом:

  dst[0] = src[0] >> 9;
  dst[1] = (src[0] >> 1) & 0xff;

  for(i = 1; i < 8; i++)
  {
    dst[2*i] = src[i] >> (9+i) | (src[i-1] & BITS(i)) << (8-i);
    dst[2*i + 1] = (src[i] >> (i+1)) & 0xff;
  }
  dst[16] = src[7] & 0xff;

Вероятно, при лучшем анализе циклов можно провести оптимизацию, чтобы нам не понадобилисьособое отношение к случаям на границах.Макрос BITS создает маску из N битов, установленных в 1 (младшие биты).Нечто подобное (проверяется на лучший способ, если таковой имеется)

#define BITS(I) (~((~0)<<(I)))

ADD

Здесь я предположил, что src, например, int32_t и dst int8_tили как.

Answer 5

Я бы, наверное, пошел по этому пути.Я не хочу иметь дело со странными типами, когда я делаю свою обработку.Может быть, мне нужно хранить их в каком-то необычном формате из-за устаревших проблем.Значения, которые жестко запрограммированы, вероятно, должны основываться на значении 17, просто не беспокойтесь.

struct int_block {
    static const uint32 w = 17;
    static const uint32 m = 131071;
    int_block() : data(151, 0) {} // w * 8 + (sizeof(uint32) - w)
    uint32 get(size_t i) const {
        uint32 retval = *reinterpret_cast<const uint32 *>( &data[i*w] );
        retval &= m;
        return retval;
    }
    void set(size_t i, uint32 val) {
        uint32 prev = *reinterpret_cast<const uint32 *>( &data[i*w] );
        prev &= ~m;
        val |= prev;
        *reinterpret_cast<uint32 *>( &data[i*w] ) = val;
    }
    std::vector<char> data;
};

TEST(int_block_test) {

    int_block ib;
    for (uint32 i = 0; i < 8; i++)
        ib.set(i, i+25);

    for (uint32 i = 0; i < 8; i++)
        CHECK_EQUAL(i+25, ib.get(i));
}

Вы могли бы сломать это, задав неверные значения, но яоставьте это как упражнение для читателя.:))

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

Answer 6

Это в C, поэтому вы можете использовать vector.

#define srcLength 8
#define destLength 17
int src[srcLength] = { 25409, 23885, 24721, 23159, 25409, 23885, 24721, 23159 };
unsigned char dest[destLength] = { 0 };

int srcElement = 0;
int bits = 0;
int i = 0;
int j = 0;

do {
    while( bits >= srcLength ) {
        dest[i++] = srcElement >> (bits - srcLength);
        srcElement = srcElement & ((1 << bits) - 1);
        bits -= srcLength;
    }

    if( j < srcLength ) {
        srcElement <<= destLength;
        bits += destLength;
        srcElement |= src[j++];
    }
} while (bits > 0);

Отказ от ответственности: если у вас буквально есть семнадцать целых чисел (а не 100000 групп по 17),следует забыть об этих оптимизациях, если ваша программа не работает очень медленно.