本文共 611 字,大约阅读时间需要 2 分钟。
位运算
写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
设两数字的二进制形式 a,b ,其求和 s = a + b ,a(i) 代表 a 的二进制第 i 位,则分为以下四种情况:
a(i) | b(i) | 无进位 | 进位 |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
观察发现,无进位和运算就是按位异或结果,进位就是与运算结果但是需要左移一位,因为进位影响下一位的运算。所以 s = a + b,其实就是无进位和 + 进位的结果。
算法设计:
public class Solution { public int Add(int num1, int num2) { int noCarrySum = num1 ^ num2; int carry = (num1 & num2) << 1; return carry == 0 ? noCarrySum : Add(noCarrySum, carry); }}
转载地址:http://edjvb.baihongyu.com/