c - 如何将 32 位数组元素压缩为所需的最少位元素？

Question

假设我有一个如下所示的输入数组

int input_arr[100] = {10,20,1255,1200,50,55,1,5,6,1000};

在这里存储数组的每个元素，即使数组元素的值非常小，即 1255 是数组中的最大元素并存储它，它也需要 32 位只需要 11 位，这意味着在 11 位 中我可以容纳数组的所有其他元素。

那么我的任务是将32位数组元素压缩为11位数组元素？预期的压缩数组看起来像

int output_arr[] = {00000001010 00000010100 .... 10011111111 ... }
                        |             |               |
                   11 bits(1)    11 bits(2)     11 bits( 1255)

为了完成上述任务，我所做的就是在这里

• 查找给定数组中的最大元素
• 找到存储最大元素所需的位(上一步)
• 找到存储位数所需的字节，例如存储11位，我需要等效的2字节 (在下面的代码 new_size 中包含这个)。 我需要你的帮助。这是我的经理告诉我的内存浪费，因为要存储 11 位，我的 new_size 是 2 字节 即 5 位 > 仍然是额外的或浪费的。我怎样才能避免这种情况。

这是我尝试过的

int my_pow(int input_num,int p) {
        int temp = 1;
        for(int iter = 0;iter < p; iter++) {
                temp = temp * input_num;
        }
        return temp;
}
int main() {
        #if 0
        int input_array[53069] = {1,2,2,3,4,1,2,4,6,1255,1,2,5,1233};
        #endif
        int input_array[] = {1,2,3,4,6,1255,1,2,5,1233};

        int max = input_array[0], ele = sizeof(input_array)/sizeof(input_array[0]);
        /* finding max elements in a array */
        for(int i = 0;i < ele; i++) {
                if(input_array[i] > max) {
                        max = input_array[i];
                }
        }
        /* finding no of bits required to store highest elements of array */
        int bit_required = 0;
        while(1) {
                if(max < my_pow(2,bit_required))
                        break;
                bit_required+=1;
        }
        /* when above loop fails bit_required is nothing 
           but no of bit required to store the highest element of array */

        /* finding size of new/compressed array */
        int new_size = 0;
        if(bit_required % 8 == 0) {
                new_size = bit_required/8;
        }
        else {
                new_size = (bit_required/8) + 1;
        }
        /* construct the new array again */
        typedef struct array_task {
                unsigned char new_array[new_size];/* in each cmp_arr, can store new_size char
                                                     now for each B[] I'm not using 32 bits , its new_size bits */
        }cmp_arr;/* creating new array of ele elements */
        cmp_arr cmpressed[ele];
        /* store elements of input_array[] into output_array[] */
        for(int row = 0 ; row < ele ;row++) {
                for(int col = bit_required - 1; col >= 0; col-- ) {
                        cmpressed[row].new_array[col] = ((input_array[row] >> col & 1) + 48) ;
                        printf("%d",(cmpressed[row].new_array[col]) - 48);
                }
                printf("\n");
        }
        #if 0
        printf("Size of A before %d\n",sizeof(input_array)); /* 40 bytes */
        printf("size of compressed array %d\n",sizeof(cmp_arr));/* same task, it perform in 2 bytes, 
                                                                each elements won't take 32 bits  */
        #endif
        return 0;
}

还有其他方法可以有效地完成相同的任务吗？欢迎所有建议？

Answer 1

要将值移动 11 位而不是 8、16 或 32 位，需要对位进行操作。您基本上必须模拟整数数组(例如 32 位)中的位数组。在这种情况下，如果一个值存储在位偏移量 X 处，它将(可能)存储在数组中索引 X/32 和 X/32+1 上的某个位置(如果它跨越 32 位边界)。每次当您必须在数组中设置一个值时，您都必须加载这两个值并将您的数字“放置”在那里。实现有点技术性，尝试以下代码:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MASK32 ((uint64_t)0xffffffff)

void setValue(uint32_t *a, int bits, int i, int n) {
    int bitoffset = i * bits;
    int index = bitoffset / 32;
    int shift = bitoffset % 32;
    uint64_t maskbits = (~(uint64_t)0) >> (64-bits);
    uint64_t val = ((uint64_t)a[index+1]<<32) + a[index];
    val = val & ~(maskbits << shift) | ((n & maskbits) << shift);
    a[index] = (val & MASK32);
    a[index+1] = (val >> 32) & MASK32;
}

int getValue(const uint32_t *a, int bits, int i) {
    int bitoffset = i * bits;
    int index = bitoffset / 32;
    int shift = bitoffset % 32;
    uint64_t maskbits = (~(uint64_t)0) >> (64-bits);
    int val = ((((uint64_t)a[index+1]<<32) + a[index]) >> shift) & maskbits;
    return(val);
}

int input_arr[100] = {10,20,1255,1200,50,55,1,5,6,1000};

int main() {
    int        i, j;
    uint32_t   a[100*11/32+2];

    for(i=0; i<100; i++) setValue(a,11,i,input_arr[i]);
    for(j=0; j<100; j++) printf("a[%d/11] == %d\n", j, getValue(a,11,j));
}