⌘K

Bitmasks and Bitwise Arithmetic

EditorialUpdated Nov 9, 2026

Dividing by subtracting

Divide Two Integers asks for a quotient without *, / or %. The first idea: subtract the divisor until it no longer fits, counting the times. On the problem's largest case, 2,147,483,647 divided by 1, in every language the judge runs:

import time

start = time.perf_counter()
a, b, q = 2147483647, 1, 0            # subtract b until it no longer fits; q counts the times
while a >= b:
    a -= b
    q += 1
print(f"{q} in {time.perf_counter() - start:.2f} s")

# (nothing: still subtracting when the judge's 5-second limit stopped it)

public class Main {
    public static void main(String[] args) {
        long start = System.nanoTime();
        int a = 2147483647, b = 1, q = 0;     // subtract b until it no longer fits; q counts the times
        while (a >= b) {
            a -= b;
            q++;
        }
        System.out.printf("%d in %.2f s%n", q, (System.nanoTime() - start) / 1e9);
    }
}

// 2147483647 in 1.06 s

#include <bits/stdc++.h>
using namespace std;

int main() {
    auto start = chrono::steady_clock::now();
    int a = 2147483647, b = 1, q = 0;      // subtract b until it no longer fits; q counts the times
    while (a >= b) {
        a -= b;
        q++;
    }
    printf("%d in %.2f s\n", q, chrono::duration<double>(chrono::steady_clock::now() - start).count());
}

// 2147483647 in 0.00 s

const start = performance.now();
let a = 2147483647, b = 1, q = 0;         // subtract b until it no longer fits; q counts the times
while (a >= b) {
    a -= b;
    q++;
}
console.log(`${q} in ${((performance.now() - start) / 1000).toFixed(2)} s`);

// 2147483647 in 1.46 s

const start = performance.now();
let a: number = 2147483647, b: number = 1, q: number = 0;   // subtract b until it no longer fits
while (a >= b) {
    a -= b;
    q++;
}
console.log(`${q} in ${((performance.now() - start) / 1000).toFixed(2)} s`);

// 2147483647 in 2.11 s

using System;
using System.Diagnostics;

class Program {
    static void Main() {
        var watch = Stopwatch.StartNew();
        int a = 2147483647, b = 1, q = 0;     // subtract b until it no longer fits; q counts the times
        while (a >= b) {
            a -= b;
            q++;
        }
        Console.WriteLine($"{q} in {watch.Elapsed.TotalSeconds:F2} s");
    }
}

// 2147483647 in 0.70 s

package main

import (
	"fmt"
	"time"
)

func main() {
	start := time.Now()
	a, b, q := 2147483647, 1, 0 // subtract b until it no longer fits; q counts the times
	for a >= b {
		a -= b
		q++
	}
	fmt.Printf("%d in %.2f s\n", q, time.Since(start).Seconds())
}

// 2147483647 in 0.70 s

That's 2,147,483,647 subtractions. Java, JavaScript, TypeScript, C# and Go needed 0.70 to 2.11 seconds; Python didn't finish inside its 5-second limit. C++ printed the answer at once: its compiler worked out what the loop computes and dropped the loop, which you can't count on.

Subtracting the divisor doubled, then doubled again, takes at most 32 rounds instead: the quotient's bits come out one at a time. This lesson is about two uses of a number's bits: as a set of yes-or-no flags, which lists every subset of a small set by counting, and as binary digits that a shift doubles and halves. It ends back here, with division by doubling.

Two dashed panels for 70 divided by 3. Left, crossed, subtracting: 23 small orange blocks of 3 in a row of rows, one per subtraction, and 1 left over: 23 steps. Right, ticked, doubling: the multiples 3, 6, 12, 24 and 48 as a ladder of blocks; take 48 (16 threes), then 12 (4), then 6 (2), then 3 (1), leaving 1: 4 subtractions, and the quotient 16 + 4 + 2 + 1 = 23 is 10111 in binary. Focal line: subtract the divisor doubled as often as it fits, from the largest down. Title: doubling beats subtracting.

A number as a set

Give each item of a small set a bit: item i is in the set when bit i is 1. One integer then holds a whole subset, and set operations become single operators: OR is union, AND is intersection, AND with the other set flipped is difference, and a shift tests one member. With A = {0, 2, 3} and B = {2, 4}:

def members(m):                       # the items whose bits are 1, as {0, 2, 3}
    return "{" + ", ".join(str(i) for i in range(8) if (m >> i) & 1) + "}"


A = (1 << 0) | (1 << 2) | (1 << 3)    # the set {0, 2, 3}
B = (1 << 2) | (1 << 4)               # the set {2, 4}
print("A      ", format(A, "05b"), members(A))
print("B      ", format(B, "05b"), members(B))
print("A | B  ", format(A | B, "05b"), members(A | B))      # union
print("A & B  ", format(A & B, "05b"), members(A & B))      # intersection
print("A & ~B ", format(A & ~B, "05b"), members(A & ~B))    # in A but not in B
print("is 3 in A?", (A >> 3) & 1)

# A       01101 {0, 2, 3}
# B       10100 {2, 4}
# A | B   11101 {0, 2, 3, 4}
# A & B   00100 {2}
# A & ~B  01001 {0, 3}
# is 3 in A? 1

public class Main {
    static String members(int m) {        // the items whose bits are 1, as {0, 2, 3}
        StringBuilder s = new StringBuilder("{");
        for (int i = 0; i < 8; i++)
            if (((m >> i) & 1) == 1) s.append(s.length() > 1 ? ", " : "").append(i);
        return s.append("}").toString();
    }

    static String bits(int m) {
        return String.format("%5s", Integer.toBinaryString(m)).replace(' ', '0');
    }

