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

为了压缩小整数，zigzag算法的操作如下：

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

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

(00000000_00000000_00000000_00000001)_补码

(00000000_00000000_00000000_00000010)_zigzag

以上就是针对正数的zigzag操作。

然而，上面的算法对负数是无效的，考虑数字-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

由此，就实现了对负数的压缩。

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

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

使用代码描述如下：

static uint32_t EncodeZigzag32(int32_t &v) {
    if(v > 0) {
        return v << 1;
    } else {
        return (-v) << 1 - 1;
    }
}

static uint32_t EncodeZigzag64(int64_t &v) {
    if(v > 0) {
        return v << 1;
    } else {
        return (-v) << 1 - 1;
    }
}

当然，正数和负数的情况下也可以合并到一起，通过下面这一条语句实现zigzag转换：

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

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

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

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

二进制