CIDR Subnet Report

1. Background Knowledge

IPv4 addresses are 32-bit integers, typically represented in dotted-decimal notation (e.g., 192.168.1.1). A CIDR (Classless Inter-Domain Routing) block is defined by an IP address and a prefix length $p$ (e.g., /24). The prefix length indicates how many leading bits constitute the network portion, while the remaining $32 - p$ bits constitute the host portion.

The netmask is a 32-bit integer with the first $p$ bits set to 1 and the remaining bits set to 0. It acts as a filter to isolate the network portion of any IP address within that block. The network address is the lowest address in the block, obtained by performing a bitwise AND between any IP in the block and the netmask. The broadcast address is the highest address, obtained by setting all host bits to 1.

Membership in a subnet is determined by checking if the network portion of a candidate IP matches the subnet's network address. Specifically, an IP x belongs to the subnet if (x & mask) == network_address. Usable host counts depend on the prefix length: for $p \le 30$, it is $2^{32-p} - 2$ (excluding network and broadcast addresses). Special cases exist for $/31$ (2 usable) and $/32$ (1 usable) per RFC standards.

2. Algorithm Approach

The core approach relies on integer bit manipulation. Since Python handles arbitrarily large integers, we can treat IPv4 addresses as standard 32-bit integers. The algorithm involves three main phases:

1. Parsing: Convert the CIDR string and list of IPs into their integer representations.
2. Mask Calculation: Compute the netmask integer based on the prefix length $p$.
3. Derivation: Use bitwise operations (&, |, ~) to derive the network address, broadcast address, and check membership for each IP.

This approach avoids string parsing complexities during calculation and leverages efficient bitwise operators.

3. Step-by-Step Strategy

1. Helper Function: Create a helper to convert dotted-quad strings (e.g., "10.0.0.1") to integers. Split by ., convert each octet to int, and combine using bitwise shifts: a << 24 | b << 16 | c << 8 | d.
2. Parse CIDR: Split the input cidr string by / to get the base IP and prefix length $p$. Convert the base IP to an integer.
3. Compute Netmask:

• If $p == 0$, mask is 0.
• Otherwise, mask is (0xFFFFFFFF << (32 - p)) & 0xFFFFFFFF. This creates $p$ ones followed by zeros.

4. Derive Network Address: Perform network = ip_int & mask.
5. Derive Broadcast Address: The host bits are the inverse of the mask. broadcast = network | (~mask & 0xFFFFFFFF). Alternatively, broadcast = network | (mask ^ 0xFFFFFFFF).
6. Calculate Usable Hosts:

• If $p == 32$, return 1.
• If $p == 31$, return 2.
• Otherwise, return $2^{32-p} - 2$.

7. Check Membership: For each IP in ips:

• Convert IP to integer.
• Check if (ip_int & mask) == network.
• Store the boolean result.

8. Format Output: Convert the integer network, broadcast, and mask back to dotted-quad strings. Construct the final dictionary.

4. Common Pitfalls

• Sign Extension: In Python, integers are signed. When shifting or inverting masks, ensure you mask with 0xFFFFFFFF to keep values within 32-bit unsigned range. For example, ~mask will produce a negative number; ~mask & 0xFFFFFFFF corrects this.
• Prefix Edge Cases: Do not blindly apply $2^{32-p} - 2$. You must explicitly handle $/31$ and $/32$ prefixes as specified in the problem description.
• Non-Network Input IPs: The input CIDR IP (e.g., 10.0.5.37/22) is not necessarily the network address. Always compute the network address via ip & mask rather than assuming the input IP is the start of the block.
• String Conversion: When converting integers back to dotted-quad strings, ensure you extract octets correctly using shifts and masks (e.g., (ip >> 24) & 0xFF for the first octet).

5. Time & Space Complexity

• Time Complexity: $O(N)$, where $N$ is the number of IPs in the ips list. Parsing the CIDR and computing the mask is $O(1)$. Each IP check involves constant-time bitwise operations.
• Space Complexity: $O(N)$ to store the in_subnet list of booleans. The auxiliary space for integers and strings is $O(1)$.