c – 整数数组的位打包

我有一个整数数组,假设它们是int64_t类型.现在,我知道只有每个整数的每个前n位都是有意义的(也就是说,我知道它们受到一些界限的限制).

以所有不必要的空间被去除的方式转换阵列的最有效的方法是什么(即,我在第一个整数为[0],第二个为[0] n位等等)？

我希望尽可能地是一般的,因为n会不时地有所不同,尽管我猜想可能会对具体的n喜欢2或sth的力量进行智能优化.

当然我知道我可以迭代价值超过价值,我只是想问你StackOverflowers如果你能想到一些更聪明的方式.

编辑：

这个问题不是压缩数组以尽可能少的空间.我只需要从每个整数“剪切”n个位,并给出数组,我知道我可以安全地切割的确切的n位.

解决方法

我同意keraba,你需要使用像霍夫曼编码或者Lempel-Ziv-Welch算法.位置打包的问题是您有两种选择：

>选择常数n,以便可以表示最大的整数.
>允许n从值到值不同.

第一个选项比较容易实现,但真正浪费了很多空间,除非所有的整数都相当小.

第二个选择的主要缺点是您必须在输出比特流中以某种方式传达更改.例如,每个值都必须有一个与之相关联的长度.这意味着您为每个输入值存储两个整数(尽管较小的整数).很有可能通过这种方法增加文件大小.

霍夫曼或LZW的优点在于,它们以这样的方式创建码本,即可以从输出比特流导出代码的长度,而不实际存储长度.这些技术使您可以非常接近香农限制.

我决定给你原来的想法(常数n,删除未使用的位和打包)一个尝试的乐趣,这里是我提出的天真的实现：

#include <sys/types.h>
#include <stdio.h>

int pack(int64_t* input,int nin,void* output,int n)
{
    int64_t inmask = 0;
    unsigned char* pout = (unsigned char*)output;
    int obit = 0;
    int nout = 0;
    *pout = 0;

    for(int i=0; i<nin; i++)
    {
        inmask = (int64_t)1 << (n-1);
        for(int k=0; k<n; k++)
        {
            if(obit>7)
            {
                obit = 0;
                pout++;
                *pout = 0;
            }
            *pout |= (((input[i] & inmask) >> (n-k-1)) << (7-obit));
            inmask >>= 1;
            obit++;
            nout++;
        }
    }
    return nout;
}

int unpack(void* input,int nbitsin,int64_t* output,int n)
{
    unsigned char* pin = (unsigned char*)input;
    int64_t* pout = output;
    int nbits = nbitsin;
    unsigned char inmask = 0x80;
    int inbit = 0;
    int nout = 0;
    while(nbits > 0)
    {
        *pout = 0;
        for(int i=0; i<n; i++)
        {
            if(inbit > 7)
            {
                pin++;
                inbit = 0;
            }
            *pout |= ((int64_t)((*pin & (inmask >> inbit)) >> (7-inbit))) << (n-i-1);
            inbit++;
        }
        pout++;
        nbits -= n;
        nout++;
    }
    return nout;
}

int main()
{
    int64_t input[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int64_t output[21];
    unsigned char compressed[21*8];
    int n = 5;

    int nbits = pack(input,21,compressed,n);
    int nout = unpack(compressed,nbits,output,n);

    for(int i=0; i<=20; i++)
        printf("input: %lld   output: %lld\n",input[i],output[i]);
}

这是非常低效的,因为一次只有一步,但这是实现它的最简单的方式,而不处理endianess的问题.我还没有测试过这个值,只是测试中的值.此外,没有边界检查,并且假设输出缓冲区足够长.所以我所说的是,这段代码可能仅仅是教育目的才能让你开始.

c – 整数数组的位打包

解决方法

猜你在找的C&C++相关文章