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

By [Aulee](https://paragraph.com/@aulee) · 2023-04-20

---

在计算机网络的不同系统之间，或同一系统内部，数据传输的单位通常为byte。1个byte由8个bits组成， 为了方便常常显示为2个[hexits](https://en.wiktionary.org/wiki/hexit)。使用utf-8，我们可以把任意字符串编码为bytes。我们也需要办法把任意整数编码为bytes。

### 使用modulo方法

在前面的[笔记](https://mirror.xyz/0x78874f895B96BEc9f48e67BAE188309D285b45a0/QjO9H3sFZSWFyTVkRBnANdmOLocXsZB_9Dx_OQVVmjE)中，我分析了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`的逆运算。

---

*Originally published on [Aulee](https://paragraph.com/@aulee/PpjhvLU4DMnvPCRRSHa9)*