整数与二进制相关的tricks。

整数

整数范围&数量级

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

符号位与补码

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

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

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

-1：

原码1000 0001
反码1111 1110
补码1111 1111

-128：

原码无
反码无
补码1000 0000

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

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

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

C++整数相关的常量

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

宏描述可能值
SHRT_MINshort int类型的最小值-32768
SHRT_MAXshort int类型的最大值32767
USHRT_MAXunsigned short int类型的最大值65535
INT_MINint类型的最小值-2^31
INT_MAXint类型的最大值2^31 - 1
UINT_MAXunsigned int类型的最大值2^32 - 1
LONG_MINlong int类型最小值-2^63
LONG_MAXlong int类型最大值2^63 - 1
ULONG_MAXunsigned long int类型最大值2^64 - 1
LLONG_MINlong long int类型最小值 -2^63
LLONG_MAXlong long int类型最大值2^63 - 1
ULLONG_MAXunsigned long long int类型最大值2^64 - 1

FLT_MIN

DBL_MIN

LDBL_MIN

各浮点类型最小值

1.17549e-38

2.22507e-308

3.3621e-4932

FLT_MAX

DBL_MAX

LDBL_MAX

各浮点类型最大值

3.40282e+38

1.79769e+308

1.18973e+4932

这里注意一点，对于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。

为了压缩小整数，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转换：

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

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


二进制