时间复杂度:O(1)
空间复杂度:O(1)
EG: 6: 0110 3: 0011 num2 = 3 = 0011 进位: c = 0110 0011 & -------- 0010 << ------------ 0100 = 4 不进位: num1 = 0110 0011 ^ ---------------- 0101 = 5 num2 = c = 0100 = 4 ------------------------------- 进位: c = 0101 0100 & -------- 0100 << ------------ 1000 = 8 num1 = 0101 0100 ^ ---------------- 0001 = 1 num2 = c = 1000 = 8 ------------------------------- c = 0001 1000 & -------- 0000 << ------------ 0000 = 8 num1 = 0001 1000 ^ ---------------- 1001 = 9 num2 = c = 0000 = 0
无进位和运算就是按位异或结果,
进位就是与运算结果但是需要左移一位,因为进位影响下一位的运算。
所以s = a + b,其实就是无进位和+进位的结果。
public class Solution { public int Add(int num1,int num2) { while(num2 != 0) { int c = ((num1 & num2)) << 1; num1 ^= num2; num2 = c; } return num1; } }