readyforhires
Sign up free

Math & Bits 101

Intermediate · 4 chapters · 8 min read · Use XOR, powers of two and number tricks to solve problems in a few lines.

Practise this in the app All guides

When maths and bits are the answer

Numbers have structure

Some interview problems look like they need a data structure but really need a small mathematical observation: XOR cancels pairs, a power can be computed by repeated squaring, a line through two points has a slope you can store as a reduced fraction. Recognising these saves you from long, fragile code.

Binary in one minute

Every integer is a sum of powers of two. 13 is 1101 in binary: 8 + 4 + 1. The bit operators work on these digits directly:

Signals in a problem statement

Key XOR facts

x ^ x == 0, x ^ 0 == x, and XOR is commutative and associative. So XOR-ing a whole list cancels every value that appears an even number of times, leaving the odd one out. That one fact solves a surprising number of questions in O(n) time and O(1) space.

Core patterns with templates

1. XOR cancels pairs

def single_number(nums):
    x = 0
    for v in nums:
        x ^= v
    return x

2. Bit tricks you should know

def is_power_of_two(n):
    return n > 0 and n & (n - 1) == 0

def count_ones(n):
    c = 0
    while n:
        n &= n - 1   # drop the lowest set bit
        c += 1
    return c

3. Reuse smaller answers (bits DP)

i >> 1 is i without its last bit, so the count of ones in i is the count for i >> 1 plus the last bit.

def count_bits(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)
    return ans

4. Fast power by squaring

def power(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

Example: x^13 with 13 = 1101₂ multiplies x^8 · x^4 · x^1, needing about four squarings instead of twelve multiplications.

5. Exact slopes with GCD

For "maximum points on a line", fix one point and count the others by the slope to it. Store the slope as a reduced pair, never as a float.

from math import gcd
from collections import Counter

def max_points(points):
    best = 0
    for i, (x1, y1) in enumerate(points):
        slopes = Counter()
        for x2, y2 in points[i + 1:]:
            dx, dy = x2 - x1, y2 - y1
            g = gcd(dx, dy)
            dx, dy = dx // g, dy // g
            if dx < 0 or (dx == 0 and dy < 0):
                dx, dy = -dx, -dy
            slopes[(dx, dy)] += 1
        best = max(best, 1 + max(slopes.values(), default=0))
    return best

The sign normalisation makes (1, -2) and (-1, 2) the same slope.

Complexity, mistakes and edge cases

Complexity

TaskTimeSpace
XOR of a listO(n)O(1)
Count bits of one numberO(number of set bits)O(1)
Bits for 0..nO(n)O(n) output
Fast powerO(log n)O(1)
gcd(a, b)O(log min(a, b))O(1)
Points on a lineO(n²)O(n)

Common mistakes

Edge cases

n = 0 and n = 1 for bit counts, x = 0 with a negative exponent, a single point or two points (always on one line), vertical and horizontal lines, all points identical, and the minimum and maximum 32-bit integers.

Useful identities

x & -x isolates the lowest set bit. x | (1 << k) sets bit k; x & ~(1 << k) clears it; (x >> k) & 1 reads it. These four lines cover most bitmask code you will need.

Variations and practise

How interviewers twist it

How to explain it

Name the property you rely on: "XOR cancels equal pairs, so only the single number survives", or "squaring halves the exponent each step". A short, precise sentence makes even a three-line solution feel well understood.

Practise

The problems below cover the XOR trick, counting bits with a small recurrence, fast exponentiation with negative powers, and counting points on a line with exact slopes. Try each one first with the obvious approach, then rewrite it using the property from this card.

Practise

Easy

Medium

Hard

Practise this in the app All guides