快读快写 原理详解

C++ 的 cin cout 和 C 的 scanf printf 等 IO 函数已经够我们是用了，但是它们很慢，尽管 cin cout 可以取消同步以优化，但还是不够快. 。

所以我们需要找一种更快的方式来输入输出，以防在 OI 中出现 TLE 的情况，便有了快读快输. 。

代码

注：它们只能读取整数 。

快读 read quickly

                        
                          template<class T>
inline void rq(T& x) {
    x = 0;
    char c;
    bool sign = 0;
    while(!isdigit(c = getchar()))
        if(c == '-')
            sign = 1;
    do
        x = (x << 3) + (x << 1) + (c ^ 48);
    while(isdigit(c = getchar()));
    if(sign)
        x = -x;
    return;
}

                        
                      

快写 write quickly

                        
                          template<class T>
inline void wq(const T& x) {
    T t = x;
    static char _wq_buffer[39];
    int bp = -1;
    if(!t) {
        putchar('0');
        return;
    }
    if(t < 0)
        putchar('-'), t = -t;
    while(t)
    {
        _wq_buffer[++bp] = t % 10 + '0';
        t /= 10;
    }
    for(int i = bp; i >= 0; i--)
        putchar(_wq_buffer[i]);
    return;
}

                        
                      

代码解释

快读

第一部分

                        
                          template<class T>
inline void rq(T& x)

                        
                      

template 是一个 C++ 的关键字，在这里它的作用是声明函数模板. 尖括号里的 class T 可以理解为声明一个类型 T ，这里的 class 也可以替换成 typename ，并无两样. 。

这个 T 是什么类型一般取决于这里的 x 是什么类型. 例如:

                        
                          int x;
rq(x); // T = int

long long y;
rq(y); // T = long long

char z;
rq(z); // T = char

                        
                      

inline 是 内联 ，在这里是 内联函数 ，加上它可能会让程序运行的速度变快，类似于宏展开，但它做出的优化取决于编译器和函数的复杂程度， 有兴趣的可以看这位大佬的 博客 . 。

void 在这里的意思是无返回类型函数. 。

T& x 在这里是 引用传参 ，在此函数内更改 x 对应传进来的参数也会更改，这里它和指针极为相似:

                        
                          void swap1(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}

