整数与二进制相关的tricks。

整数

整数范围&数量级

注意一点，32位整数的数量级是40亿，也就是10^9，如果数据范围达到了10^9级别，则需要考虑是否采用64位整数来表示。

符号位与补码

C++支持无符号数和有符号数，重点关注有符号数的表示。

对于有符号数，最高位表示符号位，符号位为0，表示这个数是正数，符号位为1，表示这个数为负数。对于负数，计算机中使用补码来表示，补码等于原码除符号位外全部取反再加1。

以8位有符号数-1和-128为例，其原码，反码，补码如下：

-1：

-128：

一个数字从0开始不断加1，其表示的有符号数变化过程为：

• 0
• 正数不断增大
• 最大正数（符号位为0，其他全1）
• 最小负数（符号位为1，其余全0）
• 负数不断增大
• -1。

以上过程可用于判断正数累加是否溢出，即一个正数在累加的过程中突然从正数变成了负数，则表示这个数已经溢出了。

C++整数相关的常量

在头文件<limits.h>和<float.h>（C++对应为<climits>和<cfloat>）中有整数和浮点数相关的常量宏定义，可能用到的有以下几个：

这里注意一点，对于char类型，标准并没有规定它是signed还是unsigned类型，所以没法确定CHAR_MIN的值。如果编译器实现上把char当成有符号类型，则CHAR_MIN的值应该是-128，否则，如果编译器认为char是无符号类型，那么CHAR_MIN的值应该是0。以下是在Ubuntu20.04上的测试结果：

SCHAR_MIN:-128
SCHAR_MAX:127
UCHAR_MAX:255
CHAR_MIN:-128
CHAR_MAX:127

可以看出，这里编译器把char当成有符号来对待。

zigzag算法

zigzag算法用于压缩有符号的小整数，使得原本需要用4字节或8字节表示的小整数可以用更少的字节来表示。zigzag算法常用于网络传输之前对有符号数进行序列化和反序列化，以减少数据的传输量。

zigzag算法认为，在大多数情况下，我们使用的整数都是比较小的，比如id编号，评论计数等。对于这些较小的整数，如果全部使用4字节或8字节的基本类型来表示，会存在空间浪费问题。比如整数1，在4字节基本类型下表示为：

00000000_00000000_00000000_00000001

很明显，这里除了最后一位的1为有效位外，前面的0都是无效的，理想情况下，我们只需要1位就可以表示这个整数1。考虑到计算机以字节为最小存储单位，这里也只需要低8位 00000001 就可以表示整数1。

为了压缩小整数，应该让整数的有效数字尽量靠右分布，左侧只负责填充0，这样就可以把前导的0都去掉，为此，zigzag算法应运而生。

具体来说，zigzag对整数的处理如下：

• 针对整数的补码，把符号位放到最低位，其他位整体往前移一位。
• 去掉所有的前导0，从第一个1开始存储有效数字。

比如上面的1，经过zigzag操作后如下：

(00000000_00000000_00000000_00000001)_补码

(00000000_00000000_00000000_00000010)_zigzag

以上就是针对正数的zigzag操作，注意，这里我们只调整了符号位的位置，而没有修改bit位的值，所以并没有丢失信息，调整符号位后的数字仍然能够表示之前的数值。

然而，上面的算法对负数是无效的，考虑数字-1，它的zigzag表示如下：

(11111111_11111111_11111111_11111111)_补码

(11111111_11111111_11111111_11111111)_zigzag

很明显，按上面的操作，并没有实现小负数的压缩。所以，zigzag对负数有如下调整：

• 同样是针对补码，把符号位放到最低位，其他位整体往前移一位。
• 除最低位符号位外，其他位全部取反。
• 去掉所有的前导0，从第一个1开始存储有效数字。

按上面的操作对-1进行zigzag，如下：

(11111111_11111111_11111111_11111111)_补码

(11111111_11111111_11111111_11111111)_{符号位后移}

(00000000_00000000_00000000_00000001)_zigzag

由此，就实现了对负数的转换。虽然这里修改了bit位的值，但是只要按对应的规则进行解码，也就是在最低位为1时，先对前面的所有位取反，仍然能够还原出原来的数字。

综合起来，zigzag对整数的转换可以用下面的过程来描述：

• 针对补码，把符号位放到最低位，其他位整体往前移一位。
• 如果是正数，则无需处理，如果是负数，则除最低位符号位外，其他位全部取反。
• 去掉所有的前导0，从第一个1开始存储有效数字。

使用代码描述如下：

uint32_t EncodeZigzag32(int32_t &v) {
    return (v << 1) ^ (v >> 31);
}

uint64_t EncodeZigzag64(int64_t &v) {
    return (v << 1) ^ (v >> 63);
}

