Ip to cidr

String Bit Manipulation

53.7% acceptance

Mar 31, 2026

117

366

An IP address is a formatted 32-bit unsigned integer where each group of 8 bits is printed as a decimal number and the dot character '.' splits the groups. For example, the binary number 00001111 10001000 11111111 01101011 (spaces added for clarity) formatted as an IP address would be "15.136.255.107". A CIDR block is a format used to denote a specific set of IP addresses. It is a string consisting of a base IP address, followed by a slash, followed by a prefix length k. The addresses it covers are all the IPs whose first k bits are the same as the base IP address. For example, "123.45.67.89/20" is a CIDR block with a prefix length of 20. Any IP address whose binary representation matches 01111011 00101101 0100xxxx xxxxxxxx, where x can be either 0 or 1, is in the set covered by the CIDR block. You are given a start IP address ip and the number of IP addresses we need to cover n. Your goal is to use as few CIDR blocks as possible to cover all the IP addresses in the inclusive range [ip, ip + n - 1] exactly. No other IP addresses outside of the range should be covered. Return the shortest list of CIDR blocks that covers the range of IP addresses. If there are multiple answers, return any of them.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn ip_to_cidr(ip: String, n: i32) -> Vec<String> {
    let parts: Vec<u32> = ip.split('.').map(|x| x.parse().unwrap()).collect();
    let mut start: u32 =
      (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3];
    let mut remaining = n as u32;
    let mut result = Vec::new();
    while remaining > 0 {
      let low_bit = start & start.wrapping_neg();
      let mut block = if low_bit == 0 { 1u32 << 31 } else { low_bit };
      while block > remaining {
        block >>= 1;
      }
      let prefix = 32 - block.trailing_zeros();
      result.push(format!(
        "{}.{}.{}.{}/{}",
        (start >> 24) & 0xFF,
        (start >> 16) & 0xFF,
        (start >> 8) & 0xFF,
        start & 0xFF,
        prefix
      ));
      start = start.wrapping_add(block);
      remaining -= block;
    }
    result
  }
}