Bitwise Arithmetic

May 2026 · 26 min read

Bitwise arithmetic asks: what do addition, subtraction, multiplication, division, and averaging look like when you only reason about bits? You should know these patterns for interviews, but also understand their edge cases well enough not to use them blindly in production or contest code.

Add Without +

XOR gives the sum without carries. AND finds positions that generate carries. Shift the carries left and repeat until there are no carries left.

int add(int a, int b) {
    while (b != 0) {
        unsigned carry = (unsigned)(a & b) << 1;
        a = a ^ b;
        b = (int)carry;
    }
    return a;
}

For interview explanation: a ^ b is "different bits add to 1", while a & b is "two 1s create a carry".

Subtraction with Two's Complement

Subtraction is addition of the negated value. In two's complement, -b = ~b + 1.

int subtract(int a, int b) {
    return add(a, add(~b, 1));
}

Conceptually useful, but normal a - b is clearer unless the problem forbids arithmetic operators.

Multiply with Shifts

Binary multiplication is repeated addition of shifted copies. If bit i of b is set, add a << i.

long long multiply(long long a, long long b) {
    long long ans = 0;
    while (b > 0) {
        if (b & 1LL) ans += a;
        a <<= 1;
        b >>= 1;
    }
    return ans;
}

This is the same idea as binary exponentiation. The multiplier's bits decide which shifted values contribute.

Divide with Shifts

Division by repeated subtraction is too slow. Instead, subtract the largest shifted divisor that fits, from high bit to low bit.

long long divide_positive(long long a, long long b) {
    long long q = 0;
    for (int k = 62; k >= 0; --k) {
        if ((b << k) >= 0 && (b << k) <= a) {
            a -= b << k;
            q |= 1LL << k;
        }
    }
    return q;
}

Average Without Overflow

(a + b) / 2 can overflow. There are two classic fixes.

// Works when a <= b and subtraction cannot overflow.
int mid = a + (b - a) / 2;

// Bit identity: common bits plus half of differing bits.
int avg = (a & b) + ((a ^ b) >> 1);

For unsigned values, the bit identity is clean. For signed values, understand how right shift of negatives behaves before relying on it.

Power-of-Two Arithmetic

x << k        // x * 2^k, if no overflow
x >> k        // floor(x / 2^k) for unsigned
x & ((1<<k)-1) // x mod 2^k, for non-negative x
(x + m - 1) & ~(m - 1) // round up to multiple of power-of-two m

Pitfalls

• Bitwise arithmetic is usually for learning and special constraints, not for replacing normal arithmetic everywhere.
• Signed overflow remains undefined in C++; use wider or unsigned types when modeling raw bits.
• Division with shifts needs careful sign and overflow handling.
• Right shift and division differ for negative odd numbers on common machines.

Practice Problems

• LeetCode 371 - Sum of Two Integers carry canonical add-without-plus problem.
• LeetCode 29 - Divide Two Integers shift division handle signs and INT_MIN.
• LeetCode 50 - Pow(x, n) binary decomposition same bit-by-bit idea as multiplication.
• LeetCode 69 - Sqrt(x) overflow-safe mid binary search with safe arithmetic.