
问题
不使用运算符 + 和 – ,计算两整数 a 、b 之和。
输入: a = 1, b = 2
输出: 3
输入: a = -2, b = 3
输出: 1
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Given a = 1 and b = 2, return 3.
Credits:Special thanks to @fujiaozhu for adding this problem and creating all test cases.
示例
public class Program { public static void Main(string[] args) { var a = 16; var b = 13; var res = GetSum(a, b); Console.WriteLine(res); a = 168; b = 136; res = GetSum2(a, b); Console.WriteLine(res); Console.ReadKey(); } public static int GetSum(int a, int b) { //按位取异或 int result = a ^ b; //判断是否需要进位 int forward = (a & b) << 1; if(forward != 0) { //如有进位,则将二进制数左移一位,进行递归 return GetSum(result, forward); } return result; } public static int GetSum2(int a, int b) { while(b != 0) { int carry = a & b; a = a ^ b; b = carry << 1; } return a; } }
以上给出2种算法实现,以下是这个案例的输出结果:
True False
分析:
显而易见,IsPowerOfTwo 的时间复杂度为: ,IsPowerOfTwo2 的时间复杂度为:
。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4060。