First, we need to confirm what CIDR is? CIDR represents a classless inter-domain routing, usually in the form of an IP address followed by a slash and a number, such as 192.168.1.0/24. This number represents the number of bits in the network prefix, and the remaining number of bits is used for the host address. The role of CIDR is to allocate IP addresses more efficiently and reduce waste.
We now want to implement, convert the given start and end IP into CIDR blocks. So, how do you find the CIDR that overwrites them from two IP addresses? It may be necessary to decompose into multiple CIDR blocks, as a single CIDR may not cover the entire range, especially if the range is not a continuous power of 2.
1. The following points need to be considered
Convert IP address to integer: IPv4 addresses are 32 bits, and each part can be converted into binary and then combined into a long integer, which is easy to calculate. For example, 192.168.1.0 is converted to integers is 3232235776.
Determine the integer form of the start and end IP: the input string needs to be split into four parts, each part is converted into an integer, and the displacement is combined into a long integer.
Calculate the CIDR block: Starting from the start address, find the largest prefix length (i.e. the smallest subnet) so that the subnet is included in the start and end ranges. Then, increment the start address to the start address of the next subnet, repeating the process until the entire range is covered.
The key step here is how to find every possible CIDR block. For example, suppose the starting IP is 192.168.0.0 and the ending IP is 192.168.3.255. This range can be decomposed into 192.168.0.0/23 or 192.168.0.0/24 and 192.168.1.0/24 and 192.168.2.0/23, etc., but the most suitable decomposition method needs to be found.
2. Possible algorithm steps
- Converts the start and end IPs to long integers.
- If the start IP is greater than the end IP, then they are swapped.
- Initialize a list to save the CIDR block.
- Loop until the start IP exceeds the end IP:
- Calculate the lowest significant bit of the starting IP (i.e. the number of digits with the largest suffix 0), which determines the maximum CIDR block currently possible.
- At the same time, determine the size of the current block, and do not exceed the end IP.
- Determine the number of mask bits that can actually be used so that the subnet does not exceed the end IP.
- Add CIDR blocks to the list.
- Add the starting IP to the current block size and continue processing.
It should be noted here that the CIDR block found each time should be the largest possible block to reduce the number of blocks. For example, if the starting IP is 192.168.0.0 and the ending IP is 192.168.0.255, then the CIDR is /24. But if the end IP is 192.168.1.127, it may need to be decomposed into multiple blocks, such as /24 and /25, etc.
When implemented in Java, large integers need to be processed because IPv4 is 32 bits, and long types can be used to avoid symbolic problems. At the same time, the calculation of the mask may require bit operations, such as finding the longest common prefix.
In addition, some special situations need to be handled, such as the start and end IPs are the same, and the CIDR is /32 at this time. Or the starting IP to end IP is a continuous block, but cannot be covered by one CIDR and needs to be split into multiple.
For example, the starting IP is 192.168.0.5 and the ending IP is 192.168.0.7. At this time, the CIDR list should be 192.168.0.5/32, 192.168.0.6/31, or a similar combination. But it is necessary to ensure that the IP range covered by each CIDR block is between the start and the end.
3. Java program implementation steps
Now, you need to convert these logic into Java code, and the following steps are required:
- Write a method to convert an IP string to a long integer.
- Write a method to convert long integers back to IP strings.
- Write a method to calculate a list of CIDR blocks between two IPs.
When converting IP to long integers, you need to shift each part to the corresponding number of bits left, for example, the first part shifts left by 24 bits, the second one shifts left by 16 bits, and so on. At the same time, make sure that the value of each part is between 0-255.
When calculating the CIDR block, it is necessary to find the maximum number of mask bits so that the start address plus the block size of the subnet does not exceed the end IP. The block size is 2^(32 - mask), so you need to find the largest mask so that start + size <= end + 1. Alternatively, another way is to find the lowest significant bit of the starting IP and then gradually adjust the number of mask bits.
3.1 How to calculate mask?
The difference from start to end can be calculated as diff = end - start +1. Then, the largest block is the largest power of 2, not greater than diff, and the size of the block also needs to be considered whether the low bit of start is 0.
Alternatively, find the lowest significant bit starting from start, for example, calculate the position of 1 of the lowest bit in the binary of start, and then the size of the block is 2^that position, but cannot exceed end - start +1.
For example, if the binary of start is x, then the largest block size is the largest power of 2, such that the block size is <= diff, and the block size is the value represented by the lowest bit 1 in the binary of start.
For example, suppose start is 192.168.0.5 (converted to integer is 3232235525), and the binary is…00000101. The position of the lowest bit of 1 is 0 (because the last bit is 1), so the block size is 1, that is, the mask is 32. In this way, the block only contains start itself. But if the diff is greater than 1, then the next block may be larger afterwards.
Or, this may not be the optimal way. The correct way to do this should be to find the largest mask so that the start address covered by the subnet is start, and the end address of the subnet does not exceed end.
This may require calculating the network address of the subnet and then finding the largest mask so that the broadcast address of the subnet does not exceed the end.
For example, the network address of the subnet is start & mask, and the broadcast address is network | (~mask & 0xFFFFFFFL). So you need to ensure that the broadcast address is <= end.
But this process may be more complicated. Therefore, another approach may be needed:
For the current start, try to find the largest mask so that the corresponding block size of the mask (i.e. 2^(32 - mask)) makes start + block_size -1 <= end.
At the same time, mask must meet the start binary, and the last (32-mask) bits must all be 0, otherwise the start address of the subnet is not start, but a smaller address.
For example, if start is 192.168.0.5 and mask is 24, the start address of the subnet is 192.168.0.0, and start is not at the start address of the subnet, so the mask is 24 cannot be used. Therefore, the largest mask must be found so that start is the start address of the subnet, that is, the last (32-mask) bit of start must be 0.
Therefore, the correct steps should be:
Calculate the number of digits with the largest suffix 0 starting from start. This can be calculated by calculating the position of the lowest bit 1 of start. For example, if there are n suffixes 0 in the binary of start, then the largest mask is 32 - n. At this time, the block size is 2^n. For example, start is 192.168.0.0 (i.e.…00000000), then n is 8, mask is 24, and block size is 256.
But if start is 192.168.0.128 and the binary is...10000000, then the number of digits with the suffix 0 is 7, so the mask is 25 and the block size is 128. At this time, the subnet is 192.168.0.128/25 and the broadcast address is 192.168.0.255.
However, if the end is 192.168.0.255, then this block can be included. But if end is a smaller value, such as 192.168.0.200, then the mask needs to be adjusted so that the block size does not exceed end - start +1.
Therefore, the determination of mask should be:
mask = 32 - (lowBit, log2(remainingSize))
where lowBit is the lowest bit 1 of start, and remainingSize is end - start +1.
Or, another way is:
mask = 32 - (lowBit, 32 - (int)((remainingSize)/(2)))
However, the way lowBit needs to be calculated correctly. For example, for the binary of start, find the rightmost 1 position. For example, the binary of start is...0001000, then lowBit is 3 (counting from 0), that is, 2^3=8. So the size of the block is 8 and the mask is 32 -3 =29.
3.2 How to calculate lowBit?
You can use bit operations to find the rightmost position of 1. For example, for a long type start, take the value start & -start, which will get a number with only the rightmost 1 and then calculate log2.
For example, start & -start can get a number where only the rightmost 1 is preserved. For example, start is 5 (binary 101), and the result of start & -start is 1 (binary 1), so log2(1)=0, that is, lowBit=0. At this time, the size of the block is 1, mask=32-0=32.
If start is 8 (binary 1000), start & -start=8, log2(8)=3, so lowBit=3, the size of the block is 8, mask=29.
So, lowBit = log2(start & -start). But how to calculate log2? You can use bit operations or move the rightward in a loop.
In Java, you can use the () method, which returns the number of 0 after the lowest bit 1 in binary. For example, for 8 (1000), numberOfTrailingZeros is 3. At this time, lowBit is this value, that is, the size of the block is 1 << lowBit.
But does this approach work for all cases?
Assuming start is 0, then start & -start is 0, which may be problematic. But start is somewhere between the start and the end here, so it may not be 0?
But the starting IP may be 0, for example 0.0.0.0 to 0.0.0.255. At this time, lowBit is 8, the size of the block is 256, and the mask is 24.
So, the calculation of lowBit should be:
long diff = start & -start;
If diff ==0, then lowBit =32? Or how to deal with it?
Alternatively, another way, use (startIpLong) to obtain the number of 0s after the lowest bit 1. For example, for startIpLong=8 (binary 1000), this method returns 3 because there are 3 0s at the end. At this time, the size of the block is 1 << 3 =8.
So, lowBit = (startIpLong | 0xFFFFFFF00000000L)? Not sure, it may require careful testing.
Or, for IPv4's 32-bit value, startIpLong is a 32-bit value, stored in the high 32-bit or the low 32-bit of the long type? It may depend on whether the conversion method is correct. For example, whether the previous conversion function correctly converts IP to a long integer, such as shifting the first eight to a high bit.
For example, the way IP addresses are converted to long integers is: a<<24 | b<<16 | c<<8 | d. In this way, is the 32 bits of IPv4 placed in the high 32 bits or the low 32 bits of long?
Assuming the conversion is correct, for 192.168.0.5, the conversion to a long integer is (192 <<24) | (168<<16) | (0<<8) |5 = 3232235525. Binary representation is:
11000000 10101000 00000000 00000101
Here, the lowest bit 1 is in bit 0 (the last byte is 00000101, and the lowest bit is 1). Therefore, (3232235525) should be 0, because the lowest bit is 1 and there is no 0 afterwards. So the size of the block is 1 and the mask is 32-0=32.
In this way, the size of each block is determined by the position of the lowest bit 1 of start, but it is also necessary to ensure that the size of the block does not exceed the remaining address space (i.e. end - start +1).
3.3 To summarize, the steps are as follows
Convert startIp and endIp to long integers s and e, making sure s <=e.
Initialize the result list.
When s <= e, loop:
- a. Calculate the position of the lowest bit 1 of the current s and get lowBit = (s).
- b. Possible block size maxSize = 1 << lowBit.
- c. But maxSize cannot exceed e - s +1, so the actual block size is (maxSize, e -s +1).
- d. At this time, you need to find the largest mask so that the block size is actualSize. Because actualSize must be a power of 2, mask = 32 - log2(actualSize).
- e. So, mask = 32 - (int)((actualSize)/(2)).
- f. Add CIDR block to result list: IP/mask.
- g. s += actualSize.
This way, one block is processed at a time until the entire range is covered.
For example, start=192.168.0.5, end=192.168.0.7:
s=3232235525 (0xC0A80005), e=3232235527.
First loop:
- lowBit = trailing zeros of s=5 (binary 101), that is, 0 bits, so maxSize=1<<0=1.
- actualSize=min(1, 7-5+1=3) →1.
- mask=32 -0=32.
- The CIDR block is 192.168.0.5/32.
- s +=1 →6.
The second loop:
- s=6, binary 00000110, trailing zeros is 1 (because the last two digits are 10 → the lowest digit is 0?)
- No, (6) is 1, because the binary of 6 is 110 and there is a 0 at the end.
- So, lowBit=1 →maxSize=2.
- actualSize=min(2, 7-6+1=2) →2.
- mask=32 -1=31.
- The CIDR block is 192.168.0.6/31, covering 6 and 7.
- s +=2 →8, exceeding e=7, the loop ends.
So, the result is two CIDR blocks: /32 and /31.
This seems to be correct.
Another example, start=192.168.0.0, end=192.168.3.255:
s=3232235520, e=3232238079.
First loop:
lowBit=(s) →s=0xC0A80000 → Binary is 11000000 10101000 0000000000000 0000000000000 → There are 16 zeros at the end? Or it may depend on the specific conversion method.
If the way the IP address is converted to a long integer is to be used as a high bit, for example:
For 192.168.0.0, convert to:
192 <<24 | 168 <<16 | 0 <<8 |0 → i.e. 3232235520, the binary is 11000000 10101000 0000000000000.
(3232235520)→Calculate the number of 0 at the end. The binary of 3232235520 is:
11000000 10101000 000000000000 000000000 →The last 16 bits are all 0, so trailing zeros is 16.
So, lowBit=16 →maxSize=1<<16=65536.
But the actual remaining size is e -s +1 = 3232238079 -3232235520 +1=2560.
So actualSize=min(65536, 2560)=2560.
But 2560 is not the power of 2. At this time, you need to adjust and find the maximum power of 2, no more than 2560.
So, I may have a problem with my previous idea here, that is, the size of the block must be power of 2, and the actual remaining size may not be, so I need to take the maximum possible block, whose size is power of 2, and it does not exceed the remaining size.
What should I do at this time?
For example, in step c, maxSize is determined by lowBit, that is, the possible block size is 2^lowBit, but this size may exceed the remaining size, so actualSize needs to be set to the maximum power of 2, not exceeding the remaining size.
Alternatively, another way, actualSize is the largest power of 2, such that actualSize <= remainingSize, and actualSize <= maxSize (i.e., the block size determined by lowBit).
For example, if remainingSize is 2560, then the maximum power of 2 is 2048 (2^11=2048), and maxSize is 65536 by lowBit=16, so actualSize=2048.
At this time, mask=32 -11=21.
So, is the CIDR block 192.168.0.0/21? But in this case, the range of the block is 192.168.0.0 to 192.168.7.255, but the end IP of the user is 192.168.3.255, so this will be out of range. This shows that there is something wrong with my logic.
Oh, this means there may be problems with the original algorithm. It may be necessary to rethink how to determine the size of the block.
The correct logic should be to find the largest mask so that the start address of the subnet is s and the end address of the subnet <=e.
That is, the mask of the subnet determines that the size of the block is 2^(32 - mask), so we need to find the largest mask (i.e. the smallest block size), such that s + (2^(32 - mask)) -1 <=e.
At the same time, the mask must satisfy the last (32-mask) bit of s is 0, that is, s is the starting address of the subnet.
For example, for s=192.168.0.0, e=192.168.3.255.
The largest mask is 22, because the block size is 2(32-22)=210=1024, and s+1024-1=192.168.3.255. This is exactly what is needed.
So, the correct CIDR is 192.168.0.0/22.
Therefore, in this case, the algorithm should return one CIDR block, not multiple. So what's the problem?
The size of the block should satisfy both:
The size of the block is a power of 2, and the starting address of the block is s.
The end address of this block does not exceed e.
So, the size of the block should be the largest possible power of 2, satisfying s + size -1 <=e, and size is the largest possible value, and s mod size ==0.
3.4 How to calculate such a size?
Algorithm steps:
Calculate remaining = e - s +1.
The initial size is the greatest possible, i.e. the maximum power of 2 <= remaining.
At the same time, size must satisfy s & (size -1) ==0 (that is, s is a multiple of this size).
If these two conditions are satisfied, size can be the value, otherwise, size needs to be halved until the condition is satisfied.
For example, for s=192.168.0.0, e=192.168.3.255, remaining=1024.
The maximum size is 1024, and s mod 1024 ==0, so you can use size=1024 and mask=22.
So, the correct CIDR is /22.
So how do you convert this logic into code?
Implementation steps:
Calculate remaining = e -s +1.
Calculate maxMask = 32 - (int)((remaining)/(2)) → but this may not be correct, because remaining may not be a power of 2.
Alternatively, find the largest mask such that 2^(32 - mask) <= remaining, and s & (2^(32 -mask) -1) ==0.
The correct algorithm should be:
Loop processing, finding the largest size (power of 2) each time, such that:
size <= remaining
And s + size -1 <=e
And s & (size -1) ==0 (that is, s is an integer multiple of size)
Then, mask=32 - log2(size).
Then, add the CIDR block to the list, s += size, remaining = e -s +1.
Repeat until remaining=0.
Now, how do you implement this in your code?
step:
while s <=e:
remaining = e -s +1;
maxSize = 1 << 30; // Initially a larger number, such as 2^30size = 0;
for (int shift = 0; shift <=32; shift++) {
currentSize = 1 << shift;
if (currentSize > remaining) break;
if ((s & (currentSize -1)) ==0) {
size = currentSize;
}
}
// At this time, size is the largest size that meets the conditionsmask = 32 - log2(size) →Right nowmask=32 - shift.
add cidr: ipToString(s) + "/" + mask
s += sizeBut this may require a loop to find the maximum size.
Alternatively, you can use bit operations to find the largest possible size:
size = remaining;
Then, find the largest size, which is the power of 2, and satisfies size <= remaining, and (s & (size -1)) ==0.
For example:
size = (remaining); // The maximum power of 2 <= remainingwhile (size >0) {
if ((s & (size -1)) ==0) {
break;
}
size >>=1;
}
In this way, the size is adjusted to the maximum size that satisfies the condition.
For example, the method to calculate size:
long size = (remaining);
Then, loop check (s & (size -1)) ==0, otherwise cut the size in half until the size that meets the condition is found.
The code may be as follows:
long remaining = e - s +1;
long size = (remaining);
while (size >0) {
if ((s & (size -1)) ==0) {
break;
}
size >>=1;
}
if (size ==0) {
size =1;
}
Then, mask=32 - log2(size). But how to calculate log2(size)?
Can be used to get it. For example, for size=1024, the binary is 1000000000, with a total of 11 bits, so numberOfLeadingZeros is 64-11=53. But (1024) returns 64 - 11 =53? This may require adjustment.
Alternatively, calculating log2(size) can use bit operations:
int logSize = 63 - (size);
For example, size=1024 →63 - 53 (numberOfLeadingZeros(1024)) is 10 →log2(1024)=10.
So, mask=32 - logSize.
In this way, for example size=1024 →mask=22.
Therefore, based on the above analysis, the general structure of Java code can be:
public static List<String> ipRangeToCidrs(String startIp, String endIp) {
// Convert startIp and endIp to long s and e List<String> cidrs = new ArrayList<>();
long s = ipToLong(startIp);
long e = ipToLong(endIp);
while (s <= e) {
// Calculation remains long remaining = e - s +1;
// Calculate the maximum size long size = 1;
int shift =0;
// Find the maximum size=2^shift <= remaining, and s & (size-1) ==0 for (shift =0; (1L << (shift+1)) <= remaining; shift++) {
if ((s & ( (1L << (shift+1)) -1 )) !=0) {
break;
}
}
size = 1L << shift;
// Calculate mask int mask = 32 - shift;
// Add CIDR (longToIp(s) + "/" + mask);
// Update s s += size;
}
return cidrs;
}
4. ipToLong function
public static long ipToLong(String ip) {
String[] octets = ("\\.");
if ( !=4) {
throw new IllegalArgumentException("Invalid IP address");
}
long result =0;
for (int i=0; i<4; i++) {
int octet = (octets[i]);
if (octet <0 || octet >255) {
throw new IllegalArgumentException("Invalid IP octet");
}
result <<=8;
result |= octet;
}
return result;
}
In this way, for192.168.0.5,turn out(192 <<24) | (168 <<16) | (0 <<8) |5 = 3232235525L.
5. longToIp function
public static String longToIp(long ip) {
return ("%d.%d.%d.%d",
(ip >>24) & 0xFF,
(ip >>16) & 0xFF,
(ip >>8) & 0xFF,
ip & 0xFF);
}
so,3232235525LWill be converted correctly to192.168.0.5.
6. Write the main loop part
public static List<String> ipRangeToCidr(String startIp, String endIp) {
long start = ipToLong(startIp);
long end = ipToLong(endIp);
List<String> result = new ArrayList<>();
if (start > end) {
throw new IllegalArgumentException("Start IP must be <= End IP");
}
while (start <= end) {
// Calculate the position of the lowest bit 1 of the current start to determine the largest possible mask long maxSize = 1;
int shift =0;
// Find the largest shift so (1 << shift) <= remaining, and (start & ((1 << shift) -1)) ==0 long remaining = end - start +1;
// The initial shift is 0, gradually increase until the condition cannot be met for (shift =0; (1L << (shift+1)) <= remaining; shift++) {
// Check if shift is added, whether the bits after start are 0 long mask = (1L << (shift +1)) -1;
if ((start & mask) !=0) {
break;
}
}
long currentSize = 1L << shift;
int mask = 32 - shift;
(longToIp(start) + "/" + mask);
start += currentSize;
}
return result;
}
To sum up, the final Java function should include:
Transformation functions of ipToLong and longToIp.
The main function handles the loop and finds every possible CIDR block.
Correct size and mask.
7. Complete code implementation
The following is the complete Java code and handles possible exceptions and boundary cases that can convert the start and end IP into the most accurate list of CIDR blocks. This method dynamically calculates the range of each CIDR block through bit operations, ensuring that all IPs are covered without overlapping
import ;
import ;
public class CidrCalculator {
public static List<String> convertIpRangeToCidr(String startIp, String endIp) {
long start = ipToLong(startIp);
long end = ipToLong(endIp);
List<String> cidrList = new ArrayList<>();
if (start > end) {
throw new IllegalArgumentException("The start IP cannot be greater than the end IP");
}
while (start <= end) {
// Calculate the lowest significant bit of the current starting IP (determines the size of the CIDR block) int suffixZeros = (start);
long maxSize = 1L << suffixZeros; // Possible block size (2^suffixZeros) long remaining = end - start + 1; // The remaining number of IPs to be covered
// The actual block size cannot exceed the remaining range long actualSize = (maxSize, remaining);
// Calculate the number of mask bits of CIDR (32 - log2(actualSize)) int mask = 32 - (int) ((actualSize) / (2));
// Add CIDR blocks to the list (longToIp(start) + "/" + mask);
// Move to the starting IP of the next block start += actualSize;
}
return cidrList;
}
// Convert IP string to 32-bit integer (using long storage) private static long ipToLong(String ip) {
String[] octets = ("\\.");
if ( != 4) {
throw new IllegalArgumentException("Invalid IP address format");
}
long result = 0;
for (int i = 0; i < 4; i++) {
int octet = (octets[i]);
if (octet < 0 || octet > 255) {
throw new IllegalArgumentException("IP octets out of range");
}
result = (result << 8) | octet;
}
return result;
}
// Convert 32-bit integers to IP strings private static String longToIp(long ip) {
return ((ip >> 24) & 0xFF) + "." +
((ip >> 16) & 0xFF) + "." +
((ip >> 8) & 0xFF) + "." +
(ip & 0xFF);
}
// Test cases public static void main(String[] args) {
// Example 1: Single IP (/32) test("192.168.0.5", "192.168.0.5"); // ["192.168.0.5/32"]
// Example 2: Two consecutive IPs (/31) test("192.168.0.6", "192.168.0.7"); // ["192.168.0.6/31"]
// Example 3: A complete Class C subnet (/24) test("192.168.0.0", "192.168.0.255"); // ["192.168.0.0/24"]
// Example 4: IP range across subnets test("192.168.0.5", "192.168.0.7"); // ["192.168.0.5/32", "192.168.0.6/31"]
}
private static void test(String startIp, String endIp) {
List<String> cidrs = convertIpRangeToCidr(startIp, endIp);
("IP range: " + startIp + " - " + endIp);
("CIDR Block: " + (", ", cidrs) + "\n");
}
}
Code description
Core logic
- Bit calculation: Determine the maximum possible CIDR block size by finding the lowest significant bit of the starting IP.
- Dynamically adjust the block size: Dynamically adjust the actual CIDR block size according to the alignment requirements of the remaining IP range (remaining) and the starting IP.
Key Methods
- ipToLong(): Convert an IP string to a 32-bit integer (stored with long to avoid symbolic problems).
- longToIp(): Convert integers back to dotted decimal format.
- convertIpRangeToCidr(): main method, traversing the IP range to generate a CIDR list.
Test cases
Coverage single IP, continuous IP, complete subnet and cross-subnet ranges to verify the accuracy of different scenarios.
Execution Example
enter:
convertIpRangeToCidr("192.168.0.6", "192.168.0.7");
Output:
CIDR Block: 192.168.0.6/31
enter:
convertIpRangeToCidr("192.168.0.5", "192.168.0.7");
Output:
CIDR block: 192.168.0.5/32, 192.168.0.6/31
This is the article about the detailed explanation of the principles and implementation of IP segment to CIDR in Java. For more related Java IP segment to CIDR content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!