Bitmask Basics For Dynamic Programming

Image Source

Many Java developers who feel comfortable with loops and arrays still find bitmask based dynamic programming a little hard to read at first. Routing, scheduling, and selection problems ask you to track which items are already part of a partial solution and which ones are still free. This bitmask idea turns that yes or no choice for each item into bits inside an integer, so dynamic programming states can record both the current position and the subset of visited elements. This compact layout lets you store many states and move between them with direct, mechanical rules that work well for problems built from small sets of elements.

Bitmasks As Subset Trackers

Lots of problems in routing, scheduling, or selection boil down to one question for every element in a small set, included or not included. That decision can be stored in a boolean array, but bitmasks pack those answers into the bits of an integer so that one value carries the entire subset. Each bit stands for one element, and switching a bit on or off changes membership in the subset without any extra objects or collections. Bit operations in Java are fast and stable, so this style pairs naturally with dynamic programming tables that need to remember which items are active at a given moment.

Most Java developers already work with int and long all the time, but rarely pay attention to the individual bits. Thinking of an int as 32 separate flags and a long as 64 flags opens a very compact way to track subsets, where membership checks become bit tests and updates become bit operations. That view is exactly what bitmask dynamic programming leans on later, so building comfort with these ideas up front pays off.

Bits As Flags For Elements

Many bitmask based solutions start with a simple mapping. Element 0 corresponds to bit 0, element 1 to bit 1, and so on up to some limit such as n - 1. Bit value 1 means the element is present in the subset. Bit value 0 means it is absent. Single integer variables then hold several membership flags at once. Java gives direct operators for this work. Operator << shifts bits to the left, & performs bitwise and, | performs bitwise or, and ~ flips bits. Combining those operators lets code add an element to a subset, remove an element, and test membership without any branches beyond a comparison. Small helper methods keep the intent readable.

This helper collects the usual bit operations into small methods that keep the intent obvious:

Each method works with a plain int mask, where i is an index from zero up to at most thirty for a safe range when negative values are not desired. Operator ^ in toggleElement performs bitwise xor, which flips the chosen bit while leaving all others alone.

Many beginners find it helpful to see how a mask changes as bits are flipped for a small example. Suppose elements are numbered from 0 to 3, and a developer wants a subset that currently holds only elements 1 and 3. That subset corresponds to a mask where bit 1 and bit 3 are set. Binary representation looks like 1010 which is 10 in decimal form.

This prints a small mask and reports which elements are present so the effect of each call is easy to see:

The console output lists which elements are present according to the bitmask. That loop over i matches what many dynamic programming transitions will do later, checking each element in turn and deciding whether to add it to the subset or skip it.

Bit indexing does not have to start at zero for every problem, although that convention is common and keeps expressions readable. Some developers offset indices or group related bits next to each other to match how they think about the data. What matters is that the mapping from elements to bit positions stays consistent everywhere in the code.

Encoding Subsets With Integers

Small combinatorial problems that use bitmask dynamic programming typically involve up to 20 or so elements. That count is important because a set with n elements has 2^n subsets, and each subset maps to an integer mask from 0 up to 2^n - 1. Writing those masks in binary form gives a direct picture of which elements are present. Mask 0 represents the empty set. Mask 1 has only element 0. Mask 5 has elements 0 and 2.

An int has 32 bits, but code that counts masks with 1 << n and uses masks as array indices stays workable only while n is at most 30, because 1 << 31 overflows and masks turn negative. A long mask with 1L << n avoids that overflow and supports the same style of loops up to n equal to 62.

Iterating through all subsets of a given size n is straightforward with masks. Java loops usually run from 0 to (1 << n) - 1 when the mask is an int and n is at most 30, past that, switch the mask and the bound to long and use 1L << n.

The code example here walks through every subset for a small value of n and writes the result in set notation:

Output from this program lists every subset of the set {0, 1, 2, 3} in some order corresponding to the mask values. Human readers can watch how the binary representation of mask relates to the subset contents, which builds intuition for later dynamic programming states that attach costs or distances to those same masks.

