作者码字不易，白天敲代码，晚上熬夜赶报告，要转载请注明出处哦，程序猿的辛酸泪
目录
位运算回顾
若 a = 250 // 二进制为1111 1010
b = ((a << 5) >> 5) // b = 2，即0000 0010
若 c = 15 // 即0000 1111
d = ((c << 3) | b) // d = 0111 1010
讲解：当我们将a左移5位，在右移5位的时候（逻辑右移，即高位补0），就相当于将a的高5位抹零了，所以b就获得了a的低3位，即010，等于2；当我们将c左移3位，再和b进行或运算的时候，就相当于将a的低3位衔接到了c变量的后面。
注意：这里有一个小bug，文末揭晓。
压缩过程
为了方便打印数据，我们自定义一个myWrite()函数，代码如下图
unsigned int num = 1;
void myWrite(ofstream &fout, unsigned long long &value)
{
fout.write(reinterpret_cast<char*>(&value), sizeof(value));
cout << "向输出文件中写入的第 " << num++ << " 个value的值是：" << value << endl;
}接下来我们需要定义一些数据，来演示是如何把灰度图像的像素进行压缩的，数据以及变量的详情如下
// 这是像素点的数量，数量为12个
unsigned int count = 12;
// 这是我们的像素数据，下标从1开始
unsigned char data[] = { 0, 10, 12, 15, 255, 1, 2, 1, 1, 2, 2, 1, 1};
// 这是经过dp算法后，计算出来的分段数量
unsigned int segNum = 3;
// 这是经过dp算法后，计算出来的(分段长度-1)，下标从1开始
// l[1] = 2，表示第一段有3个元素，l[2] = 0，表示第二段有1个元素，分段长度最长256
unsigned char l[] = { 0, 2, 0, 7 };
// 这是每一段各像素的最大bit位数
unsigned char b[] = { 0, 4, 8, 2 };
// 压缩结束标志
bool isEnd = false;
unsigned long long value = 0; // 可写64bit位，当位操作满8字节时向文件中写入value
unsigned char index = 0; // 记录已经被操作了的bit数目
unsigned int dataNum = 1; // data数组的下标接下来开始我们的压缩第一步，写入长度为8bit的第一段的段长，代码如下
// 存段长，即该段元素的数量，最多256个，占8bit
if (index + 8 < 64)
{
value <<= 8;
value |= l[i];
index += 8;
}
else if (index + 8 == 64)
{
value <<= 8;
value |= l[i];
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
value = 0;
}
else // index + 8 > 64
{
unsigned char t = 64 - index; // 8位先存t位
value <<= t;
value |= (l[i] >> (8 - t)); // 存前t位
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
value = 0;
value |= (static_cast<unsigned char>(l[i] << t) >> t); // 8 - (8 - t)
index = 8 - t;
}讲解：这里分为了三种情况：
1，当我们写入8bit的段长信息后，未操作满64bit，这是我们的第一种情况，不调用的myWrite()函数；
2，当我们写入8bit的段长信息后，正好满64bit，将这个写满数据的value输出到文件中，然后变量重置；
3，当我们写入8bit的段长信息后，超过了64bit，就需要分两步存入。比如，我们此时的index = 62，我们第一步只能先存入2个bit位的数据，若l[i] = 1101 1111(二进制)，我们先将l[i]高位的11追加到value的末尾，然后将value写入文件中，然后第二步，再将l[i]低位的0001 1111存入value，这里就用到了我们前面回顾的位操作哦。最后index = 6，表示新的value被操作了6个bit位。
好，开始我们的压缩第二步，写入长度为3bit的第一段中各元素的最大长度，最长最8，即8 - 1 = 7（二进制111，3bit）
// 存段中各元素的统一长度，最长8位，占3bit
if (index + 3 < 64)
{
value <<= 3;
value |= (b[i] - 1);
index += 3;
}
else if (index + 3 == 64)
{
value <<= 3;
value |= (b[i] - 1);
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
value = 0;
}
else // index + 3 > 64
{
unsigned char t = 64 - index; // 3位先存t位
value <<= t;
value |= ((b[i] - 1) >> (3 - t)); // 存前t位
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
value = 0;
value |= (static_cast<unsigned char>((b[i] - 1) << (5 + t)) >> (5 + t)); // 8 - (3 - t)
index = 3 - t;
}讲解：这里就不详讲啦，原理和上面一模一样。不过这里有一个小地方要注意哦，在第三种情况中，（b[i] - 1）需要左移（5 + t）位，而不是 t 位，想想为什么(ฅ>ω<*ฅ)
嘿嘿，接下来就是第三步啦，我们前面已经写入了11bit的header，接下来就开始压入我们的像素数据了，代码如下，仔细看哦
// 存段中元素的像素数据，注意这里是l[i] + 1，才是我们的段长
for (unsigned char j = 0; j < l[i] + 1; j++)
{
if (index + b[i] < 64)
{
value <<= b[i];
value |= data[dataNum++];
index += b[i];
}
else if (index + b[i] == 64)
{
value <<= b[i];
value |= data[dataNum++];
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
value = 0;
}
else // index + b[i] > 64
{
unsigned char t = 64 - index; // b[i]位先存t位
value <<= t;
value |= (data[dataNum] >> (b[i] - t)); // 存前t位
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
value = 0;
value = (static_cast<unsigned char>(data[dataNum] << (8 - (b[i] - t))) >> (8 - (b[i] - t)));
dataNum++;
index = b[i] - t;
}
if (dataNum == count + 1) // 最后一个数据
{
value <<= (64 - index);
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
isEnd = true;
break;
}好啦，写了这么长的一段代码，一共有9个条件判断呢，是不是心里没底，不知道自己写的对不对，那我们就来打印一下存入的value的值，看看我们的算法有没有问题。我们前面自定义的myWrite()函数就能派上用场啦。请看输出信息
有人可能会疑惑，咦，不对呀，第一个value的值怎么感觉有点小呀，是不是长度没有达到64bit位呀。真的是我们的算法出错了吗？其实不是哒，因为如果高位有多个0的话，转化成10进制数，就体现不出来了呀。比如十进制2，它对应的unsigned char类型，其二进制可是0000 0010，前面的6个0也没有体现出来呀。那怎么检验呢。
这里安利一款好用的小工具，可以将一个超大的10进制数，转换成其对应的二进制数，一些在线的转换工具可达不到这个目的。
界面如下，下载链接文末给出(๑´ㅂ`๑)
这里是我们第一个value的值，数数看（一行3个字节），上面一共显示了58位，可见最前面是有6个0的。为了方便检验，我把二进制信息写到下面
0000 0010（前面补了6个0）
011 1010 1100 1111
0000 0000
111 1111 1111
0000 0111
001 01 10 01 01 10 1 （未完，被分成了两段）
检验一下看看，第一段元素有3（2+1）个，每个元素长度为4（3+1），分别是10， 12， 15
第二段元素有1（0+1）个，每个元素长度为8（7+1），分别是255
第三段元素有8（7+1）个，每个元素长度为2（1+1），分别是1，2，1，1，2，......
第二个value的值我就不检验了，感兴趣的小伙伴可以自己去检验看看哦，肯定是没问题的。
解压过程
哇，好了，费了不小的劲，终于把压缩过程讲解完啦，接下来的解压过程就是一个逆过程哦，也是很好理解的
首先，我们同样也需要先读取一些数据，还需要定义一些变量用来记录，代码如下图
// 读取我们的分段数量。
// 在实际情况中，我们可以在压缩的时候，将分段的数量最先写入文件中，在解压的时候，就可以直接读取出来了
unsigned int segNum = 3;
// 这是像素点的数量，数量为12个。
// 这里直接给出了，其实在实际情况中，我们可以通过bitMap的信息头的biWidth和biHeight的乘积来获取到
unsigned int count = 12;
// 存储我们解压出来的像素数据
unsigned char *data = new unsigned char[count + 1];
data[0] = 0;
// 解压结束标志
bool isEnd = false;
unsigned long long value = 0; // 含义同压缩
unsigned char index = 0; // 含义同压缩
unsigned int dataNum = 1; // 含义同压缩
unsigned char x = 0; // 段长
unsigned char y = 0; // 每段各像素的最大长度
// 初始化，先读入第一个value
fin.read(reinterpret_cast<char*>(&value), sizeof(value));接下来开始我们解压的第一步，读取长度为8bit的第一段的段长，代码如下
// 读取段元素的数量，最多256个，占8bit
if (index + 8 < 64)
{
x = ((value << index) >> 56);
index += 8;
}
else if (index + 8 == 64)
{
x = ((value << 56) >> 56);
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + 8 > 64
{
unsigned char t = 64 - index; // 先读t位
x = static_cast<unsigned char>((value << index) >> index);
index = 8 - t; // 再读8-t位
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
x <<= index;
x |= (value >> (64 - index));
}讲解：解压缩的过程就是一个逆过程啦，我们要从高位向低位读取数据，所以先左移，消除掉之前已读取到的数据，再右移的过程就必不可少了。
解压第二步，读取长度为3bit的段中元素的最大长度，代码如下
// 读取段中各元素的统一长度，最长8位，占3bit
if (index + 3 < 64)
{
y = ((value << index) >> 61) + 1;
index += 3;
}
else if (index + 3 == 64)
{
y = ((value << 61) >> 61) + 1;
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + 3 > 64
{
unsigned char t = 64 - index; // 先读t位
y = static_cast<unsigned char>((value << index) >> index);
index = 3 - t; // 再读3-t位
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
y <<= index;
y |= (value >> (64 - index));
y++;
}讲解：注意第三种情况的那个y++是因为最大长度等于读取到的数据 + 1，注意一下就好啦。
解压第三步，开始解压我们的像素数据啦，仔细看哦
// 读取段中元素的像素数据
for (unsigned char j = 0; j < x + 1; j++)
{
if (index + y < 64)
{
data[dataNum++] = static_cast<unsigned char>((value << index) >> (64 - y));
if (dataNum == count + 1) {
isEnd = true;
break;
}
index += y;
}
else if (index + y == 64)
{
data[dataNum++] = static_cast<unsigned char>((value << index) >> index);
if (dataNum == count + 1) {
isEnd = true;
break;
}
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + y > 64
{
unsigned char t = 64 - index; // 先读t位
data[dataNum] = static_cast<unsigned char>((value << index) >> index);
index = y - t; // 再读y-t位
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
data[dataNum] <<= index;
data[dataNum] |= (value >> (64 - index));
dataNum++;
if (dataNum == count + 1) {
isEnd = true;
break;
}
}讲解：已经没有什么可以讲解的了，原理都差不多呢(｡･ω･｡)ﾉ♡
最后的最后，让我们来接验一下我们解压的成果吧，只需要把data数组里的输出一下就可以了，请看下图
大功告成，啦啦啦 (*/ω＼*)
关于一个莫得感情的小bug
最后，来解答一下最开头所提到的小bug吧。细心的小伙伴们可能会发现，在压缩和解压的函数里，有些地方我们使用了强制类型转换（static_cast<unsigned char>()），有些地方确没有使用。一方面，我们在解压过程中，将64bit位的value强行赋值给我们的x，y，或data[dataNum]，编辑器会警告我们这样的转换可能会丢失精度，额为了消除这样的警告（强迫症啦这是），所以我们就使用一个强制类型转换啦。但是，另一方面，不知道小伙伴们有没有做过这样的尝试
unsigned char a = 250; // 11111010
cout << "a：" << int(a) << endl;
unsigned char b = ((a << 5) >> 5);
cout << "b：" << int(b) << endl;
unsigned char c = (static_cast<unsigned char>(a << 5) >> 5);
cout << "c：" << int(c) << endl;有人可能会疑惑，诶，b和c的值是一样的吧，肯定是2啊，先左移再右移嘛，但结果真的是这样吗，请看运行结果
我的天，为什么先左移再右移没有起作用呢，这里经过尝试后发现，对于unsigned char类型的变量，在同一条执行语句中，先左移再右移，编辑器会貌似会进行一个不必要的优化，即它发现，诶你既左移了5位，又右移了5位，不就相当于没移嘛，那我就不用给你执行这条语句了。同理，经测试后发现，如果对于unsigned char类型的变量，在同一条执行语句中，先左移5位，在右移4位，编辑器会优化成最终只用向左移1位。所以啊，如果我们希望通过先左移再右移来达到消除高位的效果，要么将左移和右移分两步进行，要么在左移结束后要加一个强制类型转换，告诉编辑器，我就要先左移，你必须得给我执行 o(一︿一+)o
博主又经过了多轮测试，发现，这个左移右移的优化功能，貌似只对unsigned char类型和unsigned short类型起作用，对于unsigned int 和unsigned long long类型，就算你把左移和右移放在同一条执行语句中，就算你没有加强制类型转换，它也不会给你进行优化了。
好吧，这也算是，课外的一个算有趣也不算有趣的小知识点吧 o(╯□╰)o
实用小工具的下载地址
最后的最后的最后，放出我们那个超好用的小工具的下载链接，说实话，这个小工具在我找bug的时候，帮了我不少的忙，虽然，这个灰度图像压缩的bug让我找得猿生绝望。
完整版代码
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
unsigned int num = 1;
void myWrite(ofstream &fout, unsigned long long &value)
{
fout.write(reinterpret_cast<char*>(&value), sizeof(value));
cout << "向输出文件中写入的第 " << num++ << " 个value的值是：" << value << endl;
}
bool Compress(string fileName)
{
// 关联我们要输出的文件
ofstream fout(&fileName[0], ios::binary);
if (!fout) return false;
///
/// 此处省略了我们写文件头的操作
///
// 这是像素点的数量，数量为12个
unsigned int count = 12;
// 这是我们的像素数据，下标从1开始
unsigned char data[] = { 0, 10, 12, 15, 255, 1, 2, 1, 1, 2, 2, 1, 1};
// 这是经过dp算法后，计算出来的分段数量
unsigned int segNum = 3;
// 这是经过dp算法后，计算出来的(分段长度-1)，下标从1开始
// l[1] = 2，表示第一段有3个元素，l[2] = 0，表示第二段有1个元素，分段长度最长256
unsigned char l[] = { 0, 2, 0, 7 };
// 这是每一段各像素的最大bit位数
unsigned char b[] = { 0, 4, 8, 2 };
// 压缩结束标志
bool isEnd = false;
// 开始压缩像素，并写入文件
unsigned long long value = 0; // 可写64bit位，当位操作满8字节时向文件中写入value
unsigned char index = 0; // 记录已经被操作了的bit数目
unsigned int dataNum = 1; // data数组的下标
for (unsigned int i = 1; i <= segNum && !isEnd; i++)
{
// 存段长，即该段元素的数量，最多256个，占8bit
if (index + 8 < 64)
{
value <<= 8;
value |= l[i];
index += 8;
}
else if (index + 8 == 64)
{
value <<= 8;
value |= l[i];
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
value = 0;
}
else // index + 8 > 64
{
unsigned char t = 64 - index; // 8位先存t位
value <<= t;
value |= (l[i] >> (8 - t)); // 存前t位
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
value = 0;
value |= (static_cast<unsigned char>(l[i] << t) >> t); // 8 - (8 - t)
index = 8 - t;
}
// 存段中各元素的统一长度，最长8位，占3bit
if (index + 3 < 64)
{
value <<= 3;
value |= (b[i] - 1);
index += 3;
}
else if (index + 3 == 64)
{
value <<= 3;
value |= (b[i] - 1);
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
value = 0;
}
else // index + 3 > 64
{
unsigned char t = 64 - index; // 3位先存t位
value <<= t;
value |= ((b[i] - 1) >> (3 - t)); // 存前t位
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
value = 0;
value |= (static_cast<unsigned char>((b[i] - 1) << (5 + t)) >> (5 + t)); // 8 - (3 - t)
index = 3 - t;
}
// 存段中元素的像素数据，注意这里是l[i] + 1，才是我们的段长
for (unsigned char j = 0; j < l[i] + 1; j++)
{
if (index + b[i] < 64)
{
value <<= b[i];
value |= data[dataNum++];
index += b[i];
}
else if (index + b[i] == 64)
{
value <<= b[i];
value |= data[dataNum++];
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
value = 0;
}
else // index + b[i] > 64
{
unsigned char t = 64 - index; // b[i]位先存t位
value <<= t;
value |= (data[dataNum] >> (b[i] - t)); // 存前t位
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
value = 0;
value = (static_cast<unsigned char>(data[dataNum] << (8 - (b[i] - t))) >> (8 - (b[i] - t)));
dataNum++;
index = b[i] - t;
}
if (dataNum == count + 1) // 最后一个数据
{
value <<= (64 - index);
myWrite(fout, value);
//fout.write(reinterpret_cast<char*>(&value), sizeof(value));
isEnd = true;
break;
}
}
}
fout.close();
return true;
}
bool UnCompress(string fileName)
{
// 打开指定文件
ifstream fin(&fileName[0], ios::binary);
if (!fin) return false;
///
/// 此处省略了我们读文件头的操作
///
// 读取我们的分段数量。
// 在实际情况中，我们可以在压缩的时候，将分段的数量最先写入文件中，在解压的时候，就可以直接读取出来了
unsigned int segNum = 3;
// 这是像素点的数量，数量为12个。
// 这里直接给出了，其实在实际情况中，我们可以通过bitMap的信息头的biWidth和biHeight的乘积来获取到
unsigned int count = 12;
// 存储我们解压出来的像素数据
unsigned char *data = new unsigned char[count + 1];
data[0] = 0;
// 解压结束标志
bool isEnd = false;
unsigned long long value = 0; // 含义同压缩
unsigned char index = 0; // 含义同压缩
unsigned int dataNum = 1; // 含义同压缩
unsigned char x = 0; // 段长
unsigned char y = 0; // 每段各像素的最大长度
// 初始化，先读入第一个value
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
for (unsigned int i = 1; i <= segNum && !isEnd; i++)
{
// 读取段元素的数量，最多256个，占8bit
if (index + 8 < 64)
{
x = ((value << index) >> 56);
index += 8;
}
else if (index + 8 == 64)
{
x = ((value << 56) >> 56);
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + 8 > 64
{
unsigned char t = 64 - index; // 先读t位
x = static_cast<unsigned char>((value << index) >> index);
index = 8 - t; // 再读8-t位
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
x <<= index;
x |= (value >> (64 - index));
}
// 读取段中各元素的统一长度，最长8位，占3bit
if (index + 3 < 64)
{
y = ((value << index) >> 61) + 1;
index += 3;
}
else if (index + 3 == 64)
{
y = ((value << 61) >> 61) + 1;
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + 3 > 64
{
unsigned char t = 64 - index; // 先读t位
y = static_cast<unsigned char>((value << index) >> index);
index = 3 - t; // 再读3-t位
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
y <<= index;
y |= (value >> (64 - index));
y++;
}
// 读取段中元素的像素数据
for (unsigned char j = 0; j < x + 1; j++)
{
if (index + y < 64)
{
data[dataNum++] = static_cast<unsigned char>((value << index) >> (64 - y));
if (dataNum == count + 1) {
isEnd = true;
break;
}
index += y;
}
else if (index + y == 64)
{
data[dataNum++] = static_cast<unsigned char>((value << index) >> index);
if (dataNum == count + 1) {
isEnd = true;
break;
}
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
index = 0;
}
else // index + y > 64
{
unsigned char t = 64 - index; // 先读t位
data[dataNum] = static_cast<unsigned char>((value << index) >> index);
index = y - t; // 再读y-t位
fin.read(reinterpret_cast<char*>(&value), sizeof(value));
data[dataNum] <<= index;
data[dataNum] |= (value >> (64 - index));
dataNum++;
if (dataNum == count + 1) {
isEnd = true;
break;
}
}
}
}
fin.close();
// 输出一下我们解压出来的像素信息
for (int i = 0; i <= 12; i++) {
cout << int(data[i]) << " ";
}
cout << endl;
///
/// 此处省略了将data数组按蛇形写入输出文件，即还原成2维数组的过程
///
delete[] data;
return true;
}
int main()
{
if (Compress("output.img"))
{
cout << "压缩成功" << endl;
}
else
{
cout << "压缩失败" << endl;
}
if (UnCompress("output.img"))
{
cout << "解压成功" << endl;
}
else
{
cout << "解压失败" << endl;
}
return 0;
}欢迎可爱的小伙伴给我留言呀，Mum~
1104
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