    public static void main(String[] args) {
        int A = (1 << 0) | (1 << 2) | (1 << 3);   // the set {0, 2, 3}
        int B = (1 << 2) | (1 << 4);              // the set {2, 4}
        System.out.println("A       " + bits(A) + " " + members(A));
        System.out.println("B       " + bits(B) + " " + members(B));
        System.out.println("A | B   " + bits(A | B) + " " + members(A | B));     // union
        System.out.println("A & B   " + bits(A & B) + " " + members(A & B));     // intersection
        System.out.println("A & ~B  " + bits(A & ~B) + " " + members(A & ~B));   // in A but not in B
        System.out.println("is 3 in A? " + ((A >> 3) & 1));
    }
}

// A       01101 {0, 2, 3}
// B       10100 {2, 4}
// A | B   11101 {0, 2, 3, 4}
// A & B   00100 {2}
// A & ~B  01001 {0, 3}
// is 3 in A? 1

#include <bits/stdc++.h>
using namespace std;

string members(int m) {               // the items whose bits are 1, as {0, 2, 3}
    string s = "{";
    for (int i = 0; i < 8; i++)
        if ((m >> i) & 1) s += (s.size() > 1 ? ", " : "") + to_string(i);
    return s + "}";
}

int main() {
    int A = (1 << 0) | (1 << 2) | (1 << 3);   // the set {0, 2, 3}
    int B = (1 << 2) | (1 << 4);              // the set {2, 4}
    cout << "A       " << bitset<5>(A) << " " << members(A) << "\n";
    cout << "B       " << bitset<5>(B) << " " << members(B) << "\n";
    cout << "A | B   " << bitset<5>(A | B) << " " << members(A | B) << "\n";     // union
    cout << "A & B   " << bitset<5>(A & B) << " " << members(A & B) << "\n";     // intersection
    cout << "A & ~B  " << bitset<5>(A & ~B) << " " << members(A & ~B) << "\n";   // in A but not in B
    cout << "is 3 in A? " << ((A >> 3) & 1) << "\n";
}

// A       01101 {0, 2, 3}
// B       10100 {2, 4}
// A | B   11101 {0, 2, 3, 4}
// A & B   00100 {2}
// A & ~B  01001 {0, 3}
// is 3 in A? 1

function members(m) {                 // the items whose bits are 1, as {0, 2, 3}
    const out = [];
    for (let i = 0; i < 8; i++) if ((m >> i) & 1) out.push(i);
    return `{${out.join(", ")}}`;
}
const bits = (m) => m.toString(2).padStart(5, "0");

const A = (1 << 0) | (1 << 2) | (1 << 3);   // the set {0, 2, 3}
const B = (1 << 2) | (1 << 4);              // the set {2, 4}
console.log("A      ", bits(A), members(A));
console.log("B      ", bits(B), members(B));
console.log("A | B  ", bits(A | B), members(A | B));      // union
console.log("A & B  ", bits(A & B), members(A & B));      // intersection
console.log("A & ~B ", bits(A & ~B), members(A & ~B));    // in A but not in B
console.log("is 3 in A?", (A >> 3) & 1);

// A       01101 {0, 2, 3}
// B       10100 {2, 4}
// A | B   11101 {0, 2, 3, 4}
// A & B   00100 {2}
// A & ~B  01001 {0, 3}
// is 3 in A? 1

function members(m: number): string {   // the items whose bits are 1, as {0, 2, 3}
    const out: number[] = [];
    for (let i = 0; i < 8; i++) if ((m >> i) & 1) out.push(i);
    return `{${out.join(", ")}}`;
}
const bits = (m: number): string => m.toString(2).padStart(5, "0");

const A = (1 << 0) | (1 << 2) | (1 << 3);   // the set {0, 2, 3}
const B = (1 << 2) | (1 << 4);              // the set {2, 4}
console.log("A      ", bits(A), members(A));
console.log("B      ", bits(B), members(B));
console.log("A | B  ", bits(A | B), members(A | B));      // union
console.log("A & B  ", bits(A & B), members(A & B));      // intersection
console.log("A & ~B ", bits(A & ~B), members(A & ~B));    // in A but not in B
console.log("is 3 in A?", (A >> 3) & 1);

// A       01101 {0, 2, 3}
// B       10100 {2, 4}
// A | B   11101 {0, 2, 3, 4}
// A & B   00100 {2}
// A & ~B  01001 {0, 3}
// is 3 in A? 1

using System;
using System.Collections.Generic;

class Program {
    static string Members(int m) {        // the items whose bits are 1, as {0, 2, 3}
        var items = new List<int>();
        for (int i = 0; i < 8; i++) if (((m >> i) & 1) == 1) items.Add(i);
        return "{" + string.Join(", ", items) + "}";
    }

    static string Bits(int m) => Convert.ToString(m, 2).PadLeft(5, '0');

    static void Main() {
        int A = (1 << 0) | (1 << 2) | (1 << 3);   // the set {0, 2, 3}
        int B = (1 << 2) | (1 << 4);              // the set {2, 4}
        Console.WriteLine($"A       {Bits(A)} {Members(A)}");
        Console.WriteLine($"B       {Bits(B)} {Members(B)}");
        Console.WriteLine($"A | B   {Bits(A | B)} {Members(A | B)}");     // union
        Console.WriteLine($"A & B   {Bits(A & B)} {Members(A & B)}");     // intersection
        Console.WriteLine($"A & ~B  {Bits(A & ~B)} {Members(A & ~B)}");   // in A but not in B
        Console.WriteLine($"is 3 in A? {(A >> 3) & 1}");
    }
}

// A       01101 {0, 2, 3}
// B       10100 {2, 4}
// A | B   11101 {0, 2, 3, 4}
// A & B   00100 {2}
// A & ~B  01001 {0, 3}
// is 3 in A? 1

package main

import (
	"fmt"
	"strings"
)

func members(m int) string { // the items whose bits are 1, as {0, 2, 3}
	items := []string{}
	for i := 0; i < 8; i++ {
		if (m>>i)&1 == 1 {
			items = append(items, fmt.Sprint(i))
		}
	}
	return "{" + strings.Join(items, ", ") + "}"
}

