IP to CIDR
Problem
Given a starting IP address and the number n of consecutive addresses to cover, return the minimum list of CIDR blocks that exactly cover [ip, ip + n).
ip="255.0.0.7", n=10["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]def ipToCIDR(ip, n):
parts = list(map(int, ip.split('.')))
start = (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3]
res = []
while n > 0:
low = start & -start if start else (1 << 32)
size = 1
while size * 2 <= n and (size * 2) <= low:
size *= 2
bits = 0
s = size
while s > 1: bits += 1; s >>= 1
prefix = 32 - bits
a, b, c, d = (start >> 24) & 255, (start >> 16) & 255, (start >> 8) & 255, start & 255
res.append(f"{a}.{b}.{c}.{d}/{prefix}")
start += size
n -= size
return resfunction ipToCIDR(ip, n) {
const p = ip.split('.').map(Number);
let start = (p[0] * 2**24) + (p[1] << 16) + (p[2] << 8) + p[3];
const res = [];
while (n > 0) {
const low = start === 0 ? 2**32 : (start & -start);
let size = 1;
while (size * 2 <= n && size * 2 <= low) size *= 2;
let bits = 0, s = size;
while (s > 1) { bits++; s >>= 1; }
const a = Math.floor(start / 2**24) & 255, b = (start >> 16) & 255, c = (start >> 8) & 255, d = start & 255;
res.push(`${a}.${b}.${c}.${d}/${32 - bits}`);
start += size; n -= size;
}
return res;
}class Solution {
public List<String> ipToCIDR(String ip, int n) {
String[] p = ip.split("\\.");
long start = (Long.parseLong(p[0]) << 24) | (Long.parseLong(p[1]) << 16) | (Long.parseLong(p[2]) << 8) | Long.parseLong(p[3]);
List<String> res = new ArrayList<>();
while (n > 0) {
long low = start == 0 ? (1L << 32) : (start & -start);
long size = 1;
while (size * 2 <= n && size * 2 <= low) size *= 2;
int bits = 0; long s = size;
while (s > 1) { bits++; s >>= 1; }
long a = (start >> 24) & 255, b = (start >> 16) & 255, c = (start >> 8) & 255, d = start & 255;
res.add(a + "." + b + "." + c + "." + d + "/" + (32 - bits));
start += size; n -= size;
}
return res;
}
}class Solution {
public:
vector<string> ipToCIDR(string ip, int n) {
long a, b, c, d; sscanf(ip.c_str(), "%ld.%ld.%ld.%ld", &a, &b, &c, &d);
long start = (a << 24) | (b << 16) | (c << 8) | d;
vector<string> res;
while (n > 0) {
long low = start == 0 ? (1L << 32) : (start & -start);
long size = 1;
while (size * 2 <= n && size * 2 <= low) size *= 2;
int bits = 0; long s = size;
while (s > 1) { bits++; s >>= 1; }
res.push_back(to_string((start>>24)&255) + "." + to_string((start>>16)&255) + "." + to_string((start>>8)&255) + "." + to_string(start&255) + "/" + to_string(32 - bits));
start += size; n -= size;
}
return res;
}
};Explanation
We must cover n consecutive IP addresses with the fewest CIDR blocks. A CIDR block is always a power-of-two run of addresses that must also be aligned to its own size. The strategy is greedy: at each step grab the biggest legal block that starts where we are and still fits in what is left.
First we turn the dotted IP into a single 32-bit integer start. Two limits decide the block size. The alignment limit is low = start & -start, the value of the lowest set bit, which is the largest power-of-two block that can legally begin at start. The remaining-count limit is n itself. We double size while it stays under both.
From size we derive the prefix length: a block of 2^bits addresses has prefix 32 - bits. We record the CIDR string, then advance start by size and shrink n by size, repeating until n hits zero.
Example: ip = "255.0.0.7", n = 10. The start ...7 is odd, so only a size-1 block aligns there, giving 255.0.0.7/32. Now at ...8 we can fit an 8-address block, 255.0.0.8/29. One address remains at ...16, giving 255.0.0.16/32.
Each block at least doubles the progress when alignment allows, so the number of blocks stays logarithmic in n.