# 751. IP to CIDR¶

• Time: $O(\log n)$
• Space: $O(\log n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 class Solution { public: vector ipToCIDR(string ip, int n) { vector ans; long num = getNum(ip); while (n > 0) { const long lowbit = num & -num; const long count = lowbit == 0 ? maxLow(n) : firstFit(lowbit, n); ans.push_back(getCIDR(num, getPrefix(count))); n -= count; num += count; } return ans; } private: long getNum(const string& ip) { istringstream iss(ip); long num = 0; for (string token; getline(iss, token, '.');) num = num * 256 + stol(token); return num; } // Returns the maximum i s.t. 2^i < n. int maxLow(int n) { for (int i = 0; i < 32; ++i) if (1 << i + 1 > n) return 1 << i; throw; } long firstFit(long lowbit, long n) { while (lowbit > n) lowbit >>= 1; return lowbit; } string getCIDR(long num, long prefix) { const long d = num & 255; num >>= 8; const long c = num & 255; num >>= 8; const long b = num & 255; num >>= 8; const long a = num & 255; return to_string(a) + '.' + to_string(b) + '.' + to_string(c) + '.' + to_string(d) + '/' + to_string(prefix); } // e.g. count = 8 = 2^3 -> prefix = 32 - 3 = 29 // count = 1 = 2^0 -> prefix = 32 - 0 = 32 int getPrefix(long count) { for (int i = 0; i < 32; ++i) if (count == 1 << i) return 32 - i; throw; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 class Solution { public List ipToCIDR(String ip, int n) { List ans = new ArrayList<>(); long num = getNum(ip.split("\\.")); while (n > 0) { final long lowbit = num & -num; final long count = lowbit == 0 ? maxLow(n) : firstFit(lowbit, n); ans.add(getCIDR(num, getPrefix(count))); n -= (int) count; num += count; } return ans; } private long getNum(String[] x) { long num = 0; for (int i = 0; i < 4; ++i) num = num * 256 + Long.parseLong(x[i]); return num; } // Returns the maximum i s.t. 2^i < n. private int maxLow(int n) { for (int i = 0; i < 32; ++i) if (1 << i + 1 > n) return 1 << i; throw new IllegalArgumentException(); } private long firstFit(long lowbit, long n) { while (lowbit > n) lowbit >>= 1; return lowbit; } private String getCIDR(long num, long prefix) { final long d = num & 255; num >>= 8; final long c = num & 255; num >>= 8; final long b = num & 255; num >>= 8; final long a = num & 255; return new StringBuilder() .append(a) .append(".") .append(b) .append(".") .append(c) .append(".") .append(d) .append("/") .append(prefix) .toString(); } // e.g. count = 8 = 2^3 -> prefix = 32 - 3 = 29 // count = 1 = 2^0 -> prefix = 32 - 0 = 32 private int getPrefix(long count) { for (int i = 0; i < 32; ++i) if (count == 1 << i) return 32 - i; throw new IllegalArgumentException(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution: def ipToCIDR(self, ip: str, n: int) -> List[str]: ans = [] num = self._getNum(ip.split('.')) while n > 0: lowbit = num & -num count = self._maxLow(n) if lowbit == 0 else self._firstFit(lowbit, n) ans.append(self._getCIDR(num, self._getPrefix(count))) n -= count num += count return ans def _getNum(self, x: List[str]) -> int: num = 0 for i in range(4): num = num * 256 + int(x[i]) return num def _maxLow(self, n: int) -> Optional[int]: """Returns the maximum i s.t. 2^i < n.""" for i in range(32): if 1 << i + 1 > n: return 1 << i def _firstFit(self, lowbit: int, n: int) -> int: while lowbit > n: lowbit >>= 1 return lowbit def _getCIDR(self, num: int, prefix: int) -> str: d = num & 255 num >>= 8 c = num & 255 num >>= 8 b = num & 255 num >>= 8 a = num & 255 return '.'.join([str(s) for s in [a, b, c, d]]) + '/' + str(prefix) def _getPrefix(self, count: int) -> Optional[int]: """ e.g. count = 8 = 2^3 . prefix = 32 - 3 = 29 count = 1 = 2^0 . prefix = 32 - 0 = 32 """ for i in range(32): if count == 1 << i: return 32 - i