uint32在c语言范围是多少_快速范围判断：到底是快还是慢？

我在前文《C语言有什么奇技淫巧？》中介绍过快速范围判断，用来优化无符号整数：

if (x >= minx && x <= maxx) ...

存在的两次分支判断，可以减少为一次，写成：

if (((x - minx) | (maxx - x)) > = 0) ...

如果语言警察们担心有符号整数回环是未定义行为的话，可以写成这样：

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

性能相同，但避开了有符号整数回环，改为无符号回环，合并后转为有符号判断最高位。

进一步多个变量范围判断还可以继续优化成，注意下面都是无符号整数：

if ( ( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

让四次判断减少为 1 次判断，这背后的道理很简单，当范围是变量时，多算两次减法完全无伤大雅，但是多一两次判断，对性能的影响是很大的：Compiler Explorer - C++ (x86-64 gcc 10.1)

两次判断语句。

有人给出了《第一个评测》：

链接：http://quick-bench.com/5ZZAqjAS4ReTpl3XOXM9jJQ5Kgc

认为貌似“快速范围判断”反而变慢了，看右边红色柱形更高，耗费的时间更长。

真是这样的么？看看他写的语句：

if ((i - min) | (max - i) >= 0) ...

他写少了一个括号，由于 C 语言的“符号优先级”中，比较 >= 符号比比特或具有更高优先级，所以其实上面会判断算 (max - i) >= 0 ，还需要计算左边那一串，最终比特或得到一个值再进行一次判断，这样当然慢。正确的写法是：

if ( ((i - min) | (max - i)) >= 0) ...

多加个括号就行，结果立马就反过来了：

链接：http://quick-bench.com/uIUtzZ1VUkbGaslhpFrt_SxBe7A

快速范围判断显然快了 5.5%，这个情况还不够准确，因为很长时间 CPU 分支预测总是正确的，我们把输入变为随机数（保证公平，两个用例前面都初始化成相同的随机化种子）：

链接：http://quick-bench.com/9FTuG6uD83G0d0CE7lz-ZJuJ_l4

差距更加明显，快速范围判断的代码比 && 比较快了近一倍，这是十分明显的提高。

当然，如果你本身就可以判断，大部分时候 x，y 都在范围外，少部分才在范围内：

if (x >= minx && x <= maxx) ...

即上面条件 90% 的时候都是为假，那么直接用 && 写法即可，因为第一个 x >= minx 为假就结束了，后面判断可以被短路。但是如果你没法确定真假，或者大部分时候 x 都是在范围内的，那么显然 “快速范围判断”能够帮助你提升代码性能。

这个 quick-bench 经常测试不准，时快时慢，有些不踏实，咱们单独写个程序最实在：

#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <stdlib.h>
#include <chrono>
#include <thread>


int64_t clock_realtime()
{
    return std::chrono::duration_cast<std::chrono::nanoseconds>(
        std::chrono::system_clock::now().time_since_epoch()).count();
}

void isleep(unsigned long millisecond)
{
    std::this_thread::sleep_for(std::chrono::milliseconds(millisecond));
}


#define TIMES 10000
#define N 10000

uint32_t min = 3333, max = 6666;
uint32_t pos[N];

void benchmark1()
{
    isleep(1000);
    int64_t ts = clock_realtime();
    int s = 0;
    for (int k = 0; k < TIMES; k++) {
        for (int i = 0; i < N; i++) {
            uint32_t j = pos[i];
            if (j >= min && j <= max) {
                s += j;
            }
            else {
                s -= j;
            }
        }
    }
    ts = clock_realtime() - ts;
    printf("bench 1: time=%d s=%dn", (int)ts, s);
}

void benchmark2()
{
    isleep(1000);
    int64_t ts = clock_realtime();
    int s = 0;
    for (int k = 0; k < TIMES; k++) {
        for (int i = 0; i < N; i++) {
            uint32_t j = pos[i];
            if ((int32_t)((j - min) | (max - j)) >= 0) {
                s += j;
            }
            else {
                s -= j;
            }
        }
    }
    ts = clock_realtime() - ts;
    printf("bench 2: time=%d s=%dn", (int)ts, s);
}

int main(void)
{
    for (int i = 0; i < N; i++) {
        pos[i] = rand() % 10000;
    }

    benchmark1();
    benchmark2();
    return 0;
}

编译运行（gcc 9.2）：

$ gcc -O3 -msse3 branch.cpp -o branch -lstdc++
$ ./branch

结果：

bench 1: time=149798100 s=-1631139824
bench 2: time=71018900 s=-1631139824

基本快一倍。