func main() {
	A := 1<<0 | 1<<2 | 1<<3 // the set {0, 2, 3}
	B := 1<<2 | 1<<4        // the set {2, 4}
	fmt.Printf("A       %05b %s\n", A, members(A))
	fmt.Printf("B       %05b %s\n", B, members(B))
	fmt.Printf("A | B   %05b %s\n", A|B, members(A|B))     // union
	fmt.Printf("A & B   %05b %s\n", A&B, members(A&B))     // intersection
	fmt.Printf("A & ~B  %05b %s\n", A&^B, members(A&^B))   // in A but not in B: Go writes it &^
	fmt.Println("is 3 in A?", (A>>3)&1)
}

// A       01101 {0, 2, 3}
// B       10100 {2, 4}
// A | B   11101 {0, 2, 3, 4}
// A & B   00100 {2}
// A & ~B  01001 {0, 3}
// is 3 in A? 1

A is 01101: bits 0, 2 and 3. The masks are 32 or 64 bits wide, so this works for sets of up to 32 or 64 items, and the size of a set is its count of 1s (Introduction to Bit Manipulation).

Every subset by counting

Subsets asks for every subset of n distinct values. Counting from 0 to 2ⁿ − 1 visits every n-bit pattern exactly once, and each pattern is a subset: mask m takes nums[i] when bit i of m is 1. On the problem's first example:

def subsets(nums):                    # mask m picks nums[i] when bit i of m is 1
    n = len(nums)
    return [[nums[i] for i in range(n) if (m >> i) & 1] for m in range(1 << n)]


for m, s in enumerate(subsets([1, 2, 3])):
    print(format(m, "03b"), "[" + ", ".join(map(str, s)) + "]")

# 000 []
# 001 [1]
# 010 [2]
# 011 [1, 2]
# 100 [3]
# 101 [1, 3]
# 110 [2, 3]
# 111 [1, 2, 3]

import java.util.*;

public class Main {
    static List<List<Integer>> subsets(int[] nums) {   // mask m picks nums[i] when bit i of m is 1
        int n = nums.length;
        List<List<Integer>> out = new ArrayList<>();
        for (int m = 0; m < (1 << n); m++) {
            List<Integer> s = new ArrayList<>();
            for (int i = 0; i < n; i++)
                if (((m >> i) & 1) == 1) s.add(nums[i]);
            out.add(s);
        }
        return out;
    }

    public static void main(String[] args) {
        List<List<Integer>> all = subsets(new int[] {1, 2, 3});
        for (int m = 0; m < all.size(); m++)
            System.out.println(String.format("%3s", Integer.toBinaryString(m)).replace(' ', '0') + " " + all.get(m));
    }
}

// 000 []
// 001 [1]
// 010 [2]
// 011 [1, 2]
// 100 [3]
// 101 [1, 3]
// 110 [2, 3]
// 111 [1, 2, 3]

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> subsets(const vector<int>& nums) {   // mask m picks nums[i] when bit i of m is 1
    int n = nums.size();
    vector<vector<int>> out;
    for (int m = 0; m < (1 << n); m++) {
        vector<int> s;
        for (int i = 0; i < n; i++)
            if ((m >> i) & 1) s.push_back(nums[i]);
        out.push_back(s);
    }
    return out;
}

int main() {
    vector<vector<int>> all = subsets({1, 2, 3});
    for (size_t m = 0; m < all.size(); m++) {
        cout << bitset<3>(m) << " [";
        for (size_t k = 0; k < all[m].size(); k++) cout << (k ? ", " : "") << all[m][k];
        cout << "]\n";
    }
}

// 000 []
// 001 [1]
// 010 [2]
// 011 [1, 2]
// 100 [3]
// 101 [1, 3]
// 110 [2, 3]
// 111 [1, 2, 3]

function subsets(nums) {              // mask m picks nums[i] when bit i of m is 1
    const n = nums.length, out = [];
    for (let m = 0; m < (1 << n); m++) {
        const s = [];
        for (let i = 0; i < n; i++) if ((m >> i) & 1) s.push(nums[i]);
        out.push(s);
    }
    return out;
}

subsets([1, 2, 3]).forEach((s, m) => console.log(m.toString(2).padStart(3, "0"), `[${s.join(", ")}]`));

// 000 []
// 001 [1]
// 010 [2]
// 011 [1, 2]
// 100 [3]
// 101 [1, 3]
// 110 [2, 3]
// 111 [1, 2, 3]

function subsets(nums: number[]): number[][] {   // mask m picks nums[i] when bit i of m is 1
    const n = nums.length, out: number[][] = [];
    for (let m = 0; m < (1 << n); m++) {
        const s: number[] = [];
        for (let i = 0; i < n; i++) if ((m >> i) & 1) s.push(nums[i]);
        out.push(s);
    }
    return out;
}

subsets([1, 2, 3]).forEach((s, m) => console.log(m.toString(2).padStart(3, "0"), `[${s.join(", ")}]`));

// 000 []
// 001 [1]
// 010 [2]
// 011 [1, 2]
// 100 [3]
// 101 [1, 3]
// 110 [2, 3]
// 111 [1, 2, 3]

using System;
using System.Collections.Generic;

class Program {
    static List<List<int>> Subsets(int[] nums) {   // mask m picks nums[i] when bit i of m is 1
        int n = nums.Length;
        var output = new List<List<int>>();
        for (int m = 0; m < (1 << n); m++) {
            var s = new List<int>();
            for (int i = 0; i < n; i++)
                if (((m >> i) & 1) == 1) s.Add(nums[i]);
            output.Add(s);
        }
        return output;
    }

    static void Main() {
        var all = Subsets(new[] { 1, 2, 3 });
        for (int m = 0; m < all.Count; m++)
            Console.WriteLine($"{Convert.ToString(m, 2).PadLeft(3, '0')} [{string.Join(", ", all[m])}]");
    }
}