Some problems care about how many elements a subset contains. Java offers Integer.bitCount(mask) to count the number of one bits in a mask. That method turns out to be very handy when dynamic programming transitions depend on subset size, such as when only subsets with exactly k elements are allowed.

This filter loop keeps only masks of a given size and sends them to the same printer:

Filtering on Integer.bitCount(mask) gives direct control over which subsets are processed, and no extra data structures are required beyond the integers already in hand. That style lines up well with dynamic programming tables indexed by mask.

Lots of developers also like having a helper that converts a mask into an int[] or List<Integer> of indices, so that call sites can pass around concrete element lists when needed. Conversion from mask to list stays mechanical.

This converter turns a mask back into a list of indices so other parts of the code can work with plain collections:

That helper wraps the common pattern of scanning bits into a small unit, so dynamic programming code can stay focused on costs, distances, or schedules while still benefiting from compact bitmask state encoding.

Dynamic Programming With Bitmasks

Dynamic programming with bitmasks builds on the idea that a single integer can carry an entire subset while an index marks a current position or choice. States then answer questions such as “what is the best cost so far if these elements are active and the process currently stands at index i”. That extra dimension based on subsets gives enough memory of the past to enforce constraints like “visit each city exactly one time” or “pick a combination of jobs that respects capacity limits”.

Many classical problems for bitmask dynamic programming use a small number of elements, usually somewhere in the low double digits. That range keeps the total count of subsets manageable; for n elements there are 2^n masks, and each mask tracks one combination. Tables indexed by mask and position then record partial results that later transitions build on.

State Design For Subset Problems

Dynamic programming always starts with a choice of state. For subset based questions, one common layout uses a two dimensional table dp[mask][i]. Variable mask tells which elements are already part of the current partial solution, and i specifies a current index such as the last city visited, the last job scheduled, or just the current position in an array. Entry dp[mask][i] then holds some quantity like total distance, total time, or total profit. Routing problems are a natural fit for this layout. A route visiting cities can be described by the set of cities already visited and the city where the traveler currently stands. That story turns directly into mask and i. Collection based state such as Set<Integer> could hold similar information, but arrays indexed by an integer mask are much more compact and easier for the CPU to work with.

Memory needs grow with n, because there are 2^n different masks and n options for i. That means dp holds n * 2^n entries. Values can be stored as int, long, or sometimes double, depending on the quantity being tracked. Many bitmask based solutions set all entries to a large value at the start, then relax that value as better paths or selections appear.

Code that allocates such a table and prepares it for use can be as simple as:

Sentinel INF stands in for “no solution yet”. Later transitions only overwrite an entry if a better value is found. That pattern mirrors the way shortest path algorithms work, with values starting high and decreasing as shorter routes are discovered.

Some problems do not need a position index at all. Subset sum, some resource allocation questions, and certain scheduling variants only care about which elements belong to the subset. In that case, state can shrink to a one dimensional array dp[mask]. Each entry then holds the best value for exactly that subset.

Let’s look at a example that uses a one dimensional table:

Base case bestProfitForMask[0] = 0 sets the starting point for transitions that add elements to the subset in later loops. Choice between dp[mask][i] and dp[mask] depends on whether the problem statement needs a notion of current position or last element.

Transitions For Routing Style Problems

Routing problems bring out the strengths of bitmask dynamic programming because every city can be included or excluded, and the traveler always has a current location. States capture “visited cities” and “current city”. Transitions move from one city to another and extend the set of visited cities. Cost tables like dist[i][j] then give the distance between city i and city j. One common variant is a Traveling Salesman style layout where a traveler has to visit each city exactly one time. State dp[mask][i] holds the minimal cost to start at some fixed city, visit the set of cities encoded in mask, and end at city i. Mask 1 << start belongs to the base case, because a route that only contains the start city has zero length. All other states are filled by transitions that add a new city to the visited set.

An example that constructs transition steps for such a route can look like this:

Nested loops scan all masks, current cities, and candidate next cities. Condition (mask & (1 << j)) != 0 makes sure that city j is not visited twice. Transition from (mask, i) to (nextMask, j) adds cost dist[i][j]. Right side of the final update keeps the smallest value seen so far for dp[nextMask][j].

