Bitwise packing/unpacking - 任意值的广义解

Question

我正在尝试使 this answer 适应任意数值。

假设我们有 3 个（无符号）数字：

v1、v2、v3

并且我们知道它们各自可能具有的最大值：

max1, max2, max3.

max1 * max2 * max3 < 2^32,

所以结果（打包值）在 32 位以内。

如何在没有“魔法”硬编码的情况下pack/unpack它们？

Answer 1

让数字按照参考答案中的相同顺序打包，从右到左从 v1:

开始

v3 <- v2 <- v1

我们已经从参考答案中找到了解决方案，但它仅适用于特定情况（源数据）：

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

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

上面的代码使用了以下魔术常量：

7 (size1) - 分配第一个数字的比特大小 (v1).
1 (size2) - ...（类似地）第二个数字 (v2)。请注意，此常量在上面隐式使用：8 = 7 + 1.
0x7F (sample1) - 用于按位比较以解压第一个数字 (v1) 的示例值。
1 (sample2) - ...（类似地）对于第二个数字 (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);

Answer 2

这里有一个稍微不同的方法。

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;

这里没有什么新鲜事。 Second shift 移动第一个和第二个值。

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

Bitwise packing/unpacking - 任意值的广义解

Bitwise packing/unpacking - generalized solution for arbitrary values

javascript

java

bitwise-operators

bit-packing