Разрешающая способность параметров в вариационной функции

Question

Я пытался понять, что делает следующий код.Особенно функция reverse_binary_value().

Я читал о функциях с переменным числом, но я не могу понять, почему при возврате значения выполняется сдвиг влево 1.

Я получил этот кодhackerank.Вопрос в следующем:

Создайте шаблонную функцию с именем reversed_binary_value.Он должен принимать произвольное количество значений bool в качестве параметров шаблона.Эти логические значения представляют двоичные цифры в обратном порядке.Ваша функция должна возвращать целое число, соответствующее двоичному значению цифр, представленных логическими значениями.Например: reversed_binary_value <0,0,1> () должно вернуть 4.

Формат ввода

Первая строка содержит целое число, количество тестовых случаев.Каждая из последующих строк содержит контрольный пример.Тестовый случай описывается как целые числа, разделенные пробелами, и, соответственно.

x - это значение для сравнения.

y представляет диапазон для сравнения: от 64 * y до 64 * y +63

Формат вывода

Каждая строка вывода содержит 64 двоичных символа.(т. е. 0 и 1).Каждый символ представляет одно значение в диапазоне.Первый символ соответствует первому значению в диапазоне.Последний символ соответствует последнему значению в диапазоне.Символ равен 1, если значение в диапазоне соответствует X;в противном случае символ равен 0.

Пример ввода

2 65 1 10 0

Пример вывода

01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001030 *

#include <iostream>

using namespace std;

template <bool a> int reversed_binary_value() { return a; }

template <bool a, bool b, bool... d> int reversed_binary_value() {
    return (reversed_binary_value<b, d...>() << 1) + a;
}

template <int n, bool...digits>
struct CheckValues {
    static void check(int x, int y)
    {
        CheckValues<n-1, 0, digits...>::check(x, y);
        CheckValues<n-1, 1, digits...>::check(x, y);
    }
};

template <bool...digits>
struct CheckValues<0, digits...> {
    static void check(int x, int y)
    {
        int z = reversed_binary_value<digits...>();
        std::cout << (z+64*y==x);
    }
};

int main()
{
    int t; 
    std::cin >> t;

    for (int i=0; i!=t; ++i) {
        int x, y;
        cin >> x >> y;
        CheckValues<6>::check(x, y);
        cout << "\n";
    }
}

Answer 1

Я читал о функциях с переменным числом, но я не могу понять, почему при возврате значения выполняется сдвиг влево 1.

template <bool a, bool b, bool... d> int reversed_binary_value() {
  return (reversed_binary_value<b, d...>() << 1) + a;
}

Представьте, что у вас есть этопример <0,0,1>.Это соответствует 100, что составляет 4 в десятичном виде.Эта функция является рекурсивным шаблоном, на первой итерации a представляет младший значащий бит, на второй итерации - следующий значащий бит.Чтобы правильно сформировать значение, результат reversed_binary_value<b, d...>() должен быть сдвинут на один бит влево на каждой итерации.

По итерации:

1. a = 0, вызывая reversed_binary_value<0,1>()
2. a = 0, вызывая reversed_binary_value<1>()

reversed_binary_value<1>() соответствует невариантному template <bool a> int reversed_binary_value() { return a; }, поскольку это соответствует списку параметров шаблона.

a = 1, возврат 1:

Возвращение из рекурсии:

return 1 << 1 + 0 равно двоичному 10, то есть 2 в десятичном виде. return 10 << 1 + 0 равно двоичному 100, то есть 4 в десятичном виде.

Может быть любопытно посмотреть, как это работает во время выполнения теста:

template <bool a> int reversed_binary_value() {
  cerr << "a = " << a << ";\n";
  return a;
}

template <bool a, bool b, bool... d> int reversed_binary_value() {
  cerr << "a = " << a << " b = " << b << " d = ";
  (cerr << ... << d);  // C++14
  cerr <<";\n";
  return (reversed_binary_value<b, d...>() << 1) + a;
}

Вывод на stderr (поток # 2), обратите внимание, что cerr и cout могут быть не синхронизированы, поэтому вывод на cout может быть не в порядке.

a = 0 b = 0 d = 0000;
a = 0 b = 0 d = 000;
a = 0 b = 0 d = 00;
a = 0 b = 0 d = 0;
a = 0 b = 0 d = ;
a = 0;
a = 1 b = 0 d = 0000;
a = 0 b = 0 d = 000;
a = 0 b = 0 d = 00;
a = 0 b = 0 d = 0;
a = 0 b = 0 d = ;
a = 0;
a = 0 b = 1 d = 0000;
a = 1 b = 0 d = 000;
a = 0 b = 0 d = 00;
a = 0 b = 0 d = 0;
a = 0 b = 0 d = ;
a = 0;
...