Different routing problems adjust this transition pattern slightly. Some situations disallow edges between certain pairs of cities, so the code only checks dist[i][j] values that are finite. Other situations use asymmetric cost matrices where dist[i][j] differs from dist[j][i]. The same loops still apply, as long as dist holds the right values for each directed arc.

Faster iteration over candidate next cities can help when n starts to push limits. Instead of scanning all j from zero up to n - 1, one variant precomputes lists of neighbors for each city and only loops over those neighbors. Another variant precomputes masks of forbidden moves and skips those with bit tests. The table layout and transitions still follow the same structure; only the inner loop that picks j changes.

Worked Example Small Routing Problem

Small concrete numbers help connect the abstract discussion with actual values. A classic example uses four cities with a symmetric distance matrix. City 0 acts as a depot, and the route must start and end at that city while visiting cities 1, 2, and 3 exactly one time each.

A distance matrix could be written as:

Entry dist[i][j] gives the travel cost from city i to city j. Diagonal entries stay at zero because moving from a city to itself costs nothing. Off diagonal entries are symmetric in this example.

State definition follows the same pattern as in the general case. Mask encodes visited cities, and i marks the last city visited. For four cities there are 2^4 = 16 masks, from 0 to 15. Binary form of mask 1 is 0001 and means “only city 0 visited”. Mask 7 is 0111 and means “cities 0, 1, and 2 visited”. Mask 15 is 1111 and means “all cities visited”.

A compact dynamic programming core for this four city Traveling Salesman variant can look like this

This core fills the dp table by extending partial tours from mask to nextMask and then scans all fully visited states to add the final leg back to city 0. That is enough structure to support a helper method or a wrapper class that plugs in a distance matrix and reads out the final cost.

Many routing problems with more cities reuse this structure with larger n and larger matrices. Memory and time grow with 2^n, so bitmask based dynamic programming stays practical only while n remains modest, yet within that range it gives precise control over which cities are included at every step.

Bitmask DP For Scheduling And Selection

Routing is not the only family of questions that benefits from bitmask dynamic programming. Any situation where subsets of a small set carry meaning becomes a candidate. Scheduling, resource allocation, and selection with constraints are common cases.

Suppose there is a set of jobs, each with a duration and maybe a profit value. State dp[mask] can represent the best total profit that can be earned by running exactly the jobs in mask. Transition from mask to mask | (1 << j) then corresponds to adding job j to the schedule, as long as that does not break some constraint such as a deadline or a maximum calendar length.

Take this profit based scheduling core:

Arrays best and time track profit and total duration for each subset, and transitions only add jobs that stay under the time limit while improving profit for the new mask. A final scan over all masks can pick the largest value in best[mask], which corresponds to the most profitable schedule that respects the time cap.

Selection problems such as subset sum, maximum subset with mutual exclusions, or picking projects with conflicts follow a similar theme. State index mask encodes which items have been included, and dp[mask] stores a value such as total weight, cost, or profit. Constraints are enforced when transitions try to add a new item to a subset. Bitmask representation makes it easy to check overlapping resource use, mutual exclusion, or other rules with bit operations on masks that represent required or forbidden combinations.

Bitmask dynamic programming gives a compact way to walk through every subset in a controlled manner. States link directly to bit patterns, and transitions boil down to setting or testing bits while updating table entries. That structure appears in routing, scheduling, and selection problems whenever the count of elements is small enough that all subsets can be processed.

Conclusion

Bitmask dynamic programming ties bit operations and state tables into a very concrete tool for small combinatorial problems. States connect integer masks that encode subsets with positions such as a current city or job index, and transitions update those masks by flipping bits as routes, schedules, or selections grow. Routing cases with distance matrices and scheduling cases with time and profit arrays both share the same mechanical structure where masks track membership and dp entries record costs. After those mechanics feel familiar, it becomes natural to build new solutions by deciding what a mask represents, what each state stores, and how each transition adds or removes elements from the subset.

1. Java Bitwise and Shift Operators

2. Java Integer Class and bitCount Method