751. IP to CIDR - cocoder39/coco39_LC GitHub Wiki

751. IP to CIDR

You should know about one’s complement(反码) and two's complement(补码)
https://stackoverflow.com/questions/2604296/twos-complement-why-the-name-two
(-x) is the two’s complement of x. (-x) will be equal to one’s complement of x plus 1.
for example:

7  in binary              :  00000111
one’s complement of 7     :  11111000
two's complement of 7     :  11111001
x & (-x) of 7             :  00000001

So the value of x & (-x) can mean for 255.0.0.7, how many more ips we can represent in CIDR. In this case it's only 1.(because x & (-x) of 7 is 1)
for example, 255.0.0.8, x & (-x) of it is 00001000, it's 8, we can represent 8 more ips which start from it.
for 255.0.0.9, x & (-x) of it is 00000001, 1 again.
So for input: 255.0.0.7 and 10 ips, we should have results:

2. edge case 0.0.0.0/32 x & (-x) = 0 & (-1) = 0

class Solution:
    def ipToCIDR(self, ip: str, n: int) -> List[str]:
        slots = ip.split('.')
        base10 = 0
        for i in range(4):
            base10 = base10 * 256 + int(slots[i])
        
        res = []
        while n > 0:
            if base10 == 0:
                res.append("0.0.0.0/32")
                n -= 1
                base10 += 1
                continue
                
            count = base10 & (-base10)
            while count > n:
                count //= 2

            res.append(self.getCIDR(base10, count))
            n -= count
            base10 += count
        return res
    
    def getCIDR(self, base10: int, count: int) -> str:
        blocks = []
        for i in range(4):
            blocks.append(str(base10 & 255))
            base10 >>= 8
        blocks.reverse()
        
        length = 0
        while count > 1:
            count //= 2
            length += 1
            
        return '.'.join(blocks) + '/' + str(32 - length)