如何将32位数组元素压缩至最小所需位数？（含实例）

Got it, let's work through how to compress your 32-bit integer array down to using only 11 bits per element—since that's all you need given the max value of 1255. Here's a practical, step-by-step solution:

We can't store standalone 11-bit values directly in memory (memory operates in byte/word chunks), so we'll pack multiple 11-bit "blocks" into standard 32-bit integers. A quick calculation: 32 bits ÷ 11 bits per element = 2 full elements per 32-bit int, with 10 leftover bits (not enough for a third element). So each entry in the output array will hold up to 2 compressed values, and we'll round up the output array length for any odd-numbered elements left over.

• First, extract the lowest 11 bits from each 32-bit input element (since 1255 is exactly the max value for 11 bits, this captures all valid data).
• Pack these 11-bit values into the output array:
  • Even-indexed input elements go into the lower 11 bits of an output int.
  • Odd-indexed input elements get shifted left by 11 bits and stored in the upper 11 bits of the same output int.
• Calculate the output array length as (input_length + 1) / 2 (integer math to avoid floating-point ceil() calls).

#include <stdio.h>

#define INPUT_SIZE 10
#define BITS_PER_ELEMENT 11
#define MASK_11BIT 0x7FF // Binary: 11 consecutive 1s

int main() {
    int input_arr[INPUT_SIZE] = {10,20,1255,1200,50,55,1,5,6,1000};
    // Calculate output array size (ceil(INPUT_SIZE / 2))
    int output_size = (INPUT_SIZE + 1) / 2;
    int output_arr[output_size] = {0};

    // Compress the input array
    for (int i = 0; i < INPUT_SIZE; i++) {
        // Extract only the necessary 11 bits
        int compressed_val = input_arr[i] & MASK_11BIT;
        
        // Determine where to place this value in the output array
        int output_idx = i / 2;
        int bit_shift = (i % 2) * BITS_PER_ELEMENT;
        
        // Pack the value into the correct position
        output_arr[output_idx] |= (compressed_val << bit_shift);
    }

    // Print input for reference
    printf("Original Input Array:\n");
    for (int i = 0; i < INPUT_SIZE; i++) {
        printf("%d ", input_arr[i]);
    }
    printf("\n\n");

    // Print compressed output in hex (to see packed bits clearly)
    printf("Compressed Output Array (Hex):\n");
    for (int i = 0; i < output_size; i++) {
        printf("0x%08X ", output_arr[i]);
    }
    printf("\n\n");

    // Unpack to verify we get the original data back
    printf("Unpacked Values (Verification):\n");
    for (int i = 0; i < INPUT_SIZE; i++) {
        int output_idx = i / 2;
        int bit_shift = (i % 2) * BITS_PER_ELEMENT;
        int unpacked_val = (output_arr[output_idx] >> bit_shift) & MASK_11BIT;
        printf("%d ", unpacked_val);
    }
    printf("\n");

    return 0;
}

• Extracting 11 bits: input_arr[i] & 0x7FF masks out all but the lowest 11 bits, since 0x7FF is 11 binary 1s. This works because your max value (1255) is exactly 0x4FF, which fits entirely in those 11 bits.
• Packing logic: For each input element, we calculate which output int it belongs to (output_idx = i/2) and how far to shift it (bit_shift). Even elements stay in the lower 11 bits, odd elements move up to the upper 11 bits.
• Verification: The unpacking step reverses the process, ensuring we can perfectly retrieve the original data—critical to confirm no information is lost.

• If your input ever includes negative numbers, you'll need to adjust for 11-bit two's complement storage, but since your max value is positive and fits in 11 bits, this isn't necessary here.
• If you need a string output like your example (00000001010 0000001010...), you can add a helper function to format each 11-bit value as a zero-padded binary string after unpacking (or during compression).

内容的提问来源于stack exchange，提问作者Achal