## IP to CIDR

• Time:O(\log n)
• Space:O(\log n)

## C++

``````class Solution {
public:
vector<string> ipToCIDR(string ip, int n) {
vector<string> 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;
}

// return max 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;
}
};
``````

## JAVA

``````class Solution {
public List<String> ipToCIDR(String ip, int n) {
List<String> 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);
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;
}

// return max 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();
}
}
``````

## Python

``````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

# return max i s.t. 2^i < n
def _maxLow(self, n: int) -> Optional[int]:
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)

# e.g. count = 8 = 2^3 . prefix = 32 - 3 = 29
#      count = 1 = 2^0 . prefix = 32 - 0 = 32
def _getPrefix(self, count: int) -> Optional[int]:
for i in range(32):
if count == 1 << i:
return 32 - i
``````