working of a faster I/O method

Question

I was studying faster I/O methods for programming problems, I found out this method of using getchar_unlocked() (though risky but still).

I looked around quite a bit but couldn't get how it scanned an integer value or in other words what do the 4 lines mean and how they work in the scanint() function defined below

#include<iostream>
#include<cstdio>
#define gc getchar_unlocked

void scanint(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc())   
        {x = (x<<1) + (x<<3) + c - 48;}
}

int main()
{   
    int n,k;
    scanint(n);
    scanint(k);
    int cnt=0;
    while(n--)
    {
     int num;
     scanint(num);
     if(num%k==0)cnt++; 
    }    
    printf("%d",cnt);
    return 0;             
}

Answer 1

ASCII value of '0' is 48, and each subsequent digit goes one more. i.e. '1'->49, '2'->50... and so on.

A side effect of this is that if you take a character digit, meaning something between '0' and '9', and subtract the ASCII value of '0' from it, then you get the integer value of that digit.

So in the line x = (x<<1) + (x<<3) + c - 48;, the c-48 part is converting the digit character (an ASCII coded character) into a number between 0-9 that refers to that character.

(x<<1)+(x<<3) is the same as x * 10,(For more information, checkout http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add and How can I multiply and divide using only bit shifting and adding? ) in fact this part of the code is unnecessarily obfuscated. The compiler can optimize multiplication in many different ways to make it as fast as possible, so we don't need to manually implement the bit shifting. It makes for an interesting college level puzzle though.

for(;(c<48 || c>57);c = gc()); This loop will ignore all the characters until it receives one that falls within the '0' to '9' range. So if the user started by typing a space or any other character, it'll simply be ignored.

By the time the code hits for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;} line, the variable c is already initialized to the first digit that the user has typed. This loop leaves the initialization empty so the control flow will dive right into the loop and start computing the number as each character is typed.

The loop will go on as long as the user keeps typing digits, as soon as the user types something other than a digit, the loop will terminate, finalizing the number.

Until the user keeps typing digits, the line x = (x<<1) + (x<<3) + c - 48; will keep getting executed over and over again, with each time c being the character just typed. And x will multiply itself by 10 and add the new digit in.

Let's say the user types 2014. Here's how the values in c and x will progress.

c = '2' #ASCII value 50
x = 2
c = '0' #ASCII value 48
x = 20
c = '1' #ASCII value 49
x = 201
c = '4' #ASCII value 52
x = 2014

HTH.

Answer 2

The code has hard-coded ASCII values for the chars '0' and '9', so it skips over anything which does not lie in that range (the first for loop in the four lines of interest to you).

Then while it sees characters in the '0' - '9' range it multiplies its running total by 10 (by shifting it left once to double it, then adding that to itself shifted left three times, which is like multiplying by 8) and adds the current char - the code for '0'.

Answer 3

The line

for(;(c<48 || c>57);c = gc());  

reads the characters which are not in between '0' to '9'.

The line

for(;c>47 && c<58;c = gc())   

reads the characters between '0' to '9' one by one.

The line

{x = (x<<1) + (x<<3) + c - 48;}   

is simply equivalent to

x = 10 * x + c - 48;  

A simplified version of this function can be rewritten as:

#define gc getchar_unlocked
int read_int()
{
    char c = gc();
    while(c<'0' || c>'9')
       c = gc();
    int ret = 0;
    while(c>='0' && c<='9')
    {
        ret = 10 * ret + c - 48;
        c = gc();
    }
    return ret;
}