~/problems / Bit manipulation

Basics: IPv4 addresses as 32-bit integers

easy basics ~10 min

An IPv4 address like "192.168.1.10" is really one 32-bit number: the four octets are its four bytes, most significant first. Almost every IP/CIDR problem starts by converting to that number, doing the work with shifts and masks, and converting back.

Write three functions, using shifts (<<, >>), masks (&, |) and no ipaddress module:

  1. ip_to_int(ip: str) -> int: "a.b.c.d" becomes a·2^24 + b·2^16 + c·2^8 + d.
  2. int_to_ip(n: int) -> str: the reverse, for 0 <= n < 2^32.
  3. cidr_range(block: str) -> tuple[int, int]: for a block "a.b.c.d/k", the first and last address it contains, as integers. The block is every address whose top k bits match a.b.c.d, so it has 2^(32-k) addresses. The low 32 - k bits of the given address may be non-zero; ignore them.
ip_to_int("0.0.1.2")             # 258        (1 << 8 | 2)
ip_to_int("192.168.1.10")        # 3232235786
int_to_ip(3232235786)            # "192.168.1.10"
int_to_ip(0)                     # "0.0.0.0"
cidr_range("10.1.2.3/24")        # (ip_to_int("10.1.2.0"), ip_to_int("10.1.2.255"))
cidr_range("0.0.0.0/0")          # (0, 4294967295)
cidr_range("8.8.8.8/32")         # (ip_to_int("8.8.8.8"), ip_to_int("8.8.8.8"))

Constraints: every octet is 0..255 with no leading zeros; 0 <= k <= 32.

Show hint

Build the int with n = (n << 8) | octet, read octet i back with (n >> (24 - 8 * i)) & 0xFF, and a /k block has size 1 << (32 - k), so its first address is ip & ~(size - 1) (masked to 32 bits) and its last is first + size - 1.

Topic: Bit manipulation (IP / CIDR). IPv4 as a 32-bit int; lowest set bit for block sizes.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc