Resolution of parameters in variadic function

Question

I was trying to understand what the following code is doing. Especially function reverse_binary_value().

I have read about variadic functions, but I can't understand why, while returning a value, the left shift 1 is done.

I got these code on hackerank. The question is something like this

Create a template function named reversed_binary_value. It must take an arbitrary number of bool values as template parameters. These booleans represent binary digits in reverse order. Your function must return an integer corresponding to the binary value of the digits represented by the booleans. For example: reversed_binary_value<0,0,1>() should return 4.

Input Format

The first line contains an integer, the number of test cases. Each of the subsequent lines contains a test case. A test case is described as space-separated integers, and, respectively.

x is the value to compare against.

y represents the range to compare: 64*y to 64*y+63

Output format

Each line of output contains 64 binary characters. (i.e., 0's and 1's). Each character represents one value in the range. The first character corresponds to the first value in the range. The last character corresponds to the last value in the range. The character is 1 if the value in the range matches X; otherwise, the character is 0.

Sample input

2 65 1 10 0

Sample output

0100000000000000000000000000000000000000000000000000000000000000 0000000000100000000000000000000000000000000000000000000000000000

Code

#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

I have read about variadic functions, but I can't understand why, while returning a value, the left shift 1 is done.

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

Imagine that you have that example <0,0,1>. It corresponds to 100, which is 4 in decimal. This function is a recursive template, on first iteration a represents least significant bit, on second iteration it represent next significant bit. To form value properly result of reversed_binary_value<b, d...>() have to be shifted by one bit to left during each iteration.

By iteration:

1. a = 0 , calling reversed_binary_value<0,1>()
2. a = 0 , calling reversed_binary_value<1>()

reversed_binary_value<1>() corresponds to non-variadic template <bool a> int reversed_binary_value() { return a; } because that matches template parameter list.

3. a = 1 , return 1:

Returning from recursion:

2. return 1 << 1 + 0 equals to binary 10, i.e. 2 in decimal.
3. return 10 << 1 + 0 equals to binary 100, i.e. 4 in decimal.

It might be curious to see how it works during test run:

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;
}

Output on stderr (stream #2), note that cerr and cout may be not synchronized, so output to cout can be out of order.

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;
...