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

Question

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

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

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

Answer 1

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

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

Answer 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

РЕДАКТИРОВАТЬ: другие ответы говорят о сохранении одного числа на четыребиты и используя бит-сдвиг.Это быстрее.

Answer 3

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

Четыре числа одинаковых размеров не подойдут - четыре бита за штуку четыре дают минимум 16 бит для их хранения.

Answer 4

Давайте скажем это в общем: предположим, что вы хотите смешать N чисел a1, a2, ... aN, a1 в диапазоне от 0..k1-1, a2 от 0..k2-1, ... и aN от 0 .. кН-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

Answer 5

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

Answer 6

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

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

Answer 7

Для упаковки четырех значений в одно число потребуется не менее 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

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

Answer 8

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

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

Answer 9

@ Mike Caron

Ваш последний пример (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;

Answer 10

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

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

value = a * 16 + b;

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

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

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

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

Если вы хотите сохранить четыре 2-битных целых числа (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

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