Bit Manipulation Example: Which Toppings Two Pizza Orders Share

Eight toppings fit in eight bits, so an order is one number, and shared, combined and differing toppings are one operator each.

A bitmask stores a set of a few options as one integer, one bit per option, so that comparing two sets takes one operator. A pizza shop offers eight toppings, and an order holds any of them. Nothing in the question mentions bits: the cue is that each topping is either in an order or not, and there are few enough to fit in one integer. Each topping gets a bit position:

Toppings and their bits
Topping	Bit
cheese	0
mushroom	1
onion	2
olive	3
pepper	4
ham	5
basil	6
chilli	7

Order A has cheese, mushroom, olive and pepper, bits 0, 1, 3 and 4, so it is 1 + 2 + 8 + 16 = 27. Order B has mushroom, onion and pepper, so it is 2 + 4 + 16 = 22. The toppings both orders share are A AND B, the toppings in either are A OR B, and the toppings in exactly one are A XOR B. The trace shows each as eight bits, chilli on the left and cheese on the right.

Two orders and their comparisons, as eight bits

Inputorder A 27, order B 22

Order A = 27
1. 0
2. 0
3. 0
4. 1
5. 1
6. 0
7. 1
8. 1
Order A: cheese, mushroom, olive and pepper
Order B = 22
1. 0
2. 0
3. 0
4. 1
5. 0
6. 1
7. 1
8. 0
Order B: mushroom, onion and pepper
A AND B = 18
1. 0
2. 0
3. 0
4. 1
5. 0
6. 0
7. 1
8. 0
AND: mushroom and pepper, the toppings both share
A OR B = 31
1. 0
2. 0
3. 0
4. 1
5. 1
6. 1
7. 1
8. 1
OR: the five toppings in either order
A XOR B = 13
1. 0
2. 0
3. 0
4. 0
5. 1
6. 1
7. 0
8. 1
XOR: cheese, onion and olive, each in one order only

ResultShared 18, either 31, exactly one 13.

The bit tricks add, remove and test one topping. The listing builds both masks from names, prints each comparison with the names it holds, then adds ham to A, removes olive from it and tests it for basil.

toppings.pypy

TOPPINGS = ["cheese", "mushroom", "onion", "olive", "pepper", "ham", "basil", "chilli"]


def mask_of(names: list[str]) -> int:
    mask = 0
    for name in names:
        mask |= 1 << TOPPINGS.index(name)
    return mask


def names_in(mask: int) -> list[str]:
    return [name for bit, name in enumerate(TOPPINGS) if (mask >> bit) & 1]


order_a = mask_of(["cheese", "mushroom", "olive", "pepper"])
order_b = mask_of(["mushroom", "onion", "pepper"])
print("order A:", order_a, "order B:", order_b)
print("both orders:", order_a & order_b, *names_in(order_a & order_b))
print("either order:", order_a | order_b, *names_in(order_a | order_b))
print("exactly one:", order_a ^ order_b, *names_in(order_a ^ order_b))
print("A with ham:", order_a | (1 << TOPPINGS.index("ham")))
print("A without olive:", order_a & ~(1 << TOPPINGS.index("olive")))
print("basil in A:", (order_a >> TOPPINGS.index("basil")) & 1)

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

order A: 27 order B: 22
both orders: 18 mushroom pepper
either order: 31 cheese mushroom onion olive pepper
exactly one: 13 cheese onion olive
A with ham: 59
A without olive: 19
basil in A: 0

A with ham is 59, A without olive is 19, and basil is not in A. Every operation is O(1) on a mask of up to 64 options in a Java long, and a Python integer holds any number. A hash set holds the same kind of set with no limit on its size, and the Hash Map Patterns topic uses one; a mask wins when the options are few and fixed, and when sets of them are compared or stored many times.

Algorithms

← → move through sections and cards