Сжатие двух или более чисел в один байт

Я думаю, что это действительно невозможно, но стоит спросить. Скажем, у меня есть два небольших числа (каждый диапазон от 0 до 11). Есть ли способ, чтобы я мог сжать их в один байт и вернуть их позже. Как насчет с четырьмя номерами одинаковых размеров.

Мне нужно что-то вроде: a1 + a2 = x. Я знаю только х и от этого получаю a1, a2
Для второй части: a1 + a2 + a3 + a4 = x. Я знаю только x и получаю a1, a2, a3, a4
Примечание. Я знаю, что вы не можете отказаться, просто проиллюстрировав мой вопрос.

x должен быть одним байтом. a1, a2, a3, a4 [0, 11].

Ответ 1

Это тривиально с бит-масками. Идея состоит в том, чтобы разделить байт на более мелкие единицы и посвятить их различным элементам.

Для двух чисел это может быть так: первые 4 бита - number1, rest - number2. Вы должны использовать number1 = (x & 0b11110000) >> 4, number2 = (x & 0b00001111) для извлечения значений и x = (number1 << 4) | number2 для их сжатия.

Ответ 2

Для двух чисел, конечно. Каждый из них имеет 12 возможных значений, поэтому пара имеет в общей сложности 12 ^ 2 = 144 возможных значения и меньше 256 возможных значений байта. Таким образом, вы можете сделать, например,

x = 12*a1 + a2
a1 = x / 12
a2 = x % 12

(Если у вас есть только подписанные байты, например, на Java, это немного сложнее)

Для четырех чисел от 0 до 11 есть 12 ^ 4 = 20736 значений, поэтому вы не можете поместить их в один байт, но вы можете сделать это с двумя.

x = 12^3*a1 + 12^2*a2 + 12*a3 + a4
a1 = x / 12^3
a2 = (x / 12^2) % 12
a3 = (x / 12) % 12
a4 = x % 12

EDIT: другие ответы говорят о сохранении одного номера на четыре бита и использовании бит-сдвига. Это быстрее.

Ответ 3

Пример 0-11 довольно прост - вы можете хранить каждое число в четырех битах, поэтому помещать их в один байт - это просто переключение одного из четырех бит влево и or объединение двух.

Четыре числа одинаковых размеров не будут соответствовать - четыре бита за четыре раза дают минимум 16 бит, чтобы удерживать их.

Ответ 4

Если числа 0-11 распределены неравномерно, вы можете сделать еще лучше, используя более короткие битовые последовательности для общих значений и более длинные для более редких значений. Это стоит, по крайней мере, одного бита для кодирования той длины, которую вы используете, поэтому существует целая ветвь CS, посвященная проверке, когда это стоит.

Ответ 5

Скажем, в общем случае: предположим, что вы хотите смешивать N чисел a1, a2,... aN, a1 от 0..k1-1, a2 от 0..k2-1,... и aN от 0.. kN-1.

Затем закодированное число:

encoded = a1 + k1*a2 + k1*k2*a3 + ... k1*k2*..*k(N-1)*aN

Затем декодирование более сложное, поэтапно:

rest = encoded
a1 = rest mod k1
rest = rest div k1

a2 = rest mod k2
rest = rest div k2

...

a(N-1) = rest mod k(N-1)
rest = rest div k(N-1)

aN = rest # rest is already < kN

Ответ 6

Таким образом, байт может содержать до 256 значений или FF в Hex. Таким образом, вы можете кодировать два числа от 0 до 16 в байте.

byte a1 = 0xf;
byte a2 = 0x9;
byte compress = a1 << 4 | (0x0F & a2);  // should yield 0xf9 in one byte.

4 Номера, которые вы можете сделать, если вы уменьшите его до 0-8.

Ответ 7

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

Если вы хотите сохранить два 4-битных целых числа (что дает вам 0-15 для каждого), вам просто нужно сделать это:

value = a * 16 + b;

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

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

a = floor(value / 16)
b = value MOD 15

MOD - модуль, это "остаток" деления.

Если вы хотите сохранить четыре двухбитовых целых числа (0-3), вы можете сделать это:

value = a * 64 + b * 16 + c * 4 + d

И, чтобы вернуть их:

a = floor(value / 64)
b = floor(value / 16) MOD 4
c = floor(value / 4) MOD 4
d = value MOD 4

Я оставляю последнее разделение как упражнение для читателя;)

Ответ 8

@Майк Карон

ваш последний пример (4 целых числа от 0 до 3) намного быстрее с битовым сдвигом. Нет необходимости в полу().

value = (a << 6) | (b << 4) | (c << 2) | d;

a = (value >> 6);
b = (value >> 4) % 4;
c = (value >> 2) % 4;
d = (value) % 4;

Ответ 9

Используйте бит-маскирование или бит-сдвиг. Чем быстрее, тем быстрее

Протестируйте BinaryTrees для некоторой забавы. (он будет позже передаваться в dev в отношении данных и всех видов dev voodom lol)

Ответ 10

Для упаковки четырех значений в одно число потребуется не менее 15 бит. Это не соответствует одному байту, но в два.

Что вам нужно сделать, это преобразование с базы 12 на базу 65536 и наоборот.

B = A1 + 12.(A2 + 12.(A3 + 12.A4))

A1 = B % 12
A2 = (B / 12) % 12
A3 = (B / 144) % 12
A4 = B / 1728

Так как это занимает 2 байта, преобразование базы с базы 12 в (упакованную) базу 16 на сегодняшний день является предварительным.

B1 = A1 + 256.A2
B2 = A3 + 256.A4

A1 = B1 % 256
A2 = B1 / 256
A3 = B2 % 256
A4 = B2 / 256

Модули и деления реализуются посредством масок и сдвигов.

Ответ 11

0-9 работает намного проще. Вы можете легко хранить десятичные десятичные числа порядка в 4 1/2 байта. Это более сжатое сжатие, чем log (256) ÷ log (10). Только с помощью творческого сопоставления. Помните, что не все сжатие связано с словарями, сокращениями или последовательностями.

Если вы говорите о случайных числах 0-9, вы можете иметь 4 цифры на 14 бит, а не 15.