Побитовая упаковка/распаковка - обобщенное решение для произвольных значений

Я пытаюсь адаптировать этот ответ к произвольным числовым значениям.

Допустим, у нас есть 3 (беззнаковых) числа:

v1, v2, v3

и мы знаем соответствующие максимальные значения, которые они могут иметь:

max1, max2, max3.

max1 * max2 * max3 < 2^32,

поэтому результат (упакованное значение) должен быть в пределах 32 бит.

Как их запаковать/распаковать без магического хардкодинга?


java javascript bit-packing bitwise-operators
person hindmost    schedule 13.01.2021    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Вот немного другой способ сделать это.

int max1 = 1000;
int max2 = 500;
int max3 = 500;

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

int size1 = 32-Integer.numberOfLeadingZeros(max1);
int size2 = 32-Integer.numberOfLeadingZeros(max2);
int size3 = 32-Integer.numberOfLeadingZeros(max3);

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

int mask1 = ~(-1<<size1);
int mask2 = ~(-1<<size2);
int mask3 = ~(-1<<size3);

int v1 = 934;
int v2 = 293;
int v3 = 349;

Здесь нет ничего нового. Второй сдвиг сдвигает как первое, так и второе значения.

int packed = (((v3<<size2)|v2)<<size1)|v1;

Теперь переверни это

v1 = packed&mask1;
// this saves the shifted packed version for the next step
v2 = (packed = packed>>>size1)&mask2;
v3 = (packed>>>size2)&mask3;
        
System.out.println(v1);
System.out.println(v2);
System.out.println(v3);

Отпечатки

934
293
349
person WJS    schedule 13.01.2021

arrow_upward
1
arrow_downward

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

v3 <- v2 <- v1

У нас уже есть решение из указанного ответа, но оно работает только для конкретного случая (исходные данные):

// packing:
packed = (v3 << 8) | (v2 << 7) | v1;

// unpacking:
v1 = packed & 0x7F;
v2 = (packed >> 7) & 1;
v3 = (packed >> 8);

В приведенном выше коде используются следующие магические константы:

  • 7 (size1) - размер в битах для размещения 1-го числа (v1).

  • 1 (size2) - ...(аналогично) для 2-го числа (v2). Обратите внимание, что эта константа используется выше неявно: 8 = 7 + 1.

  • 0x7F (sample1) - выборочное значение, которое будет использоваться при побитовом сравнении для распаковки 1-го числа (v1).

  • 1 (sample2) - ...(аналогично) для 2-го числа (v2).

Для получения общего решения достаточно обобщить приведенные выше константы. Назовем их size1, size2, sample1 и sample2 соответственно. Ниже приведены их общие определения:

size1 = Math.floor(Math.log(max1) / Math.log(2)) + 1;
size2 = Math.floor(Math.log(max2) / Math.log(2)) + 1;
sample1 = Math.pow(2, size1 + 1) - 1;
sample2 = Math.pow(2, size2 + 1) - 1;

Таким образом, с этими константами общее решение должно выглядеть так:

// packing:
packed = v3 << (size1 + size2) | v2 << size1 | v1;

// unpacking:
v1 = packed & sample1;
v2 = (packed >> size1) & sample2;
v3 = packed >> (size1 + size2);
person hindmost    schedule 13.01.2021