Bit Manipulation and Mathematical Patterns

Every number in a computer is stored as a row of switches that are either off or on: a bit is a 0 or a 1. Normally you never see this. You write 13 and the machine handles the rest. But sometimes working at the level of the bits themselves is the neatest way to solve a problem. You can pack eight true/false flags into one number. You can find the one unpaired value in a list without a hash map. You can walk through every subset of a set with a single loop.

This article is about those uses. It is deliberately not a collection of magic one-liners to memorise. For every trick you will see why it works, because a trick you cannot explain is a liability in an interview. We also cover a few elementary mathematical tools that show up constantly: GCD, modular arithmetic, fast exponentiation, and primes.

• How integers look in binary, including negative numbers in Java.
• The bitwise operators and shifts, and Java's specific rules about them.
• Reasoned uses: parity, testing and changing bits, powers of two, counting bits, XOR, masks and subsets.
• GCD and LCM, modular arithmetic, fast exponentiation, and the sieve of Eratosthenes.
• Which of these are essential, and which are rare.

In binary, each position is worth a power of two, counting from the right: 1, 2, 4, 8, 16, and so on. So 1101 in binary means 8 + 4 + 0 + 1 = 13.

A Java int has 32 bits. The leftmost bit is the sign bit. Java stores negative numbers in two's complement, where -x is ~x + 1: flip every bit of x, then add one. This has a useful consequence: the same addition hardware works for positive and negative numbers.

Because of that scheme, an int ranges from -2^31 to 2^31 - 1. The range is lopsided, so there is one more negative number than positive: Integer.MIN_VALUE has no positive counterpart. That is why -Integer.MIN_VALUE is still Integer.MIN_VALUE, and Math.abs(Integer.MIN_VALUE) is negative, as we noted in the Java article.

Here is what each operator does. All of them work on every bit position at the same time.

• a & b (AND): each result bit is 1 only if both input bits are 1.
• a | b (OR): each result bit is 1 if at least one input bit is 1.
• a ^ b (XOR, exclusive or): each result bit is 1 if the two input bits differ.
• ~a (NOT): flips every bit.
• a << k (left shift): moves all bits k places to the left, filling with zeros on the right. This multiplies by 2^k (unless bits fall off the left end).
• a >> k (arithmetic right shift): moves bits right, and copies the sign bit into the empty places on the left. For positive numbers this is a division by 2^k (rounded down), and for negative numbers it keeps the number negative.
• a >>> k (logical right shift): moves bits right and fills the left with zeros, so the result is never negative for k > 0.

// File: Main.javapublic class Main {    public static void main(String[] args) {        int a = 12;   // binary 1100        int b = 10;   // binary 1010        System.out.println(Integer.toBinaryString(a) + " " + Integer.toBinaryString(b));        System.out.println((a & b) + " " + (a | b) + " " + (a ^ b) + " " + (~a));        System.out.println((a << 2) + " " + (a >> 2) + " " + (-8 >> 1) + " " + (-8 >>> 1));        System.out.println(Integer.toBinaryString(-5));        System.out.println((1 << 32) + " " + (1 << 31) + " " + (1L << 40));        System.out.println((-Integer.MIN_VALUE == Integer.MIN_VALUE) + " " + Math.abs(Integer.MIN_VALUE));        int n = 6;        System.out.println((n & 1) == 0);     // the parentheses matter, see below    }}

1100 10108 14 6 -1348 3 -4 2147483644111111111111111111111111111110111 -2147483648 1099511627776true -2147483648true

Let us read the output carefully, because each line contains a Java-specific lesson.

• 12 & 10 is 1000 (8): only the leftmost bit is on in both. 12 | 10 is 1110 (14). 12 ^ 10 is 0110 (6): they differ in two positions. ~12 is -13, because ~x = -x - 1 in two's complement.
• 12 << 2 is 48 (twelve times four). 12 >> 2 is 3. -8 >> 1 is -4: the sign is preserved. -8 >>> 1 is 2147483644: the sign bit becomes a zero, so the result is a huge positive number.
• -5 is printed as 32 bits starting with many ones. That is two's complement: ~5 + 1.
• Shift counts wrap. For an int, only the low 5 bits of the shift count are used, so 1 << 32 is 1 << 0, which is 1, not 0. 1 << 31 is Integer.MIN_VALUE, because the 1 lands in the sign bit. To get bit 40, you need a long: 1L << 40. A shift count of k >= 32 on an int is a classic bug.
• Precedence. == binds more tightly than &, so n & 1 == 0 means n & (1 == 0), which does not compile. Always parenthesise: (n & 1) == 0.

