本文参考Sedgewick著Algorithms。
本文来自于Huffman Trie的作业要求。我使用了普林斯顿版算法进行移植。对于作者定义的BinaryStdIn/Out进行了移植与改造。
由于原文使用了Java语言与作者自定义的库,在移植时进行了一些适配。
移植重点:
C 中无法自主指定位移类型
而是通过有无符号类型判断
主体思路:
8 bit的unsigned char型buffer
buffer大小n
工具函数:
fillBuffer,从流中获取一个字节
clearBuffer,清空buffer,不足以0补齐
单位操作:
readBit:
n自减
从buffer中通过位运算>>n &1取出bit
n=0时,fill buffer
writeBit:
n自增
从buffer中通过位运算<<=1 |=bit置入bit
n=8时,clear buffer
单字节操作:
readByte:
字节对齐:
返回buffer,fill buffer
否则:
将buffer的后n位,与fill buffer后buffer的前8-n组合后返回。
writeByte:
字节对齐:
调用朴素输出byte
否则:
对每一位writeBit
多字节操作
readVal:
根据sizeof,进行循环
<<=8 |=readByte()
writeVal:
根据sizeof=N,进行循环
>>8*k (k from N-1 -> 0)&oxff
仓库地址
个人作业用途,因此只移植了部分方法。此外在异常处理上仍然存在问题。
https://github.com/sjtuzwj/Bit-IO-in-Cpp