C++:竞争性编程技巧的解释

Question

在用于竞争性编程的DMOJ在线判断中,如果问题只需要读取无符号整数数据类型,那么更快执行时间(C++)的提示之一是将此宏添加到顶部.

这是如何工作的以及使用它的优点和缺点是什么？

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x= (x<<3)+(x<<1)+_-'0');}while(0)
char _;

资料来源:https://dmoj.ca/tips/#cpp-io

Answer 1

首先让我们重新格式化一下:

#define scan(dest) \
  do { \
    while((dest = getchar()) < '0'); \
    for(dest -= '0'; '0' <= (temp = getchar()); dest = (dest<<3) + (dest<<1) + temp - '0');
  } while(0)
char temp;

首先,外部do{...}while(0)只是为了确保正确解析宏.有关详细信息,请参见此处

接下来,while((dest = getchar()) < '0');- 这也许只是,dest = getchar()但它通过丢弃角色下面(但不是上面)的任何字符来做一些额外的工作'0'.这很有用,因为空格字符都小于ascii中的0字符.

宏的肉是for循环.首先,初始化表达式dest -= '0',通过利用ascii编码中的0-9个字符相邻且顺序的事实,将dest设置为由字符表示的实际整数值.因此,如果第一个字符是'5'(值53),则减去'0'(值48)会得到整数值5.

条件语句'0' <= (temp = getchar())执行几项操作 - 首先,它获取下一个字符并将其分配给它temp,然后检查它是否大于或等于该'0'字符(因此将在空格上失败).

只要字符是数字(或至少等于'0'),就会计算增量表达式.dest = (dest<<3) + (dest<<1) + temp - '0'- temp - '0'表达式从ascii到数值执行与之前相同的调整,并且移位和添加只是一种模糊的乘以10的方式.换句话说,它相当于temp -= '0'; dest = dest * 10 + temp;.乘以10并添加下一个数字的值就是构建最终值的原因.

最后,char temp;声明临时字符存储,以便在程序中的后续宏调用中使用.

至于你为什么要使用它,我怀疑它会提供任何可衡量的好处,比如scanf或类似的东西atoi.