Positions are counted from 0 at the right. A mask is a number with the bits you care about switched on. Using 1 << i as a mask for position i:

For parity, the lowest bit is the "ones" place, and since every other place is even, a number is odd exactly when its lowest bit is 1. This works for negative numbers too, in two's complement. (n % 2 == 1 fails for negative odd numbers, because -3 % 2 is -1.)

Subtracting 1 from n flips the lowest set bit to 0 and flips every bit below it to 1. For example, 1100 minus 1 is 1011. When you AND them, everything above the lowest set bit is unchanged and everything from that bit down is cleared:

n         = 1 1 0 0n - 1     = 1 0 1 1n & (n-1) = 1 0 0 0      <- the lowest set bit (the middle 1) has been removed

So n & (n - 1) removes the lowest set bit. Two uses follow.

Power-of-two check. A positive power of two has exactly one set bit. Removing it leaves zero. So n > 0 && (n & (n - 1)) == 0. The n > 0 part matters: for n = 0 the AND is also zero, and for Integer.MIN_VALUE (a single set bit, the sign bit) the AND is zero too, but neither is a positive power of two.

Counting set bits (Brian Kernighan's method). Repeat n &= n - 1 until n is zero, counting the iterations. Each iteration removes one set bit, so the loop runs exactly as many times as there are 1s, rather than 32 times. Dry run for 13 (1101):

Java also provides Integer.bitCount(n), which you should use in real code. Knowing the loop explains how it works.

XOR has three properties that make it special:

1. a ^ a = 0: a value cancels itself.
2. a ^ 0 = a: zero changes nothing.
3. It is commutative and associative, so the order does not matter.

So if you XOR a list in which every value appears twice except one, all the pairs cancel to zero and only the single value remains. This solves "single number" in O(n) time and O(1) space, with no hash set.

The same idea finds a missing number. Take the numbers 0 to n with one missing. XOR together all the numbers 0..n and all the array elements. Every number that is present appears twice and cancels, so only the missing one remains. Unlike the sum formula in the arrays article, there is no overflow to worry about.

A number with n bits can represent a subset of n items: bit i is 1 if item i is in the subset. This is compact (one int holds up to 32 flags), fast, and it lets you enumerate all subsets with a simple loop: every number from 0 to 2^n - 1 is a different subset.

A related use is a visited set for letters. For lowercase letters, 26 bits are enough, so one int can record which letters you have seen: seen |= 1 << (c - 'a'). Testing whether a letter was seen is (seen & (1 << (c - 'a'))) != 0.

The lowest set bit of n is n & -n. In two's complement, -n is ~n + 1, which flips everything above the lowest set bit and keeps that bit and the zeros below it. ANDing with n leaves only that one bit. We will use this idea in the Fenwick tree in Range Queries and Disjoint Set Union.

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static boolean isPowerOfTwo(int n) {        return n > 0 && (n & (n - 1)) == 0;    }    static int countBitsLoop(int n) {        int count = 0;        while (n != 0) {            count += n & 1;            n >>>= 1;                    // unsigned shift, so a negative number also reaches zero        }        return count;    }    static int countBitsKernighan(int n) {        int count = 0;        while (n != 0) {            n &= n - 1;                  // remove the lowest set bit            count++;        }        return count;    }    static int singleNumber(int[] nums) {       // every other value appears exactly twice        int result = 0;        for (int v : nums) {            result ^= v;        }        return result;    }    static int missingNumber(int[] nums) {      // nums holds 0..n with one value missing        int result = nums.length;        for (int i = 0; i < nums.length; i++) {            result ^= i ^ nums[i];        }        return result;    }    static boolean allUniqueLowercase(String s) {        int seen = 0;        for (char c : s.toCharArray()) {            int bit = 1 << (c - 'a');            if ((seen & bit) != 0) {                return false;            }            seen |= bit;        }        return true;    }    static List<String> subsetsByMask(String[] items) {        List<String> result = new ArrayList<>();        for (int mask = 0; mask < (1 << items.length); mask++) {            StringBuilder subset = new StringBuilder("{");            for (int i = 0; i < items.length; i++) {                if ((mask & (1 << i)) != 0) {                    if (subset.length() > 1) {                        subset.append(',');                    }                    subset.append(items[i]);                }            }            result.add(subset.append('}').toString());        }        return result;    }    public static void main(String[] args) {        int[] powers = {1, 2, 3, 16, 0, -8, Integer.MIN_VALUE, 1 << 30};        StringBuilder out = new StringBuilder();        for (int p : powers) {            out.append(isPowerOfTwo(p)).append(' ');        }        System.out.println(out.toString().trim());        int[] numbers = {0, 1, 13, 255, -1, Integer.MIN_VALUE, Integer.MAX_VALUE};        for (int n : numbers) {            int a = countBitsLoop(n);            int b = countBitsKernighan(n);            int c = Integer.bitCount(n);            System.out.println(n + ": " + a + " " + b + " " + c + " " + (a == b && b == c));        }        int n = 10;                                   // binary 1010        System.out.println(((n >> 1) & 1) + " " + (n | (1 << 0)) + " " + (n & ~(1 << 1)) + " " + (n ^ (1 << 3)) + " " + (12 & -12));        System.out.println(singleNumber(new int[] {4, 1, 2, 1, 2}) + " " + singleNumber(new int[] {7}) + " " + missingNumber(new int[] {3, 0, 1}));        System.out.println(allUniqueLowercase("abcde") + " " + allUniqueLowercase("hello") + " " + allUniqueLowercase(""));        System.out.println(subsetsByMask(new String[] {"a", "b", "c"}));    }}

true true false true false false false true0: 0 0 0 true1: 1 1 1 true13: 3 3 3 true255: 8 8 8 true-1: 32 32 32 true-2147483648: 1 1 1 true2147483647: 31 31 31 true1 11 8 2 44 7 2true false true[{}, {a}, {b}, {a,b}, {c}, {a,c}, {b,c}, {a,b,c}]

Notes on the output:

• Integer.MIN_VALUE is not a power of two, even though it has a single set bit, thanks to the n > 0 check.
• All three bit counters agree for every test, including -1 (all 32 bits set) and Integer.MIN_VALUE (just the sign bit). In countBitsLoop, we used >>>= rather than >>=: an arithmetic shift would keep a negative number negative forever and the loop would never end.
• On the next line, for n = 10 (1010): bit 1 is 1; setting bit 0 gives 11; clearing bit 1 gives 8; toggling bit 3 gives 2; and 12 & -12 is 4, the lowest set bit of 1100.
• The subsets appear in the order of the mask: mask 3 (binary 011) is {a,b}, and mask 4 (100) is {c}. There are 2^3 = 8 of them.

Complexity. The power check, bit tests and single-bit operations are O(1). Counting bits is O(number of set bits) with Kernighan's method, or O(32). Single number and missing number are O(n) time and O(1) space. Enumerating all subsets with masks is O(n × 2^n), so it is only suitable for n up to about 20.

The GCD of two numbers is the largest number that divides both. Euclid's insight: the common divisors of a and b are exactly the common divisors of b and a mod b. So replace (a, b) by (b, a % b) until the second number is zero. The first number is then the GCD.

Dry run for gcd(48, 18):

Each step makes the numbers shrink quickly (every two steps, a at least halves), so the time is O(log(min(a, b))).

The LCM (least common multiple) is a / gcd(a, b) × b. Divide first and multiply second: a * b / gcd can overflow even when the answer fits.

Many problems ask for an answer "modulo 1,000,000,007" because the true answer is huge. The rules: (a + b) % m = ((a % m) + (b % m)) % m, and the same for multiplication. Reduce after each operation to keep numbers small. With m around a billion, the product of two reduced values is below about 10^18, which fits in a long, so use long. Also remember that Java's % can return a negative number for a negative left operand, so use Math.floorMod when a non-negative remainder is needed.

Computing base^exp by multiplying exp times is too slow for huge exponents. Binary exponentiation uses the bits of the exponent: x^13 = x^8 × x^4 × x^1 because 13 = 1101 in binary. Keep squaring base, and multiply it into the result whenever the current lowest bit of the exponent is 1. That takes O(log exp) multiplications. This is the iterative cousin of the recursive power from the recursion article.

Dry run for modPow(3, 13, 1000):

So 3^13 mod 1000 = 323. (Indeed 3^13 = 1,594,323.)

Checking one number for primality takes O(sqrt(n)), as in the Java article. To find all primes below n, the sieve of Eratosthenes is far faster. Make a table of n flags, all "might be prime". Walk upward; when you reach a number not yet crossed out, it is prime: cross out all its multiples, starting from its square (smaller multiples were already crossed out by smaller primes). The time is O(n log log n), which is nearly linear, and the space is O(n).

// File: Main.javaimport java.math.BigInteger;public class Main {    static long gcd(long a, long b) {        a = Math.abs(a);        b = Math.abs(b);        while (b != 0) {            long remainder = a % b;            a = b;            b = remainder;        }        return a;    }    static long lcm(long a, long b) {        if (a == 0 || b == 0) {            return 0;        }        return Math.abs(a / gcd(a, b) * b);          // divide first to keep the number small    }    static long modPow(long base, long exp, long mod) {        long result = 1 % mod;        base %= mod;        while (exp > 0) {            if ((exp & 1) == 1) {                result = result * base % mod;            }            base = base * base % mod;            exp >>= 1;        }        return result;    }    // Number of primes strictly less than n.    static int countPrimes(int n) {        boolean[] composite = new boolean[Math.max(n, 0)];        int count = 0;        for (int i = 2; i < n; i++) {            if (!composite[i]) {                count++;                for (long j = (long) i * i; j < n; j += i) {   // long: i * i can overflow int                    composite[(int) j] = true;                }            }        }        return count;    }    static boolean isPrime(int n) {        if (n < 2) {            return false;        }        for (int i = 2; i <= n / i; i++) {            if (n % i == 0) {                return false;            }        }        return true;    }    public static void main(String[] args) {        System.out.println(gcd(48, 18) + " " + gcd(0, 5) + " " + gcd(17, 5) + " " + gcd(-12, 18));        System.out.println(lcm(4, 6) + " " + lcm(0, 3) + " " + lcm(1_000_000_007L, 998_244_353L));        System.out.println(modPow(2, 10, 1000) + " " + modPow(3, 13, 1000) + " " + modPow(5, 0, 7));        long big = modPow(2, 1_000_000, 1_000_000_007L);        long reference = BigInteger.valueOf(2).modPow(BigInteger.valueOf(1_000_000), BigInteger.valueOf(1_000_000_007L)).longValue();        System.out.println("modPow matches BigInteger: " + (big == reference));        System.out.println(countPrimes(0) + " " + countPrimes(2) + " " + countPrimes(10) + " " + countPrimes(100) + " " + countPrimes(1000));        int slowCount = 0;        for (int i = 0; i < 1000; i++) {            if (isPrime(i)) {                slowCount++;            }        }        System.out.println("sieve agrees with trial division below 1000: " + (slowCount == countPrimes(1000)));    }}

6 5 1 612 0 99824435998771047124 323 1modPow matches BigInteger: true0 0 4 25 168sieve agrees with trial division below 1000: true

The two outputs that check one method against another (modPow against BigInteger, and the sieve against trial division) are a good habit: a simple, slow, obviously correct version is a great test for the fast one.

Complexity: gcd is O(log min(a, b)); lcm is the same plus a multiplication; modPow is O(log exp); the sieve is O(n log log n) time and O(n) space.

• Missing parentheses. n & 1 == 0 does not mean what it appears to. Write (n & 1) == 0.
• Shifting an int by 32 or more. The count wraps. Use long and 1L <<.
• >> versus >>> on negative numbers. >> keeps the sign. Use >>> for an unsigned shift.
• Using 1 << k as a mask for a long value when k >= 32. The mask is computed as an int, so it is wrong. Use 1L << k.
• n % 2 == 1 for oddness. It fails for negative numbers. Use (n & 1) != 0.
• Forgetting n > 0 in the power-of-two test.
• Overflow in math. a * b in int, a * b / gcd before dividing, and i * i in a sieve. Use long and divide first.
• Math.abs(Integer.MIN_VALUE) is negative.
• Negative remainders. Use Math.floorMod when you need 0..m-1.
• Over-cleverness. Do not use a bit trick when a plain expression is clearer, unless you are sure everyone reading it will follow.

static boolean isPowerOfTwoBuggy(int n) {    return (n & (n - 1)) == 0;}static int getBitLong(long n, int k) {    return (n & (1 << k)) != 0 ? 1 : 0;}

// File: Main.javapublic class Main {    public static void main(String[] args) {        int x = 22;        System.out.println(Integer.toBinaryString(x) + " " + Integer.toBinaryString(x - 1));        System.out.println((x & (x - 1)) + " " + (x & -x) + " " + (x >> 1) + " " + Integer.bitCount(x));    }}

10110 1010120 2 11 3

// File: Main.javapublic class Main {    static int hammingDistance(int x, int y) {        return Integer.bitCount(x ^ y);    }    public static void main(String[] args) {        System.out.println(hammingDistance(1, 4));        System.out.println(hammingDistance(3, 1));        System.out.println(hammingDistance(7, 7));        System.out.println(hammingDistance(0, -1));        System.out.println(hammingDistance(Integer.MIN_VALUE, Integer.MAX_VALUE));    }}

2103232

// File: Main.javaimport java.util.Arrays;public class Main {    static int[] countBits(int n) {        int[] bits = new int[n + 1];        for (int i = 1; i <= n; i++) {            bits[i] = bits[i >> 1] + (i & 1);        }        return bits;    }    public static void main(String[] args) {        System.out.println(Arrays.toString(countBits(5)));        System.out.println(Arrays.toString(countBits(0)));        int[] big = countBits(1000);        boolean ok = true;        for (int i = 0; i <= 1000; i++) {            ok &= big[i] == Integer.bitCount(i);        }        System.out.println("matches Integer.bitCount up to 1000: " + ok);    }}

[0, 1, 1, 2, 1, 2][0]matches Integer.bitCount up to 1000: true

// File: Main.javapublic class Main {    static boolean isPowerOfTwoBuggy(int n) {        return (n & (n - 1)) == 0;    }    static boolean isPowerOfTwo(int n) {        return n > 0 && (n & (n - 1)) == 0;    }    static int getBitLongBuggy(long n, int k) {        return (n & (1 << k)) != 0 ? 1 : 0;    }    static int getBitLong(long n, int k) {        return (n & (1L << k)) != 0 ? 1 : 0;    }    public static void main(String[] args) {        System.out.println(isPowerOfTwoBuggy(0) + " " + isPowerOfTwo(0));        System.out.println(isPowerOfTwoBuggy(Integer.MIN_VALUE) + " " + isPowerOfTwo(Integer.MIN_VALUE));        long value = 1L << 40;        System.out.println(getBitLongBuggy(value, 40) + " " + getBitLong(value, 40));    }}

true falsetrue false0 1

// File: Main.javapublic class Main {    static int[] twoSingles(int[] nums) {        int x = 0;        for (int v : nums) {            x ^= v;                       // x = a ^ b        }        int lowBit = x & -x;              // a bit where a and b differ        int a = 0;        int b = 0;        for (int v : nums) {            if ((v & lowBit) != 0) {                a ^= v;            } else {                b ^= v;            }        }        return new int[] {Math.min(a, b), Math.max(a, b)};    }    public static void main(String[] args) {        int[] r1 = twoSingles(new int[] {1, 2, 1, 3, 2, 5});        int[] r2 = twoSingles(new int[] {-1, 0});        int[] r3 = twoSingles(new int[] {Integer.MIN_VALUE, 7, 3, 7});        System.out.println(r1[0] + " " + r1[1]);        System.out.println(r2[0] + " " + r2[1]);        System.out.println(r3[0] + " " + r3[1]);    }}

3 5-1 0-2147483648 3

• Next: Graphs: Representations, BFS, and DFS starts the advanced module with one of the most important structures of all.
• Later: n & -n returns in the Fenwick tree in Range Queries and Disjoint Set Union, and subset masks are a stepping stone to some dynamic programming problems.
• Practice habit: whenever you use a bit trick, write a one-line comment that says what the bits mean ("lowest set bit", "letter seen"). If you cannot write that comment, use plain arithmetic instead.