// 000 []
// 001 [1]
// 010 [2]
// 011 [1, 2]
// 100 [3]
// 101 [1, 3]
// 110 [2, 3]
// 111 [1, 2, 3]

package main

import (
	"fmt"
	"strings"
)

func subsets(nums []int) [][]int { // mask m picks nums[i] when bit i of m is 1
	n := len(nums)
	out := [][]int{}
	for m := 0; m < 1<<n; m++ {
		s := []int{}
		for i := 0; i < n; i++ {
			if (m>>i)&1 == 1 {
				s = append(s, nums[i])
			}
		}
		out = append(out, s)
	}
	return out
}

func main() {
	for m, s := range subsets([]int{1, 2, 3}) {
		parts := []string{}
		for _, v := range s {
			parts = append(parts, fmt.Sprint(v))
		}
		fmt.Printf("%03b [%s]\n", m, strings.Join(parts, ", "))
	}
}

// 000 []
// 001 [1]
// 010 [2]
// 011 [1, 2]
// 100 [3]
// 101 [1, 3]
// 110 [2, 3]
// 111 [1, 2, 3]

A dashed band with the items 1, 2 and 3 over bits 0, 1 and 2. Below, a grid of eight cards, one per mask from 000 to 111: each shows the mask's three bits, the 1s green, and the subset it picks: 000 [], 001 [1], 010 [2], 011 [1, 2], 100 [3], 101 [1, 3], 110 [2, 3], 111 [1, 2, 3]. Focal line: count from 0 to 2ⁿ − 1 and every subset appears once. Title: every mask is a subset.

That's 2ⁿ subsets with up to n values each, O(n · 2ⁿ), the same as building them by choosing or skipping each value (Backtracking: Subsets and Combinations); the loop just has no recursion. Masks stay practical up to about 20 items, where 2²⁰ is 1,048,576 subsets.

The subsets of a mask

Sometimes you need every subset of one mask, not of everything. sub = (sub - 1) & mask steps from mask down through each of its subsets: subtracting 1 turns the lowest 1 into 0s and 1s, and the AND keeps only bits that are in mask. On 1011, then counted over every mask of 10 bits:

mask = 0b1011                         # 11: the items 0, 1 and 3
sub, seen = mask, []
while True:
    seen.append(sub)
    if sub == 0:
        break
    sub = (sub - 1) & mask            # the next smaller subset of mask
print(*seen)
print(*(format(s, "04b") for s in seen))

n, steps, power = 10, 0, 1
for m in range(1 << n):               # every mask of 10 bits, and every subset of each
    sub = m
    while True:
        steps += 1
        if sub == 0:
            break
        sub = (sub - 1) & m
for _ in range(n):
    power *= 3
print(f"n = {n}: {steps} steps, and 3^{n} is {power}")

# 11 10 9 8 3 2 1 0
# 1011 1010 1001 1000 0011 0010 0001 0000
# n = 10: 59049 steps, and 3^10 is 59049

public class Main {
    public static void main(String[] args) {
        int mask = 0b1011;                    // 11: the items 0, 1 and 3
        StringBuilder values = new StringBuilder(), bits = new StringBuilder();
        for (int sub = mask; ; sub = (sub - 1) & mask) {   // the next smaller subset of mask
            values.append(values.length() > 0 ? " " : "").append(sub);
            bits.append(bits.length() > 0 ? " " : "")
                .append(String.format("%4s", Integer.toBinaryString(sub)).replace(' ', '0'));
            if (sub == 0) break;
        }
        System.out.println(values);
        System.out.println(bits);

        int n = 10, steps = 0, power = 1;
        for (int m = 0; m < (1 << n); m++) {  // every mask of 10 bits, and every subset of each
            for (int sub = m; ; sub = (sub - 1) & m) {
                steps++;
                if (sub == 0) break;
            }
        }
        for (int i = 0; i < n; i++) power *= 3;
        System.out.println("n = " + n + ": " + steps + " steps, and 3^" + n + " is " + power);
    }
}

// 11 10 9 8 3 2 1 0
// 1011 1010 1001 1000 0011 0010 0001 0000
// n = 10: 59049 steps, and 3^10 is 59049

#include <bits/stdc++.h>
using namespace std;

int main() {
    int mask = 0b1011;                     // 11: the items 0, 1 and 3
    string values, bits;
    for (int sub = mask; ; sub = (sub - 1) & mask) {   // the next smaller subset of mask
        values += (values.empty() ? "" : " ") + to_string(sub);
        bits += (bits.empty() ? "" : " ") + bitset<4>(sub).to_string();
        if (sub == 0) break;
    }
    cout << values << "\n" << bits << "\n";

    int n = 10, steps = 0, power = 1;
    for (int m = 0; m < (1 << n); m++) {   // every mask of 10 bits, and every subset of each
        for (int sub = m; ; sub = (sub - 1) & m) {
            steps++;
            if (sub == 0) break;
        }
    }
    for (int i = 0; i < n; i++) power *= 3;
    cout << "n = " << n << ": " << steps << " steps, and 3^" << n << " is " << power << "\n";
}

// 11 10 9 8 3 2 1 0
// 1011 1010 1001 1000 0011 0010 0001 0000
// n = 10: 59049 steps, and 3^10 is 59049

const mask = 0b1011;                      // 11: the items 0, 1 and 3
const seen = [];
for (let sub = mask; ; sub = (sub - 1) & mask) {   // the next smaller subset of mask
    seen.push(sub);
    if (sub === 0) break;
}
console.log(seen.join(" "));
console.log(seen.map((s) => s.toString(2).padStart(4, "0")).join(" "));