void swap2(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int main() {
    int x = 1, y = 2;
    swap1(x, y); // x = 2, y = 1
    swap2(&x, &y); // x = 1, y = 2
}


                        
                      

这两个的函数的功能都一样，在汇编层面也一样，只不过 swap1 比 swap2 的写法更简便，更像是 C++ 相对于 C 特有的语法糖. 。

第二部分

                        
                          x = 0;
char c;
bool sign = 0;

                        
                      

x = 0 ，这里一般清零，因为传进来的 x 的值不确定，如果不是 \(0\) 会导致接下来的运算出错，从而导致读入无效. 如果可以保证传进来的 x 等于 \(0\) ，则可以省略这一行. 。

char c ，这个 c 是读入的字符，一般 IO 都是靠字符，然后再转化为数字等别的类型. 。

bool sign = 0 ，这个 sign 表示 x 的符号， \(0\) 表示 \(x \geq 0\) ， \(1\) 表示 \(x < 0\) . 在这里必须清零，因为这是在函数内，如果不清零，它的值是不确定的，从而导致 x 的正负性受到影响. 如果可以保证读入的数是一个非负整数，则可以省略这一行以及相关的内容. 。

第三部分

                        
                          while(!isdigit(c = getchar()))
    if(c == '-')
        sign = 1;

                        
                      

此部分是跳过不是数字的时候并确定 x 的符号. 。

c = getchar() 是读入一个字符， getchar() 是一个较快的方法，比 cin >> c 和 scanf("%c", &c) 快. 。

!isdigit(...) 是判断该字符是否是一个非数字. 为什么不用 a < '0' || '9' < a 之类的？因为直接 !isdigit(...) 比这个快， isdigit 内部实现类似于打表，有兴趣的可以看这位大佬的 博客 . 。

                        
                          if(c == '-')
    sign = 1;

                        
                      

显然是确定符号. 但是这种判断有个缺点，当输入:

                        
                          ho-mo114514

                        
                      

时， sign = 1 ，显然这是不正确的. 。

如果可以保证一开始读入的就是符号或是有效数字位，或已知输入的格式，则可以删除这个 while 循环并做出相应的更改. （我建议还是不要删，删了之后处理格式会很麻烦） 。

第四部分

                        
                          do
    x = (x << 3) + (x << 1) + (c ^ 48);
while(isdigit(c = getchar()));

                        
                      

此部分是边读边更改 x . 。

(x << 3) + (x << 1) 是 x * 10 . 。

x << 3 表示将 x 的二进制位左移三位， x << 1 同理. 。

什么是左移、右移?

假设 a 是一个 \(8\) 位的数，并且 a = 4 ，则 a 在二进制下是 00000100 . 左移三位得 00010000 ，表示 \(32\) ，也就是 \(4 \times 2^3\) 。

不难得出 a << b \(=a \times 2^b \space (b \geq 0)\) ， a >> b \(=a \div 2^b \space (b \geq 0)\) . 。

则上面的表达式等价于 \(x \times 2^3 + x \times 2^1 = x \times 8 + x \times 2 = x \times 10\) . 。

c ^ 48 是 c - '0' ，将一个数字字符化为数字. 。

其中 ^ 表示 异或 ，在数学中用 \(\bigoplus\) 表示，有基本的四种基本的运算法则： \(0 \bigoplus 0 = 0\) ， \(0 \bigoplus 1 = 1\) ， \(1 \bigoplus 0 = 1\) ， \(1 \bigoplus 1 = 0\) . （同0异1） 。

\(48\) 在 ASCII 中对应的字符是 0 ，二进制是 00110000 。

第五部分

                        
                          if(sign)
    x = -x;

                        
                      

此部分是添加 x 的符号. 有的可能把 -x 写成 ~(x - 1) ，这都表示取 x 的倒数，在汇编层面都一样，会被编译器优化. 。

快写

第一部分

                        
                          template<class T>
inline void wq(const T& x)

                        
                      

此部分与快读的第一步分基本一样，只不过多了个 const . const 在这里表示 x 在此函数内不可被更改，这样就可以写类似这样的代码 wq(1) wq(a + b) . 。

第二部分

                        
                          T t = x;
static char _wq_buffer[39];
int bp = -1;

                        
                      

因为 x 不可变，所以复制了一份给 t ，下面关于 x 的操作一律用 t 代替. 。

static 在这里表示静态的，相当于在全局定义 _wq_buffer . 给 buffer 加 _wq_ 这个前缀是为了避免和其他的关键字冲突. \(39\) 是 __uint128_t 的十进制下最大位数（ \(2^{127} - 1 = 340282366920938463463374607431768211455\) \(39\) 位），如果需要的话可以开更多位. 。

bp 是 _wq_buffer 当前的有效位数的位置，这里初始值为 \(-1\) 是为了下面方便计算. 。

第三部分

                        
                          if(!t) {
    putchar('0');
    return;
}
if(t < 0)
    putchar('-'), t = -t;

                        
                      

特判一些情况，但是直接 -t 的会导致像 \(-128\) \(-65536\) \(\cdots\) \(-2^{8 \times \text{sizeof(T)}}\) 这样的数会输出乱码. 。

第四部分

                        
                          while(t)
{
    _wq_buffer[++bp] = t % 10 + '0';
    t /= 10;
}

                        
                      

每次取 t 的个位，然后转化为数字字符倒序存到 _wq_buffer 里，直到 t = 0 . 。

第五部分

                        
                          for(int i = bp; i >= 0; i--)
    putchar(_wq_buffer[i]);

                        
                      

输出，因为是倒序存，所以要倒着输出. 。

参考文献

函数模板 。

pathenon. isdigit()极品实现 . 。

恋喵大鲤鱼. C++ inline 函数简介 。

最后此篇关于快读快写原理详解的文章就讲到这里了,如果你想了解更多关于快读快写原理详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。