Menu

递归算法美高梅开户

My code:

问题

求两个整型变量的和,不能使用四则运算,但可以使用位运算。

public class Solution { public int getSum(int a, int b) { if  { return a; } int sum = ; int carry = (a & b); carry = (carry << 1); return getSum(sum, carry); }}

思路

以二进制形式,考虑两个整数相加:

a = 01101001b

b = 11100111b

s =  ????????

一个常见的结论是:

我们在进行二进制加法的时候(类比十进制加法),若无进位,则直接写上结果;若有进位,则写一个进位标志,作为累计,在高位计算时加入。

也就是说,结果是由截断二进制位和及其进位标志相加而得的

思考:两个数的和 == 截断二进制位和+进位和,这种转化分解是否可行?

证明:讨论两个1bit相加出现的全部情况,一共有四种。

  1. 0 + 0 = 0 + 00
  2. 0 + 1 = 1 + 00
  3. 1 + 0 = 1 + 00
  4. 1 + 1 = 0 + 10

等式左边为一位相加,右边为截断结果s和进位c相加,可以看出,等式成立,因此这种转化方式可行

将等式记为:

a + b = s + c

我们来寻求a、b和s、c的关系。

很容易证明:

  • s=a^b,^表示异或,即a、b不同时返回0,相同时返回1。
  • c=(a&b)<<1,&表示与,即a、b都为1时返回1,否则返回0;<<表示二进制左移,<<1即乘以2。

这样,转化关系式就得出了:

a + b = a ^ b + (a & b) << 1

但是,在转化关系求出后,还存在一个问题:既然存在转化关系,就有递归调用(迭代),那递归的出口是什么?

如果可以求出递归出口,那么这个方法就完美了。

这相当于问:

a 和 b 有没有终止条件(或者说极限)?

我们假设a和b都是n位二进制数(补码表示,这样a和b的正负性不影响结果),令c=a+b。

初始时,用二进制表示,a = a[n-1] a[n-2] … a[1] a[0],b =
b[n-1] b[n-2] … b[1] b[0],c = c[n-1] c[n-2] … c[1]
c[0]。

第一次迭代。a=a^b;b=(a&b)<<1。b必为偶数,这样b[0]就是0,又由于a+b=c,故a[0]=c[0]-b[0]=c[0]。

结果为:

a = a[n-1] a[n-2] … a[2] a[1] c[0]

b = b[n-1] b[n-2] … b[2] b[1] 0

第二次迭代。对于a和b最后一位,运算后结果保持不变,所以问题就归结为a[n-1]~a[1]和b[n-1]~b[1]间的迭代。

结果为:

a = a[n-1] a[n-2] … a[2] c[1] c[0]

b = b[n-1] b[n-2] … b[2] 0 0

……

第n次迭代。递推可得:

a = c[n-1] c[n-2] … c[1] c[0]

b = 0 0 … 0 0

所以,a=c,b=0,这就是收敛条件,即递归出口。证毕。

我们还可以得出其他结论:

  1. 迭代次数的上界是n,超过n,立即收敛。
  2. 假如b的二进制表示的前缀0有许多,那么收敛速度将大大增加。
  3. 在迭代过程中,a呈指数增加,b呈指数减少,比率近似于2。
  4. 假如a和b当中有负数,结果也是正确的,因为位运算是纯二进制运算(补码表示)。

自己想复杂了就没继续想,看的答案。

实现

function sum(a,b)
{
    return b?sum(a^b,(a&b)<<1):a;
}

reference:

sum 求出不进位的话应该的结果。

然后 (a & b)
可以求出每一位的进位结果。然后左移一位,把这些进位的数给最终结果加进去。用个递归。

差不多就这么意思。bit manipulation 感觉都是耍耍小聪明,没什么意思。除了
dfs 用 bit map 来剪枝,是挺酷的。

Anyway, Good luck, Richardo! — 09/09/2016

标签:,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图