let n = 10, steps = 0, power = 1;
for (let m = 0; m < (1 << n); m++) {      // every mask of 10 bits, and every subset of each
    for (let sub = m; ; sub = (sub - 1) & m) {
        steps++;
        if (sub === 0) break;
    }
}
for (let i = 0; i < n; i++) power *= 3;
console.log(`n = ${n}: ${steps} steps, and 3^${n} is ${power}`);

// 11 10 9 8 3 2 1 0
// 1011 1010 1001 1000 0011 0010 0001 0000
// n = 10: 59049 steps, and 3^10 is 59049

const mask: number = 0b1011;              // 11: the items 0, 1 and 3
const seen: number[] = [];
for (let sub = mask; ; sub = (sub - 1) & mask) {   // the next smaller subset of mask
    seen.push(sub);
    if (sub === 0) break;
}
console.log(seen.join(" "));
console.log(seen.map((s) => s.toString(2).padStart(4, "0")).join(" "));

let n = 10, steps = 0, power = 1;
for (let m = 0; m < (1 << n); m++) {      // every mask of 10 bits, and every subset of each
    for (let sub = m; ; sub = (sub - 1) & m) {
        steps++;
        if (sub === 0) break;
    }
}
for (let i = 0; i < n; i++) power *= 3;
console.log(`n = ${n}: ${steps} steps, and 3^${n} is ${power}`);

// 11 10 9 8 3 2 1 0
// 1011 1010 1001 1000 0011 0010 0001 0000
// n = 10: 59049 steps, and 3^10 is 59049

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int mask = 0b1011;                    // 11: the items 0, 1 and 3
        var values = new List<string>();
        var bits = new List<string>();
        for (int sub = mask; ; sub = (sub - 1) & mask) {   // the next smaller subset of mask
            values.Add(sub.ToString());
            bits.Add(Convert.ToString(sub, 2).PadLeft(4, '0'));
            if (sub == 0) break;
        }
        Console.WriteLine(string.Join(" ", values));
        Console.WriteLine(string.Join(" ", bits));

        int n = 10, steps = 0, power = 1;
        for (int m = 0; m < (1 << n); m++) {  // every mask of 10 bits, and every subset of each
            for (int sub = m; ; sub = (sub - 1) & m) {
                steps++;
                if (sub == 0) break;
            }
        }
        for (int i = 0; i < n; i++) power *= 3;
        Console.WriteLine($"n = {n}: {steps} steps, and 3^{n} is {power}");
    }
}

// 11 10 9 8 3 2 1 0
// 1011 1010 1001 1000 0011 0010 0001 0000
// n = 10: 59049 steps, and 3^10 is 59049

package main

import (
	"fmt"
	"strings"
)

func main() {
	mask := 0b1011 // 11: the items 0, 1 and 3
	values, bits := []string{}, []string{}
	for sub := mask; ; sub = (sub - 1) & mask { // the next smaller subset of mask
		values = append(values, fmt.Sprint(sub))
		bits = append(bits, fmt.Sprintf("%04b", sub))
		if sub == 0 {
			break
		}
	}
	fmt.Println(strings.Join(values, " "))
	fmt.Println(strings.Join(bits, " "))

	n, steps, power := 10, 0, 1
	for m := 0; m < 1<<n; m++ { // every mask of 10 bits, and every subset of each
		for sub := m; ; sub = (sub - 1) & m {
			steps++
			if sub == 0 {
				break
			}
		}
	}
	for i := 0; i < n; i++ {
		power *= 3
	}
	fmt.Printf("n = %d: %d steps, and 3^%d is %d\n", n, steps, n, power)
}

// 11 10 9 8 3 2 1 0
// 1011 1010 1001 1000 0011 0010 0001 0000
// n = 10: 59049 steps, and 3^10 is 59049

1011 has three 1s, so 2³ = 8 subsets, the last one empty. Over every mask of n bits it's 3ⁿ steps in all, 59,049 for n = 10: each bit is in neither, the mask only, or both. Bitmask DP in Dynamic Programming is built on these loops.

The AND of a range

Bitwise AND of Numbers Range asks for the AND of every number from left to right. Counting from left to right flips every bit below the highest one where left and right differ, so all of those come out 0; what's left is the binary prefix they share. Shift both right until they're equal, then shift back:

def range_and(left, right):           # the AND of every number from left to right
    shift = 0
    while left != right:              # drop bits from the right until only the common prefix is left
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift              # the prefix, with 0s where the dropped bits were


for left, right in ((5, 7), (26, 30), (0, 0), (1, 2147483647)):
    print(f"[{left}, {right}] -> {range_and(left, right)}")

# [5, 7] -> 4
# [26, 30] -> 24
# [0, 0] -> 0
# [1, 2147483647] -> 0

