【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“125.Jerry的异或运算”的解法探究。先来看一下题目内容：
题目详情
等级：困难
知识点：DP、数学
查看题目：125.Jerry的异或运算
Jerry最近在研究异或运算，异或也叫半加运算，其运算法则相当于不带进位的二进制加法。
Jerry给你一个数字N，他想知道在0到N之间有多少对数字(a,b)满足u+v=a, u⊕v = b,⊕ 表示按位异或，由于答案将会非常大，请将结果对1e9+7取模。
输入一个整数 N (0<=N<1e18)
输出整数对(a,b)的数目，结果模1e9+7
示例1
输入：
3
输出：
5
解题方法：
由于 u+v=a,u⊕v = b,根据异或的性质我们可以知道：u+v = ((u&v)<<1) + (u⊕v)，所以u+v >=u⊕v，那么只要u+v<=n, u⊕v也必定小于等于n。于是这道题就转化成了对于 u+v<=n ,求(u,v)的对数。
定义dp[n]表示 u+v<=n ,(u,v)的对数，当n=0的时候dp[0] = 1，n=1时，dp[1] = 2。他们的(u,v)分别是{(0,0)}和{(0,0),(1,0)}。
dp[n]再往下递推的时候，要考虑u+v<=n时 二进制是如何由小到大转化过来的。
从二进制上来看u和v，两者的末位只有0或1，那么二者的末位和有0,1,2三种情况。
设u+v=x，令u = u1*2+u0，v = v1 *2+v0，u0+v0即为二者的末位和，又有x<=n，故(u1+v1)*2+u0+v0<=n,所以u1+u2<=(n-u0-v0)/2。
由u1+u2<=(n-u0-v0)/2到 (u1+v1)*2+u0+v0<=n可以推出来递推式：dp[n] = dp[n/2]+dp[(n-1)/2]+dp[(n-2)/2]。
看完之后是不是有了答题思路了呢，快来练练手吧：125.Jerry的异或运算
在线编程周赛、月赛火热进行中，更有限时答题活动，定制卫衣、双肩背包、机械键盘等多重好礼等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！
