работа более быстрого метода ввода / вывода
Я изучал более быстрые методы ввода / вывода для задач программирования,
Я узнал этот метод использования getchar_unlocked() (хоть и рискованно но все же).
Я немного осмотрелся, но не смог понять, как он сканировал целочисленное значение
или, другими словами, что означают 4 строки и как они работают в scanint() функция
определено ниже
#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;
}
Решение
ASCII значение '0' 48, и каждая последующая цифра идет еще одна. то есть '1'-> 49, '2'-> 50 … и так далее.
Побочным эффектом этого является то, что если вы берете символьную цифру, что означает что-то между '0' а также '9'и вычесть значение ASCII '0' из него вы получите целочисленное значение этой цифры.
Так в линии x = (x<<1) + (x<<3) + c - 48;, c-48 part преобразует цифровой символ (ASCII-кодированный символ) в число от 0 до 9, которое относится к этому символу.
(x<<1)+(x<<3) такой же как x * 10, (Для получения дополнительной информации, оформить заказ http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add а также Как я могу умножить и разделить, используя только сдвиг и добавление битов? ) на самом деле эта часть кода излишне запутана. Компилятор может оптимизировать умножение многими различными способами, чтобы сделать его максимально быстрым, поэтому нам не нужно вручную реализовывать сдвиг битов. Это делает для интересной загадки уровня колледжа все же.
for(;(c<48 || c>57);c = gc()); Этот цикл будет игнорировать все символы, пока не получит тот, который попадает в '0' в '9' спектр. Поэтому, если пользователь начал с ввода пробела или любого другого символа, он будет просто проигнорирован.
Ко времени попадания кода for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;} строка, переменная c уже инициализирован первой цифрой, набранной пользователем. Этот цикл оставляет инициализацию пустой, поэтому поток управления погрузится прямо в цикл и начнет вычислять число при вводе каждого символа.
Цикл будет продолжаться до тех пор, пока пользователь продолжает вводить цифры, как только пользователь вводит что-то отличное от цифры, цикл завершается, завершая набор номера.
Пока пользователь не наберет цифры, строка x = (x<<1) + (x<<3) + c - 48; будет исполняться снова и снова, с каждым разом c будучи персонажем только что набрал. А также x умножится на 10 и добавьте новую цифру в.
Допустим, пользователь вводит 2014. Вот как значения в c а также x будет прогрессировать
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
НТН.
Другие решения
Код имеет жестко запрограммированные значения ASCII для символов '0' а также '9'поэтому он пропускает все, что не лежит в этом диапазоне (первый цикл for в четырех интересующих вас строках).
Затем, пока он видит символы в '0' — '9' в диапазоне он умножает свой текущий итог на 10 (сдвигая его влево, чтобы удвоить, затем добавляя его к себе, смещенном влево три раза, что аналогично умножению на 8), и добавляет текущий символ — код для '0',
Линия
for(;(c<48 || c>57);c = gc());
читает символы, которые не находятся между '0' в '9',
Линия
for(;c>47 && c<58;c = gc())
читает символы между '0' в '9' по одному.
Линия
{x = (x<<1) + (x<<3) + c - 48;}
просто эквивалентно
x = 10 * x + c - 48;
Упрощенная версия этой функции может быть переписана как:
#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;
}