左神算法基礎班C++實作目錄
- 1.壓縮算法
-
- 原理
- 代碼
- 2.解壓縮算法
-
- 原理
- 代碼
- 3.完整代碼
int類型的表示範圍從0~4294967295，共占用四個位元組。而在實際進行中，某些較小的數在除了真正存儲的數值以外，其他位元組填充值為0，例如7的二進制表示如下，如何将未用上的前三個位元組去掉以便節省空間呢？
1.壓縮算法
原理
下圖①表示整數67335中四個位元組實際存儲的資料，本壓縮算法将每個位元組的最高位作為标志位辨別整型數值是否結束，未結束置1，結束置0。從低位向高位類推，每個位元組都有一位不進行存儲，那麼四個位元組共計有四位需要單獨存儲。也就是說，本壓縮算法能夠将4個位元組的數值壓縮為1~5個位元組。
将67335按照七位進行劃分，得到②。從右側向左側進行填充标志位，67335按照七位劃分共存儲三個位元組，後兩個标志位置1，前三個标志位置0，得到③。最後留下實際存儲不為0的位元組，得到④即壓縮後的位元組。
再舉一個例子：将255壓縮
255作為int類型存儲如①，将其按照七位劃分占用兩個位元組存儲②，将後一個位元組标志位置1，将前一個位元組标志位置0表示存儲結束③，最終結果如④
代碼
根據原理說明，需要從後向前按七位進行劃分，如果除掉此七位剩餘的數值還不為0則說明為存儲未結束，将标志位置1，如果數值為0，表示存儲結束，标志位置0。
假設傳入的值為
value
擷取後七位的數值c：可以使用
c = value & 0x7f
按七位進行一次劃分：可以使用右移
value>>=7
将标志位置1：
c |= 0x80
整理一下
unsigned char buf[100];
int len = 0;
void test_compress(int value) {
do {
unsigned char c = (unsigned char)(value&0x7f); //擷取後七位
value >>= 7; //擷取餘下的值
if (value)
c |= 0x80; //值不為0表示為存儲完将标志位置1
buf[len++] = c; //存儲這一個位元組，實際是7位資料加1個标志位
} while (value); //餘下值不為0繼續存儲
}
注意：由于是按位操作，需要列印函數檢視是否正确
- 列印原始資料二進制的
print_ori
此函數每8位加一個空格進行劃分
void print_ori(int c) {
for (int i = 31; i >= 0; i--) {
if (i == 7 || i == 15 || i == 23)
cout << " ";
if (0 != (c >> i & 0x1))
cout << "1";
else
cout << "0";
}
printf("\n");
}
- 列印一個位元組二進制的
print_one_byte
此函數在
do while
循環中列印處理的這個位元組
void print_one_byte(unsigned char c){
for (int i = 7; i >= 0; i--) {
if (0 != (c >> i & 0x1))
cout << "1";
else
cout << "0";
}
printf(" ");
}
壓縮算法完整代碼
#include<iostream>
using namespace std;
unsigned char buf[100];
int len = 0;
void print_ori(int c) {
for (int i = 31; i >= 0; i--) {
if (i == 7 || i == 15 || i == 23)
cout << " ";
if (0 != (c >> i & 0x1))
cout << "1";
else
cout << "0";
}
printf("\n");
}
void print_one_byte(unsigned char c){
for (int i = 7; i >= 0; i--) {
if (0 != (c >> i & 0x1))
cout << "1";
else
cout << "0";
}
printf(" ");
}
void test_compress(int value) {
do {
unsigned char c = (unsigned char)(value&0x7f);
value >>= 7;
if (value)
c |= 0x80;
print_one_byte(c);
buf[len++] = c;
} while (value);
}
int main() {
int ori = 255;
print_ori(ori);
test_compress(ori);
return 0;
}
上一行是255的原始資料列印，下一行是壓縮後的結果
2.解壓縮算法
原理
解壓縮是壓縮的一個逆過程，首先一個一個位元組讀取壓縮後的數
c
并擷取後七位（
x = c & 0x7f
）;将得到的值存入
value
，如果
c
的标志位為1則繼續讀取，否則結束。需要注意的是，由于壓縮從後向前存儲7位，是以每次讀出的數需要先遞增左移（第一次左移0位，第二次左移7位，第三次左移14位，第四次左移21位，第五次左移28位）再進行存儲。
代碼
void test_uncompress(){
char c; //單個位元組的數值
int len = 0; //從buf中讀取的位置
int s = 0; //左移變量，每次增加7
int value = 0; //存儲實際的值
do {
c = buf[len++];
unsigned int x = (c & 0x7f); //擷取後七位
x <<= s; //左移
value += x; //存入value
s += 7;
} while (c & 0x80); //判斷标志位
printf("%d\n", value);
}
3.完整代碼
包括四個函數：
- print_ori：将四個位元組的int按照二進制進行列印
- print_one_byte：列印一個位元組
- test_compress壓縮算法，輸入int型數值value，将壓縮後的數值存入buf
- test_uncompress解壓縮算法，讀取buf中壓縮的數值，解壓縮為int
#include<iostream>
using namespace std;
unsigned char buf[100];
int len = 0;
void print_ori(int c) {
for (int i = 31; i >= 0; i--) {
if (i == 7 || i == 15 || i == 23)
cout << " ";
if (0 != (c >> i & 0x1))
cout << "1";
else
cout << "0";
}
printf("\n");
}
void print_one_byte(unsigned char c){
for (int i = 7; i >= 0; i--) {
if (0 != (c >> i & 0x1))
cout << "1";
else
cout << "0";
}
printf(" ");
}
void test_compress(int value) {
do {
unsigned char c = (unsigned char)(value & 0x7f); //擷取後七位
value >>= 7; //擷取餘下的值
if (value)
c |= 0x80; //值不為0表示為存儲完将标志位置1
print_one_byte(c);
buf[len++] = c; //存儲這一個位元組，實際是7位資料加1個标志位
} while (value); //餘下值不為0繼續存儲
}
void test_uncompress(){
char c; //單個位元組的數值
int len = 0; //從buf中讀取的位置
int s = 0; //左移變量，每次增加7
int value = 0; //存儲實際的值
do {
c = buf[len++];
unsigned int x = (c & 0x7f); //擷取後七位
x <<= s; //左移
value += x; //存入value
s += 7;
} while (c & 0x80); //判斷标志位
printf("%d\n", value);
}
int main() {
int ori = 67335;
cout << "ori: " <<ori << endl;
print_ori(ori);
cout << "compress: " << endl;
test_compress(ori);
cout << endl<<"uncompress: " ;
test_uncompress();
return 0;
}