假设我有一个如下所示的输入数组
int input_arr[100] = {10,20,1255,1200,50,55,1,5,6,1000};
在这里存储数组的每个元素，即使数组元素的值非常小，即1255是数组中的最大元素，也需要32位，并且存储我只需要11 bit这意味着11 bit我可以容纳数组的所有其他元素。
所以我的任务是将32-bit elements of array压缩成11-bit array elements？预期的压缩数组如下所示
int output_arr[] = {00000001010 00000010100 .... 10011111111 ... }
| | |
11 bits(1) 11 bits(2) 11 bits( 1255)
为了完成上述任务，我所做的就在这里
- 在给定数组中查找
maximum元素 - 查找要存储
maximum elementsbits required(上一步) - 查找存储
no of bits所需的bytes例如存储11位，我需要等效的2 bytes(在下面的代码中new_size包含这个)。这是我需要你的帮助。这是我的经理所说的内存浪费，因为要存储11位，我的new_size2 bytes即5 bits仍然是额外的或浪费的。我怎样才能避免这种情况。
这是我尝试过的
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 %dn",sizeof(input_array)); /* 40 bytes */
printf("size of compressed array %dn",sizeof(cmp_arr));/* same task, it perform in 2 bytes,
each elements won't take 32 bits */
#endif
return 0;
}
有没有其他方法可以有效地完成相同的任务？欢迎所有建议？
要将值移位 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] == %dn", j, getValue(a,11,j));
}
我觉得"有趣"的另一种方法是分配一个字符数组，并对适合最大值的类型进行强制转换。像这样：
NumBytesMaxValue = ...;
void* pointers = malloc(NumBytesMaxValue * NumValues);
if (NumBytesMaxValue == 1)
cast_pointer_to_char_and_fill_it();
else if (NumBytesMaxValue == 2)
cast_pointer_to_short_and_fill_it();
...
数据压缩是一个广泛的主题，一个活跃的研究领域......压缩数据可以通过许多不同的方式完成，以至于偏离主题。
但是，查找阵列的最小类型可以通过实用程序或初步阶段来完成：
#include <limits.h>
#include <stdio.h>
int main() {
int input_array[] = { 1, 2, 2, 3, 4, 1, 2, 4, 6, 1255, 1, 2, 5, 1233 };
size_t i, count = sizeof(input_array) / sizeof(input_array[0]);
int min, max;
int nc = 0;
min = max = input_array[0];
for (i = 1; i < count; i++) {
if (min > input_array[i]) min = intput_array[i];
if (max < input_array[i]) max = intput_array[i];
}
printf("min value is %d, max value is %dn", min, max);
if (min >= SCHAR_MIN && max <= SCHAR_MAX)
nc += printf("type signed char is appropriaten");
if (min >= 0 && max <= UCHAR_MAX)
nc += printf("type unsigned char is appropriaten");
if (min >= SHRT_MIN && max <= SHRT_MAX)
nc += printf("type short is appropriaten");
if (min >= 0 && max <= USHRT_MAX)
nc += printf("type unsigned short is appropriaten");
if (nc == 0)
printf("no type smaller than int is appropriaten");
return 0;
}
您可以通过以下步骤对一组在编译时具有未知值的数字使用相同的方法：
- 从分配的小型数组(如
signed char)开始。 - 读取下一个值：如果它适合当前类型，请将其添加到数组中并继续。
- 如果没有，请分配一个较大类型的数组，例如
short，将到目前为止解析的值复制到其中，释放前一个数组，存储新值并继续。 - 如果新值不适合
short，请使用较大的类型，如int。 - 您可以为更大的类型(如
long和long long)编写代码，但您需要为每种类型编写特定的代码。 - 在读取阶段结束时，您将拥有一个处理数据集中所有值的最小类型的数组。使用特定类型的代码处理此数组。 这意味着您必须复制每种类型的处理代码，这可能很棘手。