【整理搬运】快读、快写


比较详细的原理介绍↓

 

 来源:https://www.cnblogs.com/648-233/p/10675983.html

作者: _Alex_Mercer 

 

某些题中,读入数据往往比较繁多,故输入是一大难题,有时会遇到一些读入困难,cin与scanf也许都解决不了,这时掌握快读是必要的。

基本快读思想如下(分析整数):

一位一位读入,对当前读入字符进行分析,

先判断首位是否为负号,并进行相应处理,

如果读入的为数字,将其做处理后存入,

遇到空格视为停止,返回所存值(return)。

一般快读代码如下:

 
#include<bits/stdc++.h>
using namespace std;
#define mod 10000007 //取模数据,一般大数据题目会做要求
int read(){    //快读多被定义为long long
    int f=1;   //存负
    int x=0;
    char c=getchar();
    while(c<'0'||c>='9'){
        if(c=='-') f=-1;
        c=getchar();     //不断读入,直到读入字符在0-9范围内
    }
    while('0'<=c&&c<='9'){
        x=x*10+c-'0';    //将原来的数据*=10,借此把新数字当做个位存放
        x%=mod;          //取模
        c=getchar();     //读入下个字符,如果下个字符非数字,则跳出,快读结束
    }                    //只要输入合法,快读处理数据就一定正确,毕竟合法输入的同一整数之中不存在除数字外的其他符号
    return x*f;
}
int main(){
    int a=read();
    cout<<a;
    return 0;
}
 

然而这在一般快读中并不是最快的,主要优化有以下几点:

1. 对于它

int read()

可以在int前加上inline,inline对于多次调用的函数有着非常明显的加速作用,而明显快读非常常用,inline具体原理大概是将该函数在任意调用处展开,详细原理还是的上网查吧

2.对于

 x=x*10+c-'0';

数据的四则运算固然简单,然而比起位运算要慢

(位运算就是将数据以二进制(毕竟计算机认得二进制)进行运算)

二进制比十进制计算是要快一点的,

所以可以改成下面这样:

 x=(x<<3)+(x<<1)+(c^48);

其中,x<<n表示x的二进制向左移动n位,空位补0,相当于x*=2n

这里的(x<<3)+(x<<1)相当于

  x*23+x*21,

=x*(8+2)

=x*10

而c^48则是“异或运算”

即二进制对应位置不同时该位为1,否则为0

即判断对应数位是否不同

1 0 0 1 0 1 1 0与

1 1 0 0 1 1 0 1两数运算结果为

0 1 0 1 1 0 1 1,

因其算法具体为0^0=0,0^1=1,1^0=1,1^1=0

像是二进制的加法,但没有进位,所以被称作(二进制)不进位加法

这里的c^48则是特殊情况,因为‘0’=48,而48=(110000)2

众所周知,后面四位能表示的最大十进制整数为15,故表示ACSII码中的10个数字绰绰有余

并且因为48-57中,二进制形式其第五第六位皆为1,所以进行异或运算时会被算为0,即48-57中每个数由于都含有这两位数,都减去了48,而48的后面4位全是0,故49-57的数与48的差异能且仅能在后四位体现,从48-57,后四位恰好组成0-9,且一一对应,故可用^运算来进行数字的ASCII码转换。

这里加上c^48等同于将此字符所代表数字做个位加进去,而位运算相当快,所以。。。

这算是“快读”

 
 

 


来源:C++手写快读详解(快速读入数字)

作者:_qcr

 

众所周知,C++里是自带读入的(这不废话吗)

例如:

int a;
    cin>>a;

这样的读入理解简单,适合初学者,但是非常慢。

再例如:

int a;
    scanf("%d",&a);

这样的读入就比较快了,也较好理解,在题目不卡时间的情况下可以通过大部分题。

 

——但是,还不够快。

 

有一些毒瘤题目是非常卡时间的,稍微慢一点就过不去,因此,快读应运而生:

 
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
 

原理其实也不难,我们知道,单个读入字符要比读入数字快得多(别问我,我也不知道为什么)

因此我们可以以字符的形式读入,然后自己计算出数字

 

重点是第十行:x=(x<<1)+(x<<3)+(ch^48);

" << x" 操作为二进制操作,原理是将原二进制数向左平移 x 位,右边原位置以 0 补齐

例如:

 原二进制数 10001   经过 << 2 后,变为 1000100 

 其效果: x << 1 == x * 2;

      x << 2 == x * 2 * 2;

      x << 3 == x * 2 * 2 * 2;

      ………………

所以 (x<<1)+(x<<3) 可视为 x * 10;

后面的 (ch^48) 效果为 ch - = '0';

 

getchar() 为读入单个字符(包括空格 ,换行符)

 

当然,快读也有不适用的时候,例如读入中包含大量无用空格

1 1      1 12
2      3     3
3  2        1
1       5  2

这时就识趣的别用快读了吧!

快读 && 快写

快读和快写,就是利用字符串的一些特殊性质进行读入,输出;在一定情况下(输入数据十分庞大),可以大大的缩短时间。

注意这个快读是非常的重要的,我想这应该是想要在OI这条路上走远的所有OIer必须会的东西。养成每次写题目都加上快读的好习惯,有可能会在关键的时候救你一命!

普通快读

inline void read(int &x){
   int s = 0, w = 1; char ch = getchar();
   while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   x = s*w;
   return ;
}

getchar ,就是将数字当字符读取,比scanf快很多
w用来判断数字是不是负号,
如果想的话可以再压一下行

普通快写

inline void out(int a){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(a>9)write(x/10);
    putchar(a%10+'0');
}  

快写也非常简单,利用int与ASCII码之间转换,实现快读快写的目的。

欢迎任何形式的转载,但请务必注明出处。
限于本人水平,如果文章和代码有表述不当之处,还请不吝赐教。


 
来自luogu某位大佬的快读程序↓
while (c<'0' || c>'9')
        (c == '-') && (w = -w), c = getchar();  //(c=='-')&&(w=-w)相当于if(c=='-') w = -w
    while (c>='0' && c<='9')
        x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
    x *= w;
满堂花醉三千客,一剑霜寒十四州
原文地址:https://www.cnblogs.com/phemiku/p/11409055.html