How 12306 Ticket‑Booking Uses Bitmap & Bitwise Operations to Prevent Overbooking

Introduction

Everyone has experienced the frantic race for train tickets at year‑end, but few know the algorithm behind it. This article walks through a simple yet powerful bitmap‑based solution for the 12306 ticket‑booking system.

Bitmap and Bitwise Operations

Redis bitmap usage is assumed known; readers can refer to existing tutorials for basics. The core idea is to revisit bitwise operations, which are illustrated in the following diagram:

12306 Ticket‑Grabbing Algorithm Details

Using the Beijing‑to‑Xi'an high‑speed train as an example, we simplify the problem: a seat is considered available only if none of the intermediate segments between the start and destination are already booked.

Assume the train has 4 seats.

The route has 4 stations, forming three segments: Beijing→Shijiazhuang, Shijiazhuang→Zhengzhou, Zhengzhou→Xi'an.

Step 1: Build an Empty Bitmap for Each Segment

Each segment gets a bitmap where 0 means the seat is free and 1 means it is taken.

Step 2: Book a Ticket from Beijing to Xi'an

If a passenger is assigned seat 1, we set the bits for all three segments of that seat to 1, indicating the seat is fully occupied for the whole journey.

Step 3: Book a Ticket from Shijiazhuang to Xi'an

Suppose seat 2 is allocated. We set the bits for the last two segments (Shijiazhuang→Zhengzhou and Zhengzhou→Xi'an) of seat 2 to 1.

Step 4: Determine Remaining Tickets

To find how many seats are still free for a given interval, we perform a bitwise OR across the bitmaps of the involved segments. The result contains a 0 for each seat that remains completely free; counting the zeros yields the number of available tickets.

Summary

The key to solving the ticket‑availability problem lies in constructing per‑segment bitmaps. Because a seat becomes unavailable as soon as any intermediate segment is booked (bit set to 1), a simple OR operation across the relevant segment bitmaps instantly reveals which seats are still free. While the example uses only four bits for clarity, a real‑world system would allocate a bitmap length equal to the total number of seats on the train.