public class Main {
    static int rangeAnd(int left, int right) {   // the AND of every number from left to right
        int shift = 0;
        while (left != right) {           // drop bits from the right until only the common prefix is left
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;             // the prefix, with 0s where the dropped bits were
    }

    public static void main(String[] args) {
        int[][] pairs = {{5, 7}, {26, 30}, {0, 0}, {1, 2147483647}};
        for (int[] p : pairs) System.out.println("[" + p[0] + ", " + p[1] + "] -> " + rangeAnd(p[0], p[1]));
    }
}

// [5, 7] -> 4
// [26, 30] -> 24
// [0, 0] -> 0
// [1, 2147483647] -> 0

#include <bits/stdc++.h>
using namespace std;

int rangeAnd(int left, int right) {    // the AND of every number from left to right
    int shift = 0;
    while (left != right) {                // drop bits from the right until only the common prefix is left
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;                  // the prefix, with 0s where the dropped bits were
}

int main() {
    int pairs[][2] = {{5, 7}, {26, 30}, {0, 0}, {1, 2147483647}};
    for (auto& p : pairs) cout << "[" << p[0] << ", " << p[1] << "] -> " << rangeAnd(p[0], p[1]) << "\n";
}

// [5, 7] -> 4
// [26, 30] -> 24
// [0, 0] -> 0
// [1, 2147483647] -> 0

function rangeAnd(left, right) {      // the AND of every number from left to right
    let shift = 0;
    while (left !== right) {              // drop bits from the right until only the common prefix is left
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;                 // the prefix, with 0s where the dropped bits were
}

for (const [left, right] of [[5, 7], [26, 30], [0, 0], [1, 2147483647]])
    console.log(`[${left}, ${right}] -> ${rangeAnd(left, right)}`);

// [5, 7] -> 4
// [26, 30] -> 24
// [0, 0] -> 0
// [1, 2147483647] -> 0

function rangeAnd(left: number, right: number): number {   // the AND of every number from left to right
    let shift = 0;
    while (left !== right) {              // drop bits from the right until only the common prefix is left
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;                 // the prefix, with 0s where the dropped bits were
}

for (const [left, right] of [[5, 7], [26, 30], [0, 0], [1, 2147483647]])
    console.log(`[${left}, ${right}] -> ${rangeAnd(left, right)}`);

// [5, 7] -> 4
// [26, 30] -> 24
// [0, 0] -> 0
// [1, 2147483647] -> 0

using System;

class Program {
    static int RangeAnd(int left, int right) {   // the AND of every number from left to right
        int shift = 0;
        while (left != right) {           // drop bits from the right until only the common prefix is left
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;             // the prefix, with 0s where the dropped bits were
    }

    static void Main() {
        int[][] pairs = { new[] { 5, 7 }, new[] { 26, 30 }, new[] { 0, 0 }, new[] { 1, 2147483647 } };
        foreach (int[] p in pairs) Console.WriteLine($"[{p[0]}, {p[1]}] -> {RangeAnd(p[0], p[1])}");
    }
}

// [5, 7] -> 4
// [26, 30] -> 24
// [0, 0] -> 0
// [1, 2147483647] -> 0

package main

import "fmt"

func rangeAnd(left, right int) int { // the AND of every number from left to right
	shift := 0
	for left != right { // drop bits from the right until only the common prefix is left
		left >>= 1
		right >>= 1
		shift++
	}
	return left << shift // the prefix, with 0s where the dropped bits were
}

func main() {
	for _, p := range [][2]int{{5, 7}, {26, 30}, {0, 0}, {1, 2147483647}} {
		fmt.Printf("[%d, %d] -> %d\n", p[0], p[1], rangeAnd(p[0], p[1]))
	}
}

// [5, 7] -> 4
// [26, 30] -> 24
// [0, 0] -> 0
// [1, 2147483647] -> 0

A dashed panel with the numbers 26 to 30 in binary, one per row: 11010, 11011, 11100, 11101, 11110, the first two bits of every row green, the rest grey; under them the AND, 11000 (24), its first two bits green. Beside it, a dashed panel shifting 26 and 30 right together: 13 and 15, 6 and 7, 3 and 3, equal after 3 shifts; 3 << 3 = 24. Focal line: the AND of a range keeps the bits the two ends share. Title: AND keeps the common prefix.

[26, 30] shares 11 on the left, so the answer is 11000, 24. It takes at most 31 shifts, where ANDing the numbers one by one could take two billion steps. Repeating right &= right − 1 while right > left gives the same answer, one set bit at a time.

Division by doubling

Back to Divide Two Integers. A quotient is a binary number, so build it bit by bit from the top: bit k is 1 when the divisor shifted left k times still fits in what's left, and then you subtract it. Two details: work with absolute values in 64 bits, since |−2³¹| doesn't fit in a 32-bit int, and return 2³¹ − 1 for −2³¹ / −1, the one quotient that doesn't fit:

def divide(dividend, divisor):
    if dividend == -2147483648 and divisor == -1:
        return 2147483647                 # the one quotient that doesn't fit in 32 bits
    negative = (dividend < 0) != (divisor < 0)
    a, b, q = abs(dividend), abs(divisor), 0
    for k in range(31, -1, -1):           # from the top: does b doubled k times still fit in a?
        if (a >> k) >= b:                 # the same test as b << k <= a, without overflowing
            a -= b << k
            q |= 1 << k                   # then bit k of the quotient is 1
    return -q if negative else q


for x, y in ((10, 3), (7, -3), (-7, 2), (-2147483648, -1), (-2147483648, 1), (2147483647, 1)):
    print(f"{x} / {y} = {divide(x, y)}")

# 10 / 3 = 3
# 7 / -3 = -2
# -7 / 2 = -3
# -2147483648 / -1 = 2147483647
# -2147483648 / 1 = -2147483648
# 2147483647 / 1 = 2147483647

public class Main {
    static int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;         // the one quotient that doesn't fit in 32 bits
        boolean negative = (dividend < 0) != (divisor < 0);
        long a = Math.abs((long) dividend), b = Math.abs((long) divisor), q = 0;   // |-2^31| needs 64 bits
        for (int k = 31; k >= 0; k--) {       // from the top: does b doubled k times still fit in a?
            if ((a >> k) >= b) {              // the same test as b << k <= a, without overflowing
                a -= b << k;
                q |= 1L << k;                 // then bit k of the quotient is 1
            }
        }
        return (int) (negative ? -q : q);
    }

    public static void main(String[] args) {
        int[][] pairs = {{10, 3}, {7, -3}, {-7, 2}, {-2147483648, -1}, {-2147483648, 1}, {2147483647, 1}};
        for (int[] p : pairs) System.out.println(p[0] + " / " + p[1] + " = " + divide(p[0], p[1]));
    }
}

// 10 / 3 = 3
// 7 / -3 = -2
// -7 / 2 = -3
// -2147483648 / -1 = 2147483647
// -2147483648 / 1 = -2147483648
// 2147483647 / 1 = 2147483647

#include <bits/stdc++.h>
using namespace std;

int divide(int dividend, int divisor) {
    if (dividend == INT_MIN && divisor == -1)
        return INT_MAX;                    // the one quotient that doesn't fit in 32 bits
    bool negative = (dividend < 0) != (divisor < 0);
    long long a = llabs((long long) dividend), b = llabs((long long) divisor), q = 0;   // |-2^31| needs 64 bits
    for (int k = 31; k >= 0; k--) {        // from the top: does b doubled k times still fit in a?
        if ((a >> k) >= b) {               // the same test as b << k <= a, without overflowing
            a -= b << k;
            q |= 1LL << k;                 // then bit k of the quotient is 1
        }
    }
    return negative ? -q : q;
}

int main() {
    int pairs[][2] = {{10, 3}, {7, -3}, {-7, 2}, {-2147483648, -1}, {-2147483648, 1}, {2147483647, 1}};
    for (auto& p : pairs) cout << p[0] << " / " << p[1] << " = " << divide(p[0], p[1]) << "\n";
}

// 10 / 3 = 3
// 7 / -3 = -2
// -7 / 2 = -3
// -2147483648 / -1 = 2147483647
// -2147483648 / 1 = -2147483648
// 2147483647 / 1 = 2147483647

function divide(dividend, divisor) {
    if (dividend === -2147483648 && divisor === -1)
        return 2147483647;                // the one quotient that doesn't fit in 32 bits
    const negative = (dividend < 0) !== (divisor < 0);
    let a = Math.abs(dividend), b = Math.abs(divisor), q = 0;
    for (let k = 31; k >= 0; k--) {       // from the top: does b doubled k times still fit in a?
        if ((a >>> k) >= b) {             // >>> reads a as 32 unsigned bits, so 2^31 stays positive
            a -= (b << k) >>> 0;
            q += (1 << k) >>> 0;          // then bit k of the quotient is 1
        }
    }
    return negative ? -q : q;
}

for (const [x, y] of [[10, 3], [7, -3], [-7, 2], [-2147483648, -1], [-2147483648, 1], [2147483647, 1]])
    console.log(`${x} / ${y} = ${divide(x, y)}`);

// 10 / 3 = 3
// 7 / -3 = -2
// -7 / 2 = -3
// -2147483648 / -1 = 2147483647
// -2147483648 / 1 = -2147483648
// 2147483647 / 1 = 2147483647

function divide(dividend: number, divisor: number): number {
    if (dividend === -2147483648 && divisor === -1)
        return 2147483647;                // the one quotient that doesn't fit in 32 bits
    const negative = (dividend < 0) !== (divisor < 0);
    let a = Math.abs(dividend), b = Math.abs(divisor), q = 0;
    for (let k = 31; k >= 0; k--) {       // from the top: does b doubled k times still fit in a?
        if ((a >>> k) >= b) {             // >>> reads a as 32 unsigned bits, so 2^31 stays positive
            a -= (b << k) >>> 0;
            q += (1 << k) >>> 0;          // then bit k of the quotient is 1
        }
    }
    return negative ? -q : q;
}

for (const [x, y] of [[10, 3], [7, -3], [-7, 2], [-2147483648, -1], [-2147483648, 1], [2147483647, 1]])
    console.log(`${x} / ${y} = ${divide(x, y)}`);

// 10 / 3 = 3
// 7 / -3 = -2
// -7 / 2 = -3
// -2147483648 / -1 = 2147483647
// -2147483648 / 1 = -2147483648
// 2147483647 / 1 = 2147483647

using System;

class Program {
    static int Divide(int dividend, int divisor) {
        if (dividend == int.MinValue && divisor == -1)
            return int.MaxValue;              // the one quotient that doesn't fit in 32 bits
        bool negative = (dividend < 0) != (divisor < 0);
        long a = Math.Abs((long)dividend), b = Math.Abs((long)divisor), q = 0;   // |-2^31| needs 64 bits
        for (int k = 31; k >= 0; k--) {       // from the top: does b doubled k times still fit in a?
            if ((a >> k) >= b) {              // the same test as b << k <= a, without overflowing
                a -= b << k;
                q |= 1L << k;                 // then bit k of the quotient is 1
            }
        }
        return (int)(negative ? -q : q);
    }

    static void Main() {
        int[][] pairs = { new[] { 10, 3 }, new[] { 7, -3 }, new[] { -7, 2 }, new[] { -2147483648, -1 },
                          new[] { -2147483648, 1 }, new[] { 2147483647, 1 } };
        foreach (int[] p in pairs) Console.WriteLine($"{p[0]} / {p[1]} = {Divide(p[0], p[1])}");
    }
}

// 10 / 3 = 3
// 7 / -3 = -2
// -7 / 2 = -3
// -2147483648 / -1 = 2147483647
// -2147483648 / 1 = -2147483648
// 2147483647 / 1 = 2147483647

package main

import (
	"fmt"
	"math"
)

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func divide(dividend, divisor int) int {
	if dividend == math.MinInt32 && divisor == -1 {
		return math.MaxInt32 // the one quotient that doesn't fit in 32 bits
	}
	negative := (dividend < 0) != (divisor < 0)
	a, b, q := abs(dividend), abs(divisor), 0
	for k := 31; k >= 0; k-- { // from the top: does b doubled k times still fit in a?
		if a>>k >= b { // the same test as b << k <= a, without overflowing
			a -= b << k
			q |= 1 << k // then bit k of the quotient is 1
		}
	}
	if negative {
		return -q
	}
	return q
}

func main() {
	for _, p := range [][2]int{{10, 3}, {7, -3}, {-7, 2}, {-2147483648, -1}, {-2147483648, 1}, {2147483647, 1}} {
		fmt.Printf("%d / %d = %d\n", p[0], p[1], divide(p[0], p[1]))
	}
}

// 10 / 3 = 3
// 7 / -3 = -2
// -7 / 2 = -3
// -2147483648 / -1 = 2147483647
// -2147483648 / 1 = -2147483648
// 2147483647 / 1 = 2147483647

At most 32 rounds, where subtracting took two billion, and −7 / 2 is −3: the problem's quotient rounds toward 0. (a >> k) >= b is the same test as (b << k) <= a, and it can't overflow.

Divide by Doubling. Divide one number by another without dividing: at each step, pick the largest multiple of the divisor, doubled, that still fits in what's left. Watch the quotient's bits appear.

Divide by Doubling: subtract the largest doubled divisor that fits, and build the quotient

Spotting it

The clues: "every subset" or "every combination" of at most about 20 items, a state that's a set of small things (which cities are visited, which keys are held), "without *, / or %", or the AND, OR or XOR of a whole range. Near misses:

Subsets of a larger set, or with pruning as you go: backtracking (Backtracking: Subsets and Combinations).
The best order of visiting every item, or a DP over subsets: bitmask DP (Dynamic Programming).
Values that pair up and cancel: XOR Tricks.

Mistakes that cost an interview

−2³¹ / −1 with plain division. The true answer, 2,147,483,648, is one more than a 32-bit int holds, and each language does something different:

a, b = -2147483648, -1
print(a // b)                         # -2^31 / -1, Python's integer division

# 2147483648

public class Main {
    public static void main(String[] args) {
        int a = Integer.MIN_VALUE, b = -1;
        System.out.println(a / b);         // -2^31 / -1 in 32 bits
    }
}

// -2147483648

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = INT_MIN, b = -1;
    cout << a / b << endl;                 // -2^31 / -1 in 32 bits
}

// 844223704

const a = -2147483648, b = -1;
console.log(Math.trunc(a / b), (a / b) | 0);   // as a double, then as 32 bits

// 2147483648 -2147483648

const a: number = -2147483648, b: number = -1;
console.log(Math.trunc(a / b), (a / b) | 0);   // as a double, then as 32 bits

// 2147483648 -2147483648

using System;

class Program {
    static void Main() {
        int a = int.MinValue, b = -1;
        Console.WriteLine(a / b);          // -2^31 / -1 in 32 bits
    }
}

// (nothing printed: System.OverflowException)

package main

import (
	"fmt"
	"math"
)

func main() {
	var a, b int32 = math.MinInt32, -1
	fmt.Println(a / b) // -2^31 / -1 in 32 bits
}

// -2147483648

Language	−2³¹ / −1	What happened
Python	2,147,483,648	no fixed width: the right answer
Java	−2,147,483,648	wrapped around, with no error
C++	844,223,704	undefined: −971,622,984 on the next run
JavaScript	2,147,483,648	a double; `\| 0` wraps it to −2,147,483,648
TypeScript	2,147,483,648	the same as JavaScript
C#	an error	`System.OverflowException`
Go	−2,147,483,648	wrapped around in an `int32`

Test for it first, as the solution above does.

A 32-bit counter up to 2³¹ − 1. ANDing the numbers one by one with i <= right and right = 2,147,483,647 never stops in a 32-bit int: i reaches the largest value, i++ wraps it to −2³¹, and i <= right is still true:

left, right, result = 2147483646, 2147483647, 2147483647
for i in range(left, right + 1):      # AND every number in [left, right]
    result &= i
print(result)

# 2147483646

public class Main {
    public static void main(String[] args) {
        int left = 2147483646, right = 2147483647, result = right;
        for (int i = left; i <= right; i++) result &= i;   // AND every number in [left, right]
        System.out.println(result);
    }
}

// (no line: still looping when the judge stopped it after 2 s)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int left = 2147483646, right = 2147483647, result = right;
    for (int i = left; i <= right; i++) result &= i;   // AND every number in [left, right]
    cout << result << endl;
}

// (nothing printed, and no error)

const left = 2147483646, right = 2147483647;
let result = right;
for (let i = left; i <= right; i++) result &= i;   // AND every number in [left, right]
console.log(result);

// 2147483646

const left: number = 2147483646, right: number = 2147483647;
let result: number = right;
for (let i = left; i <= right; i++) result &= i;   // AND every number in [left, right]
console.log(result);

// 2147483646

using System;

class Program {
    static void Main() {
        int left = 2147483646, right = 2147483647, result = right;
        for (int i = left; i <= right; i++) result &= i;   // AND every number in [left, right]
        Console.WriteLine(result);
    }
}

// (no line: still looping when the judge stopped it after 2 s)

package main

import "fmt"

func main() {
	var left, right int32 = 2147483646, 2147483647
	result := right
	for i := left; i <= right; i++ { // AND every number in [left, right]
		result &= i
	}
	fmt.Println(result)
}

// (no line: still looping when the judge stopped it after 2 s)

Python, JavaScript and TypeScript printed 2,147,483,646, since their numbers don't wrap at 2³¹; Java, C# and Go didn't finish; C++ printed nothing at all and exited as if it had finished: the overflow is undefined behaviour, and the compiler was free to drop the loop and the line after it. Use the prefix, or a 64-bit counter.

1 << n for n ≥ 31. In a 32-bit int, 1 << 31 is already negative, so m < (1 << n) with n = 31 runs no times at all; masks for 31 or more items need 64 bits (Introduction to Bit Manipulation ran it).

Testing a member with == 1. (mask & (1 << i)) == 1 is true only for i = 0, because the AND keeps the bit where it is, worth 2ⁱ. Compare with != 0, or shift first: (mask >> i) & 1.

Check yourself

Quiz

1 / 6

Multiple choice

Items [a, b, c] take bits 0, 1 and 2. Which subset is the mask 101?

Practice

In this section, easy to hard:

Subsets: count masks from 0 to 2ⁿ − 1; bit i picks nums[i].
Bitwise AND of Numbers Range: the common prefix of the two ends.
Divide Two Integers: the quotient's bits from the top, in 64 bits, and −2³¹ / −1 first.

Bit Manipulation Quiz, at the end of this section, mixes all three lessons.