# 读书笔记：如何编码整数？

**Published by:** [Aulee](https://paragraph.com/@aulee/)
**Published on:** 2023-04-20
**URL:** https://paragraph.com/@aulee/PpjhvLU4DMnvPCRRSHa9

## Content

在计算机网络的不同系统之间，或同一系统内部，数据传输的单位通常为byte。1个byte由8个bits组成， 为了方便常常显示为2个hexits。使用utf-8，我们可以把任意字符串编码为bytes。我们也需要办法把任意整数编码为bytes。使用modulo方法在前面的笔记中，我分析了bytes和256进制数之间的一一对应关系。我们由此可以把任意整数转化为bytes：def encode_num_by_modulo(num): result = bytearray() while num > 0: num, mod = divmod(num, 256) result.append(mod) return bytes(result) 例如，调用以上定义的函数，可把整数5738537157转化为little endian的bytes。>>> encode_num_by_modulo(5738537157) b'\xc5 \x0bV\x01' 使用比特位操作可以换一种角度实现上述过程。将任一整数转化为二进制数，并进行比特位操作。对二进制数按每8位截取成段，每段即为一个byte：def encode_num_by_bitwise(num): result = bytearray() while num: result.append(num & 0xff) num >>= 8 return bytes(result) 在上述函数中，我们每次以num & 0xff来截取二进制数字的最后8位，构成一个byte，然后通过向num >>= 8使二进制数向右缩短8位。这个过程一直进行下去，直到二进制数被取尽。 注意在截取二进制数的过程中，运用了0xff这个关键数。0xff == 255，0xff = 0b11111111。编码负整数上面的函数仅实现了对正整数的编码。需要进一步区分正整数和负整数。我们采用Distinguised Encoding Rules (DER)的格式来区分正数和负数，即要求负数编码的第1个bit为1，而正数编码的第1个bit为0。因此这时需要用到的一个关键数是0x80。该数的二进制表示为0b10000000，首个bit恰好为1。对于一个正整数来说，其二进制数的首个bit不是1即是0。如果首bit是0，则需保持，如果首bit是1，则需变更为0。若是取这个正整数的负数，如果原正数首bit已经是1，则需保持，如果原正数首bit为0，则需变更为以1为首个bit。具体的变更方式为：正数，首bit为1： 添加一个等于0的byte。负数，首bit为1： 添加一个等于0x80的byte。正数，首bit为0： 保持不变。负数，首bit为0： 对原来首个byte加上0x80。这样变更的结果是不仅区分了正负，而且使原来首bit为1的数加长了一个byte，而原来首bit为0的数长度不变。这样在解码时才能区分两种情况，实现完全的还原。编码函数定义如下：def encode_num(num): if num == 0: return b'' abs_num = abs(num) negative = num < 0 result = bytearray() while abs_num: result.append(abs_num & 0xff) abs_num >>= 8 if result[-1] & 0x80: # >= 128 if negative: result.append(0x80) else: result.append(0) elif negative: # < 128 and negative result[-1] |= 0x80 # + 128 return bytes(result) 注意在上面的编码格式中，0被编码为空byte而非0byte。 相应的解码函数如下：def decode_num(element): if element == b'': return 0 big_endian = element[::-1] if big_endian[0] & 0x80: negative = True result = big_endian[0] & 0x7f # takes the first byte except the first bit else: negative = False result = big_endian[0] for c in big_endian[1:]: result <<= 8 result += c if negative: return - result else: return result 其中用到的关键数为0x7f == 0b1111111，与&合用以提取7个bits。对于原数首bit为1的负数，其首个byte为0x80,此时0x7f & 0x80为0；对于原数首bit为0的负数，& 0x7f实现的是| 0x80的逆运算。

## Publication Information

- [Aulee](https://paragraph.com/@aulee/): Publication homepage
- [All Posts](https://paragraph.com/@aulee/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@aulee): Subscribe to updates