[Hard] interview questions #1

[rygh4775]

[tgi01054]

접근

759 + 674 = 1433 = 1110 + 323
323는 올림수 생략 계산
1110는 올림수 계산  

2진법으로 생각하면

올림수 생략 계산 => XOR
올림수 계산  => AND

Recursive version

    public static int add(int a, int b) {
        if (b == 0) return a;
        int sum = a ^ b; // add without carrying
        int carry = (a & b) << 1; // carry, but don�t add
        return add(sum, carry); // recurse
    }

Iterative version

    public static int add(int a, int b) {
        while (b != 0) {
            int sum = a ^ b; // add without carrying
            int carry = (a & b) << 1; // carry, but don't add           
            a = sum;
            b = carry;
        }
        return a;
    }