Bit manipulation and interval problems

Two small topics close this part of the series, because they are short, common in interviews and easy to get subtly wrong: bit manipulation and interval problems. The code and output below were run with Python 3 before publishing.

Part 1: bit tricks worth knowing

XOR (^): a ^ a = 0 and a ^ 0 = a. XOR every number in a list where all values appear twice except one, and only the single one is left.
n & (n - 1) clears the lowest set bit. Repeat it to count the 1-bits in a number, or check for a power of two: a positive number is a power of two if it has exactly one set bit, so n & (n - 1) == 0.
Bitmasks represent a set of up to about 20 items as the bits of an integer. Looping mask from 0 to 2^n - 1 visits every subset.
Shifts: 1 << i makes a number with only bit i set, and x >> i & 1 reads bit i.

Part 2: interval patterns

Merge intervals. Sort by start. Walk through: if the next interval starts before or at the end of the last merged one, extend it, otherwise start a new one. Cost: O(n log n).
Minimum meeting rooms. Sort by start. Keep a min-heap of the end times of rooms in use. If the earliest end is at or before the new start, reuse that room, otherwise add a room. The heap size at the end is the answer.

Code

import heapq

def single_number(nums):                 # every value appears twice except one
    x = 0
    for n in nums:
        x ^= n
    return x

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

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

def subsets(items):
    return [[items[i] for i in range(len(items)) if mask >> i & 1] for mask in range(1 << len(items))]

def merge_intervals(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

def min_meeting_rooms(intervals):
    ends = []                            # min-heap of end times of rooms in use
    for start, end in sorted(intervals):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)

Real output

single number: 4
bits in 13 (1101): 3 | 255: 8
power of two: [1, 2, 4, 8, 16, 32]
subsets of [a,b,c]: [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]
merge: [[1, 6], [8, 10], [15, 20]]
rooms: 2 | back-to-back: 1
all checks passed

merge_intervals turned [1,3], [2,6] into [1,6] and [15,18], [17,20] into [15,20]. For the meetings (0,30), (5,10), (15,20) two rooms are needed, and for back-to-back meetings (0,5), (5,10) one room is enough because a meeting that ends at 5 frees the room for one that starts at 5. Whether touching intervals merge is a decision the problem must state, so always ask. The bit functions were checked against Python's bin(n).count("1") on 300 random numbers, and merge_intervals against a brute-force coverage check on 300 random sets.

Common mistakes

Operator precedence. In C, C++ and JavaScript, == binds tighter than &, so n & (n - 1) == 0 means n & ((n - 1) == 0). Python happens to read it as you expect, but write the parentheses anyway: (n & (n - 1)) == 0.
Forgetting n > 0 in the power-of-two check, which wrongly accepts 0.
Using bitmasks for more than about 20 items: 2^n grows too fast.
Not sorting the intervals first.
Forgetting the boundary rule (do [1,2] and [2,3] merge?) or the case of an interval fully inside another, which max handles.
Mutating the input list when the caller does not expect it.

Main idea: XOR cancels pairs, n & (n - 1) clears the lowest bit, and a bitmask enumerates subsets. For intervals, sort by start, merge as you walk, and use a min-heap of end times for rooms.

Interview prep and DSA series, Part 3 (more algorithms): 5 of 5. Previous: Greedy algorithms: interval scheduling and when greedy fails.