负整数除2的幂次

Last Updated: 2023-12-03 04:00:26 Sunday

-- TOC --

我曾有个错误的认知：整数乘除2的幂次，可以通过位移的方式来快速计算。这个认知也不是全错，正整数总是正确的，而对于负数，在除2的幂次时，有个坑！

右移是Round to Floor，而整数除是Round to Zero！在计算正整数时，floor和zero的在数轴上的方向一致，因此计算结果也一致，而在计算负整数时，floor和zero的方向相反，计算结果不一致。

#include <stdio.h>
#define PRINT(e)  printf(#e " = %d\n", e)

int main(void) {
    int a = -99;
    PRINT(a);
    PRINT(a>>1);
    PRINT(a/2);
    PRINT((a+2-1)>>1);
    PRINT(a>>2);
    PRINT(a/4);
    PRINT((a+4-1)>>2);
    PRINT(a>>3);
    PRINT(a/8);
    PRINT((a+8-1)>>3);
    return 0;
}

输出：

a = -99
a>>1 = -50
a/2 = -49
(a+2-1)>>1 = -49
a>>2 = -25
a/4 = -24
(a+4-1)>>2 = -24
a>>3 = -13
a/8 = -12
(a+8-1)>>3 = -12

Look....负数的右移和负数的整数除的结果不同！

当然，可以间接使用右移，上面这段测试代码已经展示了，计算公式为：(N+2^k-1)>>k！

有时编译器吐出来的汇编代码，就是用这个公式优化过的，右移还是快的，只是对负数而言，要做个biasing！

本文示例代码用到了C语言宏定义语句中的#符号。

C语言的>>，是属于算术右移，不是逻辑右移，前者在空出来的bit位上补原数值的MSB，后者只是简单补0。负整数的算数右移，在空出来的位置，补1。

C语言的整数除，小数部分会被简单的丢弃，因此就是round to zero!

本文链接：https://cs.pynote.net/sf/c/202307201/

-- EOF --

-- MORE --