how does this algorithm work ???

help
, ,
1

#include
#include
#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;

}

What does the function gc do ?? nd hows is this code taking input of number for more than one digit??

2

gc is basically the macro defined in the above code which stands for getchar_unlocked(). You knwo about getchar()? If not, then getchar(), returns the next character from the input stream. getchar_unlocked() is the very same as getchar(), the only difference is it’s not thread safe. Well, if you’re now confused about what thread safe means, read on further. Whenever we read characters from the input stream, the stream is locked. Imagine two different processes reading the same data and modifying it. This can create synchronisation problem. Imagine you are you and your father are withdrawing money from the same bank account at same time. You drew Rs. 1000 and your father did Rs. 5k. You being unaware, will run into shock seeing the balance left in your account. :smiley: The change may be seen by one but not by the other. This concept will be more clear if you know about the very important concept of Operating systems, [mutual exclusion][1]. (If you still need some more explanation on this, let me know in comments, I’ll be happy to help).

Returning back, getchar_unlocked() doesnot check for locks on the input stream. In the usual getchar(), if some thread is already executing in the critical section(You should know this if you went across the above link) or has locked the input stream, the other threads waiting for the same will wait till the lock count becomes zero. So, significant time is spent doing this. Thus, we use getchar_unlocked() which doesnot care about the locks on stream and hence reduce the overhead involved in checking and waiting for locks. Thus, it is faster.

Speed:  getchar_unlocked()> getchar()>scanf()

If anything of the above is not clear(specially mutual exclusion and semaphore part, feel free to ask).

To answer how it is accepting input of more than one digit: The function ignores those input characters whose values(Ascii) are not in the range 47,58(irrelevant they are). If it lies, the value is assigned to the variable x. Lets say we are reading 1234, the very first time, x=1, then 2 is read, the number formed is:
(1X(10)+2)=12, then 3 is read, the number now is : (12)X(10)+3=123, then 4 is read, number now is (123)X(10)+4=1234. This way it is read,:

while(c<'0' || c>'9')
{
  c=gc();
  if(c==EOF) return;
}
int n=0;
while(c>='0' && c<='9')
{
 step1:  n=n*10 + c-'0'; // form the number
         c=gc(); // read next character
}

In the above code, the step 1 can also be written as :

n=n*10 + (c-'0');
n=n*(8+2) + (c-'0');
n= n*8 + n*2 + (c-'0')
n= n*(2^3)+ (n*(2^1)) + (c-'0');
n= (n<<3) + (n<<1) + (c-'0');

This speeds up the task as compared to multiplication.

Hope it clears… :slight_smile:
[1]: http://www.quora.com/Semaphore-vs-mutex-vs-monitor-What-are-the-differences

2 Likes
3

well,there is no need to get involved(as the answer is here) but still i would say no one can explain this better way.I am writing this answer just because to thank @damn_me you are such a great contributor to the community.You helped me and many other.We would love to see your answers in future.Okay,if anybody wants to downvote than i will not mind :slight_smile: :slight_smile:

4

@doodle90 You may try explaining, pen is mightier :stuck_out_tongue: Thanks anyway, happy to help :slight_smile: