编码生成与位运算

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void HuffmanCoder::generateCodes(HuffmanNode* root, const std::string& str) {
    if (root == nullptr) return;
    
    // 如果是叶子节点，保存编码
    if (!root->left && !root->right) {
        huffmanCode[root->data] = str;
        return;
    }
    
    // 递归遍历左子树（编码加0）
    generateCodes(root->left, str + "0");
    
    // 递归遍历右子树（编码加1）
    generateCodes(root->right, str + "1");
}

1
2
3
4
5

unsigned char byte = 1;  // 00000001

byte = byte << 1;  // 00000010 = 2
byte = byte << 2;  // 00001000 = 8
byte = byte << 3;  // 01000000 = 64

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

unsigned char byte = 0b10110011;  // 179

// 取出最高位
int highestBit = (byte >> 7) & 1;  // 1

// 取出最低位
int lowestBit = byte & 1;  // 1

// 检查第3位是否为1
if (byte & (1 << 3)) {
    std::cout << "第3位是1" << std::endl;
}

1
2
3
4

unsigned char a = 0b10110011;  // 179
unsigned char b = 0b11001100;  // 204

unsigned char result = a | b;  // 11111111 = 255

1
2
3
4
5
6

// 加密/解密的简单例子
char key = 0b01010101;
char data = 'A';  // 0b01000001

char encrypted = data ^ key;  // 0b00010100
char decrypted = encrypted ^ key;  // 0b01000001 = 'A'

1
2
3

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

1
2
3
4
5

void swap(int& a, int& b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

1
2
3
4
5
6
7
8

int getBit(unsigned char byte, int position) {
    return (byte >> (7 - position)) & 1;
}

// 示例
unsigned char byte = 0b10110011;
int bit3 = getBit(byte, 3);  // 0
int bit7 = getBit(byte, 7);  // 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

void HuffmanCoder::stringToBytes(const std::string& binaryString, 
                                std::vector<unsigned char>& bytes) {
    unsigned char byte = 0;
    int bitCount = 0;
    
    for (char bit : binaryString) {
        // 左移1位，为新的bit腾出空间
        byte = byte << 1;
        
        // 如果当前bit是1，设置最低位
        if (bit == '1') {
            byte |= 1;  // byte = byte | 1
        }
        
        bitCount++;
        
        // 每8位组成一个字节
        if (bitCount == 8) {
            bytes.push_back(byte);
            byte = 0;  // 重置
            bitCount = 0;
        }
    }
    
    // 处理剩余的不足8位的bit
    if (bitCount > 0) {
        // 左移，空位补0
        byte = byte << (8 - bitCount);
        bytes.push_back(byte);
    }
}

1

int padding = (8 - (encodedString.length() % 8)) % 8;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void HuffmanCoder::bytesToString(const std::vector<unsigned char>& bytes,
                                std::string& binaryString, int padding) {
    for (size_t i = 0; i < bytes.size(); i++) {
        unsigned char byte = bytes[i];
        
        // 最后一个字节：根据padding处理
        if (i == bytes.size() - 1) {
            for (int j = 0; j < 8 - padding; j++) {
                binaryString += ((byte >> (7 - j)) & 1) ? '1' : '0';
            }
        } 
        // 普通字节：读取全部8位
        else {
            for (int j = 0; j < 8; j++) {
                binaryString += ((byte >> (7 - j)) & 1) ? '1' : '0';
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// 在 main.cpp 中添加测试
void testBitConversion() {
    std::cout << "=== 测试位转换 ===" << std::endl;
    
    std::string binaryString = "10110011011101";
    std::vector<unsigned char> bytes;
    
    std::cout << "原始二进制字符串: " << binaryString << std::endl;
    std::cout << "长度: " << binaryString.length() << " bits" << std::endl;
    
    // 计算padding
    int padding = (8 - (binaryString.length() % 8)) % 8;
    std::cout << "Padding: " << padding << " bits" << std::endl;
    
    // 转换为字节
    HuffmanCoder coder;
    coder.stringToBytes(binaryString, bytes);
    
    std::cout << "字节数组: [";
    for (size_t i = 0; i < bytes.size(); i++) {
        printf("0x%02X", bytes[i]);
        if (i < bytes.size() - 1) std::cout << ", ";
    }
    std::cout << "]" << std::endl;
    
    // 转换回二进制字符串
    std::string recovered;
    coder.bytesToString(bytes, recovered, padding);
    
    std::cout << "恢复的二进制字符串: " << recovered << std::endl;
    
    if (binaryString == recovered) {
        std::cout << "✓ 转换正确！" << std::endl;
    } else {
        std::cout << "✗ 转换错误！" << std::endl;
    }
}

int main() {
    testBitConversion();
    return 0;
}

1
2
3
4

(0b10110011 >> 3) & 1
(0b10110011 << 2) | 0b00000011
0b10110011 & 0b11001100
~0b10110011 & 0xFF