#include <iostream>
#include <map>
typedef unsigned long long ull;
using namespace std;
map<ull, ull> save;
ull F(ull n){
    if(save.count(n) != 0) return save[n];
    else if(n % 2 == 0) return F(n - 1) + 2;
    else if(n == 1) return 0;
    else return F(n - 1) + F(n - 2) - 1;
}
int main() {
    ull n;
    ull result;
    cout << "Enter n: ";
    cin >> n;
    for(ull i = 1; i <= n ; i ++){
        save.insert(pair<ull, ull>(i, F(i)));
    } 
    cout << "Result is " << F(n);
    return 0;
}

n&(n-1)用到了按位与运算符，这一算法的用途是判断此数字二进制是否只含有唯一一个1。当满足该条件时，此式值为0。

按位与正如字面意思，按二进制的每位进行与运算。

例如，n = 1000(Bin)的情况下，

  1000 // n
& 0111 // n - 1
------
  0000 // n & ( n - 1 )

此时n&(n-1)=0。

若n = 1100(Bin)，

  1100 // n
& 1011 // n - 1
------
  1000 // n & ( n - 1 )

此时n&(n-1)≠0。