Bitwise Arithmetic (Add/Sub/Mul/Div)

Implement arithmetic operations using bitwise operators

#resource / algorithm #type / concept #status / growing #algo / bitwise

[!info] related notes 算法面试题型 MOC 异或与位运算技巧

Bitwise Arithmetic (Add/Sub/Mul/Div)

These are common interview exercises.

Add / Neg / Sub

static int add(int a, int b) {
    int sum = a;
    while (b != 0) {
        sum = a ^ b;          // no-carry sum
        b = (a & b) << 1;     // carry
        a = sum;
    }
    return sum;
}

static int neg(int n) {
    return add(~n, 1);
}

static int minus(int a, int b) {
    return add(a, neg(b));
}

Multiply

static int multiply(int a, int b) {
    int ans = 0;
    while (b != 0) {
        if ((b & 1) != 0) ans = add(ans, a);
        a <<= 1;
        b >>>= 1;
    }
    return ans;
}

Divide (basic version)

// assumes b != 0 and does not fully handle Integer.MIN_VALUE corner cases
static int div(int a, int b) {
    int x = a < 0 ? neg(a) : a;
    int y = b < 0 ? neg(b) : b;
    int ans = 0;
    for (int i = 30; i >= 0; i = minus(i, 1)) {
        if ((x >> i) >= y) {
            ans |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return (a < 0) ^ (b < 0) ? neg(ans) : ans;
}

Notes

Properly handling Integer.MIN_VALUE requires special-case logic because abs(Integer.MIN_VALUE) overflows.

异或与位运算技巧