以32位的zigzag算法为例，v << 1会挤掉最高位的符号位，并将其他位整体往前移一位，以空出最低位0用于存储符号位。而v >> 31则会将符号位右移到最低位，同时这里还借用了有符号数右移时左侧会移入符号位的规则，如果v原本是正数，则右移时左侧会全部移入0，如果v原本是负数，则右移时左侧会全部移入1，再经过异或操作后，无论是正数还是负数，最低位符号位都是原来的符号位，而前面的前导位都变成了0，从而得到zigzag的结果。

接下来是zigzag的解码，解码代码如下：

int32_t DecodeZigzag32(uint32_t &v) {
    return (v >> 1) ^ -(v & 1);
}

int64_t DecodeZigzag64(uint64_t &v) {
    return (v >> 1) ^ -(v & 1);
}

以32位为例，v >> 1会还原原有的数据位，但是丢失了符号位，并且如果原来的数是个负数，还应该对全部的数据位进行取反。而-(v & 1)则首先会还原符号位，如果原来的数是正数，则-(v & 1)只能是0，如果原来的数是负数，则-(v & 1)会变成-1，对应二进制全1。通过异常运算，就可以正确还原符号位，并且，如果是负数，还会对前面的数据位进行取反，以正确还原负数的补码形式。

通过zigzag算法，可以将一个整数转换成以前导0开始的数字，接下来就是通过某种算法，把全部的前导0干掉，以实现长度的压缩，以下面的数字为例：

(00000000_00000000_00000000_10100010)_zigzag

zigzag采用了一种字节自表示法，通过插入额外的标志位的方式，实现了长度的压缩，具体操作如下：

1. 将zigzag后的数字从低到高，每7位划分成一组，以32位整数为例，可以划分出5个组，示例如下：
   (0000_0000000_0000000_0000001_0100010)_zigzag
2. 从左向右忽略所有的值为零的前导组。
3. 将所有的非零组扩展成8bit，也就是一个字节，具体的扩展规则是，从左往右的第一个非零组高位补0，后面的非零组高位补1，以构成最终的结果，如下：
   (00000001_10100010)_zigzag压缩

通过上面的算法，就可以把一个原本要4字节表示的整数压缩成了用2个字节来表示。

接下来是解码压缩后的数字，这个过程可以按下面的算法来实现：

1. 从低到高读入压缩后的字节。
2. 判断当前字节的最高位，如果最高位为1，表示还有后续位，保留当前字节的低7位，如果最高位为0，表示这是最后一个字节，取低7位构成最终数字即可。

上面的压缩和解压缩算法可以通过下面的代码来表示：

/**
 * @brief 32位zigzag编码压缩
 * 
 * @param value zigzag编码后的数字
 * @param buf 输出缓冲区
 * @return int 返回zigzag压缩后的字节数，范围1~5字节
 */
int WriteZigzag32(uint32_t value, char *buf) {
    uint8_t i = 0;
    while(value >= 0x80) {
        buf[i++] = (value & 0x7F) | 0x80;
        value >>= 7;
    }
    buf[i++] = value;
    return i;
}

/**
 * @brief 解码压缩后的32位zigzag数字
 * 
 * @param buf 存储压缩后的数字
 * @param size 长度
 * @return uint32_t 返回解压后的zigzap数字 
 */
uint32_t ReadZigzag32(const char *buf, int size) {
    uint32_t result = 0;
    int offset = 0;
    for(int i = 0; i < size; i++) {
        uint8_t cur = buf[i];
        if(cur & 0x80) {
            result |= ((uint32_t)(cur & 0x7f)) << offset;
        } else {
            result |= ((uint32_t)cur) << offset;
            break;
        }
        offset += 7;
    }

    return result;
}

/**
 * @brief 64位zigzag编码压缩
 * 
 * @param value zigzag编码后的数字
 * @param buf 输出缓冲区
 * @return int 返回zigzag压缩后的字节数，范围1~10字节
 */
int WriteZigzag64(uint64_t value, char *buf) {
    uint8_t i = 0;
    while(value >= 0x80) {
        buf[i++] = (value & 0x7F) | 0x80;
        value >>= 7;
    }
    buf[i++] = value;
    return i;
}

/**
 * @brief 解码压缩后的64位zigzag数字
 * 
 * @param buf 存储压缩后的数字
 * @param size 长度
 * @return uint64_t 返回解压后的zigzap数字 
 */
uint64_t ReadZigzag64(const char *buf, int size) {
    uint64_t result = 0;
    int offset = 0;
    for(int i = 0; i < size; i++) {
        uint8_t cur = buf[i];
        if(cur & 0x80) {
            result |= ((uint64_t)(cur & 0x7f)) << offset;
        } else {
            result |= ((uint64_t)cur) << offset;
            break;
        }
        offset += 7;
    }

    return result;
}

通过上面的代码可知，zigzag算法只对小整数有较好的性能，如果操作的数是较大的整数，则压缩后有可能比原始数据还要更占用空间，具体的，对于32位的整数，压缩后的数据大小为1~5字节，对于64位的整数，压缩后的数据大小为1~10字节。

以上代码可参考：https://github.com/zhongluqiang/playground/blob/main/randoms/zigzag/main.cpp

二进制