#上海大学程序设计联赛 F_1+2=3?(位运算)

最近遇到挺多位运算的题目，感觉有些题还是要做下总结，来记住位运算神奇的特性
##题目：
小Y在研究数字的时候，发现了一个神奇的等式方程，他屈指算了一下有很多正整数x满足这个等式__${x}\bigoplus{2x}=3x$，比如1和2，现在问题来了，他想知道从小到大第N个满足这个等式的正整数，请你用程序帮他计算一下。
($\bigoplus$表示按位异或运算)
##输出描述：
第一行是一个正整数$T(T\leq100)$，表示查询次数。
接着有T行，每行有一个正整数$N(N\leq{10^{12}})$__，表示小Y的查询。
##输出描述：
对于每一个查询N，输出第N个满足题中等式的正整数，并换行。
###样例1：
输入

4
1
2
3
10

输出

1
2
4
18

##题解：
首先要观察一下题目的公式__${x}\bigoplus{2x}=3x$__，我们可以作出这样的翻译:
一个二进制数$x$加上这个数左移一位$2x$等于这两个数的异或和
举个例子:
$x=9$    转化为二进制是$00001001$
$2x=18$转化为二进制是$00010010$
$3x=27$转化为二进制是$00011011$
我们很容易就可以发现等式成立只要$x$的二进制表示里面的$1$是不连续的！
然后我们先想不关注题目想一个简单的问题：
$1$到$2^n$里面有多少个满足这样数?
我们先简单列一下表观察一下
00001   f[0]=1
00010   f[1]=2
00100   f[2]=3
00101
01000   f[3]=5
01001
01010
10000   f[4]=8

我们可以发现 f[i]=f[i-1]+f[i-2] ，不过为什么呢？
实际上公式应该是 f[i]=f[i-1]+f[i-2]-1+1，我们可以看一下表：
在f[4]中我们可以分成两部分：
第一部分是：f[3]
第二部分则是：
01001
01010
10000
而第二部分也可以看成：
01000+00001=01001
01000+00010=01010
01000+00100=01100$\rightarrow^{看作}$01000+01000=10000 而第三行之所以能这么看是因为01100是不满足条件的需要进一位，也就是说，要把00100换成01000。这也就是为什么有一个$+1-1$
因此，现在我们可以通过递推式知道了$1$到$2^n$里面有多少个满足这样数。
回到题目来看，我们现在知道某个满足条件数__K__是第__N__个满足条件的数，然后我们知道每__f[i]名在二进制第__i+1__位就有一个1，ans__就加上$2^{i}$，然后我们通过不断减__f[i](比N小才减)，就可以反推出__K。
##代码：

#include<bits/stdc++.h>
using namespace std;
long long f[70];
long long g[70];
int main()
{
	ios::sync_with_stdio(false);
	int T,i,j,k;
	long long n;
	long long ans;
	f[1]=1;f[2]=2;
	g[1]=1;g[2]=2;
	for(i=3;i<=60;i++)
	{
		g[i]=g[i-1]*2;
		f[i]=f[i-1]+f[i-2];
	}
	cin>>T;
	while(T--)
	{
		cin>>n;
		ans=0;
		for(i=60;i>=1;i--)
		{
			if(n>=f[i])
			{
				ans+=g[i];
				n-=f[i];
			}
		}
		cout<<ans<<endl;
	}
}

Q.E.D.