快读中位运算部分简析

代码

1
2
3
4
5
6
7
8
9
10
11
inline int read() {
    short int v=1;
    int s=0;
    char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())
        if (ch=='-') v=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())
        s = (s<<1)+(s<<3)+(ch^'0');
    return s*v;

}

简析

1
s = (s<<1)+(s<<3)+(ch^'0');

显然上面那句代码可以加速。

所以这篇博客我将讨论这行位运算的原理。

解析

1
s = s*10 + ch - '0';

上面这行是不用位运算的版本。

显然，经过对比我们可以得出：

1
s*10

和

1
(s<<1)+(s<<3)

还有

1
ch - '0'

和

1
ch^'0'

是同样作用的。

先解释前者，我们知道：

一个数向左移动$N$位，则在数学意义上，代表乘以$2^N$。

所以，很明显的，这句代码等价于：

1
(s*2) + (s*8)

根据加法交换律，上面那句代码等价于：

1
s*10

接着再来看后半部分

后半部分的作用是让输入的字符转为数字

其中ch - '0'的作用是让两个ASCII码相减，得到一个纯数字。

而ch^'0'的作用也一样。

我们知道，$0$的ASCII码是$48$，而$48$的二进制是$110000$。

而所有数字的ASCII码都在110000~111001之间，使用异或运算则可以去掉前面的11变成00，后面的每一位都会和0做异或运算，仔细想想也就是保持原样，我们也就得出了一个纯数字。

以上。