CODEWITHSUNDEEP
javascriptjavabitwise-operatorsbit-packing
hindmost
hindmost

Reputation: 7205

Bitwise packing/unpacking - generalized solution for arbitrary values

I'm trying to adapt this answer to arbitrary numeric values.

Let's say we have 3 (unsigned) numbers:

v1, v2, v3

and we know the respective max values they may have:

max1, max2, max3.

max1 * max2 * max3 < 2^32,

so the result (packed value) is to be within 32 bits.

How to pack/unpack them without "magic" hardcoding?

Upvotes: 1

Views: 604

Answers (2)

hindmost
hindmost

Reputation: 7205

Let the numbers be packed in the same order like in the referenced answer, from right to left starting with v1:

v3 <- v2 <- v1

We already have a solution from the referenced answer, but it only works for specific case (source data):

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

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

The code above uses the following magic constants:

  • 7 (size1) - size in bits to allocate the 1st number (v1).

  • 1 (size2) - ...(similarly) for the 2st number (v2). Note that this constant is used above implicitly: 8 = 7 + 1.

  • 0x7F (sample1) - sample value to be used in bitwise comparison to unpack the 1st number (v1).

  • 1 (sample2) - ...(similarly) for the 2st number (v2).

In order to get a general solution it's enough to generalize the above constants. Let's name them size1, size2, sample1 and sample2 respectively. Below are their general definitions:

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;

So with these constants the general solution should look like this:

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

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

Upvotes: 1

WJS
WJS

Reputation: 40057

Here is a slightly different way to do it.

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

shift values determined based on most significant set bit of maximums.

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

mask values determined by complementing -1 shifted size bits.

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

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

Nothing really new here. Second shift shifts both first and second values.

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

Now reverse it

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);

Prints

934
293
349

Upvotes: 1

Related Questions