I was asked a question about calculate the Fibonacci number at the compile time not at run time in C++.

Initially, I have no idea about how to solve this problem, how to make the calculation happen in the compile time? Then the key solution is: Using Template.

Template metaprogramming can make compile-time class generation, and also can perform polymorphism in a static, which is well-known as the Curiously Recurring Template Pattern (CRTP).

So the solution is listed as following:

 

template<int N>
class Fibonacci {
public:
    enum { value = Fibonacci<N-1>::value + Fibonacci<N-2>::value };
};

template<>
class Fibonacci<1> {
public:
    enum { value = 1 };
};

template<>
class Fibonacci<0> {
public:
    enum { value = 0 };
};

int main() {
    int i =  Fibonacci<6>::value;
    return i;
}

Compile it to assembly “g++ -O2 -S Fibonacci_template.cpp

 

_main:                                  ## @main
	.cfi_startproc
## BB#0:
	pushq	%rbp
Ltmp0:
	.cfi_def_cfa_offset 16
Ltmp1:
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
Ltmp2:
	.cfi_def_cfa_register %rbp
	movl	$8, %eax
	popq	%rbp
	retq
	.cfi_endproc

 

You can find: The assembly output (Line 12) is compiled into the exact number of Fibonacci(6) is to be 8.