Decompose a range in aligned blocks of size 2^n

Question

Given an arbitrary contiguous range of positive integers, find the decomposition in the minimum number of sub-ranges of size L = 2^n, with the constraint that each range must be aligned, that is the first integer i in the sub-range must satisfy i = 0 (mod L).

Background: some (especially old) netblocks aren't a simple single CIDR, that is a range in the form 192.0.2.0/24, but are a composition of several contiguous blocks, and the whois query returns explicitly the first and last ip in the block. Try yourself with whois 220.72.0.0:

[...]
IPv4 Address       : 220.72.0.0 - 220.91.255.255 (/12+/14)
[...]

Solving this problem means finding the list of valid CIDR blocks that summed up constitute this range.

Answer 1

The following greedy algorithm works optimally:

Choose the larges block allowed which is aligned with the lower bound and does not exceed the total range. Add this range to your result set and remove it from the search space. Loop until the entire range is covered.

In the following lines I took your example and simplified it to the interesting part, i.e. take the range 72-91:

0)  Range: 72 - 91 (Size 20)

1a) Largest block size allowed @72: 8
1b) Subrange #1: 72 - 79
1c) Remaining: 80 - 91 (Size 12)

2a) Largest  block size allowed @80: 16 (exceeds size) -> 8
2b) Subrange #2: 80 - 87
2c) Remaining: 88 - 91 (Size 4)

3a) Largest  block size allowed @88: 8 (exceeds size) -> 4
3b) Subrange #3: 88 - 91
3c) Remaining: empty

Result: (72-79) (80-87) (88-91)

The structure can be seen even better, if we express the numbers in binary format.

0)  Range: 01001000, Size 10100

1a) Largest block size allowed @01001000: 1000
1b) Subrange #1: 01001000, Size 1000
1c) Remaining: 01010000, Size 1100

2a) Largest block size allowed @01010000: 10000 (exceeds size) -> 1000
2b) Subrange #2: 01010000, Size 1000
2c) Remaining: 01011000, Size 100

3a) Largest  block size allowed @01011000: 1000 (exceeds size) -> 100
3b) Subrange #3: 01011000, Size 100
3c) Remaining: empty

A note for implementation: the block size for the subrange to be chosen corresponds either to the rightmost 1 bit of the lower bound or the leftmost 1 bit of the size of the range (whichever is smaller).