非2的幂次整数集合的高效打包存储与加载方法咨询

Great question! This is a perfect use case for integer packing—a technique that squeezes multiple variables into a single integer to cut down on wasted memory, exactly like you've described with saving that 1 bit. Let's break down the optimal packing and unpacking steps clearly:

Packing (Storing the Values) #

First, we need to convert each variable to a 0-based index (since your ranges start at 1, not 0—this is critical to avoid missing states):

• For foo (1-5), subtract 1 to get foo_0 (0-4, 5 total states)
• For bar (1-10), subtract 1 to get bar_0 (0-9, 10 total states)
• For baz (1-200), subtract 1 to get baz_0 (0-199, 200 total states)

Next, combine these into a single integer using weighted sums. The weight for each variable is the product of the total states of all variables that come before it:

packed = foo_0 + bar_0 * 5 + baz_0 * 5 * 10

Why this works: #

• foo_0 occupies the "least significant" portion of the packed value (each value maps to 0-4)
• Each bar_0 value represents 5 unique foo states, so we multiply by 5 to shift it into the next "block" of bits
• Each baz_0 value represents 5*10=50 unique foo+bar combinations, so we multiply by 50 to shift it into the highest block

This gives us a single integer ranging from 0 to 9999 (exactly 10,000 states), which fits neatly into 14 bits (since 2^14 = 16384, which is larger than 9999).

Unpacking (Loading the Values) #

To get your original integers back from the packed value, reverse the process using modulo (%) and integer division (//):

1. Extract foo first by taking the remainder when divided by 5, then add 1 to revert to 1-based:

   foo_0 = packed % 5
   foo = foo_0 + 1
   

2. Remove the foo portion from the packed value using integer division by 5:

   remaining = packed // 5
   

3. Extract bar the same way, using modulo 10, then add 1:

   bar_0 = remaining % 10
   bar = bar_0 + 1
   

4. What's left is the baz_0 value—just divide by 10 and add 1 to get back to 1-based:

   baz_0 = remaining // 10
   baz = baz_0 + 1
   

Example Code (Python) #

Here's a concrete implementation to test the logic:

def pack(foo, bar, baz):
    # Convert to 0-based indices
    foo_0 = foo - 1
    bar_0 = bar - 1
    baz_0 = baz - 1
    # Calculate packed value
    return foo_0 + bar_0 * 5 + baz_0 * 50

def unpack(packed):
    # Extract foo
    foo_0 = packed % 5
    remaining = packed // 5
    # Extract bar
    bar_0 = remaining % 10
    # Extract baz
    baz_0 = remaining // 10
    # Revert to 1-based values
    return (foo_0 + 1, bar_0 + 1, baz_0 + 1)

# Test with max values
foo, bar, baz = 5, 10, 200
packed_val = pack(foo, bar, baz)
print(f"Packed value: {packed_val} (binary: {bin(packed_val)})")
# Output: Packed value: 9999 (binary: 0b10011100001111) → 14 bits

unpacked_vals = unpack(packed_val)
print(f"Unpacked values: {unpacked_vals}")
# Output: Unpacked values: (5, 10, 200)

Key Notes #

• In statically typed languages (like C), use a 16-bit unsigned integer type (e.g., uint16_t) to store the packed value—this ensures you don't waste extra memory and avoids overflow.
• Compilers will automatically optimize the constant multiplications/divisions (like *5 or //10) into fast bitwise operations, so you don't need to manually rewrite them unless you're working in an extremely constrained environment.
• If your variable ranges ever change, just update the state counts (the 5, 10, 200 values) in the packing/unpacking logic—this pattern scales to any number of variables with fixed ranges.

内容的提问来源于stack exchange，提问作者Rick de Water