Сжать два или более чисел в один байт
Я думаю, что это на самом деле невозможно, но все равно стоит спросить. Скажем, у меня есть два маленьких числа (каждое в диапазоне от 0 до 11). Есть ли способ , с помощью которого я могу сжать их в один байт и получить обратно позже. Как насчет четырех номеров одинаковых размеров.
Мне нужно что-то вроде: a1 + a2 = x. Я знаю только x и из этого получаю a1, a2
Для второй части: a1 + a2 + a3 + a4 = x. Я знаю только x и из этого получаю a1, a2, a3, a4
Примечание: я знаю, что вы не можете отменить сложение, просто проиллюстрировав свой вопрос.
x должен быть одним байтом. a1, a2, a3, a4 диапазон [0, 11].
6 ответов
С битовыми масками все тривиально. Идея состоит в том, чтобы разделить байт на более мелкие части и выделить их разным элементам.
Для двух чисел это может быть так: первые 4 бита - это число1, остальные - число2. Вы должны использовать number1 = (x & 0b11110000) >> 4 , number2 = (x & 0b00001111) для получения значений и x = (number1 << 4) | number2 , чтобы сжать их.
Конечно, для двух чисел. У каждого из них 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
РЕДАКТИРОВАТЬ: в других ответах говорится о хранении одного числа на четыре бита и использовании битового сдвига. Так быстрее.
Пример 0-11 довольно прост - вы можете хранить каждое число в четырех битах, поэтому для помещения их в один байт достаточно сдвинуть на 4 бита влево, и или вместе.
Четыре числа одинакового размера не подходят - четыре бита умноженные на четыре, дают как минимум 16 бит для их хранения.
Если числа 0-11 неравномерно распределены, вы можете добиться еще большего, используя более короткие битовые последовательности для общих значений и более длинные для более редких значений. Код той длины, которую вы используете, стоит не менее одного бита, поэтому существует целая ветка CS, посвященная доказательству того, когда это стоит делать.
Таким образом, байт может содержать до 256 значений или FF в шестнадцатеричном формате. Таким образом, вы можете закодировать два числа от 0 до 16 в байте.
byte a1 = 0xf;
byte a2 = 0x9;
byte compress = a1 << 4 | (0x0F & a2); // should yield 0xf9 in one byte.
4 числа, которые вы можете сделать, если уменьшите его до диапазона 0-8.
Поскольку один байт состоит из 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
Я оставляю последнее деление в качестве упражнения для читателя ;)