# Reduce a list of IPv4 to lowest common CIDR

I have a long list of IP addresses that show some pattern of closeness

Example:

``````XX.249.91.16
XX.249.91.21
XX.249.91.32
XX.249.91.160
XX.249.91.165
XX.249.92.15
XX.249.92.25
XX.249.92.51
XX.249.92.234
``````

and sometimes a whois reveals a range like this

``````XX.163.224.0 - XX.163.239.255
``````

I would like to create a list of CIDR that gives me the lowest common number

It seems Python already has such a thing - iprange_to_cidrs - but I need it in JavaScript

``````XX.249.90.0/16
``````

if that is what would handle

``````XX.249.91.0 - XX.249.92.255
``````

ditto XX.163.200.0/nn to handle

``````XX.163.224.0 - XX.163.239.255
``````

A calculator that can do it one range at a time when I fiddle with the mask is here http://www.subnet-calculator.com/cidr.php

My preferred language is JavaScript and I have the following start but need the algorithm that does the match and transform

``````var list = [
"10.249.91.16",
"10.249.91.21",
"10.249.91.32",
"10.249.91.160",
"10.249.91.165",
"10.249.92.15",
"10.249.92.25",
"10.249.92.51",
"10.249.92.234"
]
function dec2bin(ip) {
return ip.map(function(num) {
return ("00000000"+parseInt(num,10).toString(2)).slice(-8);
}).join(".");
}
const result = list.map(ip => dec2bin(ip));
``````

FIDDLE

``````const getDec = ip => {
let octet = ip.split(".");
return (octet << 24) | (octet << 16) | (octet << 8) | octet;
};

// now what?
``````

Update 2:

could the result of the range 111.163.224.0 - 111.163.239.255 be `111.163.224.0/20` ? since we have

``````01101111.10100011.11100000.00000000 - 0,111.163.224.0
01101111.10100011.11101111.11111111 - 0,111.163.239.255
``````

What you're looking for is a the set of contiguous high-order bits in the address that don't change across the entire set of addresses. IPv4 addresses are, at their core, 32-bit unsigned integers. The dotted-quad notation is a convenience for humans. It's best to deal with them in that form. Conversion is easy:

``````integer_ip = (octet1 << 24) | (octet2 << 16) | (octet3 << 8) | octet4
``````

Once you have integers, the right tool for determining which ones change is bitwise exclusive or (`^` in many C-derived languages). This is because it detects change, returning a `1` bit if the corresponding bit in the two values differ, and a `0` otherwise.

I'm going to use 8-bit quantities in the examples to keep it readable, but this applies just the same to the 32-bit numbers you'd get from an IP address.

We have to begin with an integer whose bits indicate which bits changed, which is none of them:

``````changed_bits = 0x00
``````

For each address after the first one, XOR items n and n-1, resulting in the set of bits that changed between the two. Those can the be ORed with our running set of changed bits to add to the set:

``````a = 0x10
a = 0x11    0x10 ^ 0x11 = 0x01    changed_bits = 0x00 | 0x01 = 0x01
a = 0x1f    0x11 ^ 0x1f = 0x0e    changed bits = 0x01 | 0x0e = 0x0f
``````

The end value of `changed_bits`, `0x0f`, indicates that during all comparisons, the upper four bits didn't change (they're all zeros) and the lower four bits did (all ones). Then all you have to do is count the number of unchanged (zero) bits, starting from the most-significant:

``````cidr_size = 0;
for ( bit=0 ; bits < 8 ; ++bits ) {   // Use 32 for IPs
if ( changed_bits & 0x80 ) {      // Use 0x800000 for IPs
break;  // Stop when we hit the first bit that changed.
}
++cidr_size;
changed_bits = changed_bits << 1;  // Rotate the next bit into the high spot
}
``````

At this point, `cidr_size` will hold the number of bits your addresses had in common. Then you can use that to construct a mask with the proper number of bits

``````mask = 0xff << (8 - cidr_size)  // Use 0xffffffff and 32 for IPs
``````

With that in hand, you can use it against any of the integers in your list to come up with the CIDR block:

``````cidr_block = a & mask
``````

Convert `cidr_block` back to octets, add a slash, spit out `cidr_size` and you're in business.

What's in this answer will get you the lowest common CIDR for an entire list of addresses.

Given just IPs, there's no magic algorithm to determine the CIDR from which they came. Based on what they have in common, the IPs used in the question could be included in any of 13 CIDR blocks as large as `10.0.0.0/8` or as small as `10.249.88.0/20`. (Blocks larger than `/8` are also possible, but the practical reality is that no block larger than that has ever been issued.)

To properly group the IPs, you would need a database of the CIDRs that have been issued which could be joined with the IPs you have, grouped by CIDR and aggregated to get a count. The only other thing you could get away with is knowing the netmask that goes with each IP, which isn't going to happen because the receiving end doesn't see it.

• Thanks for the detailed example - a bit (pun intended) confused as to whether the actual code will change other than where indicated for 32 bits since I am actually only interested in IPs. Also how do I detect that I have a new range? The idea is to come up with 123.456.0.0/x, 234.123.123.123/32, 245.768.111.0/y Jul 1, 2014 at 4:18
• @mplungjan: The code shouldn't change other than where indicated. I made a couple of minor edits to the answer and added an addendum that addresses ranges. Jul 1, 2014 at 12:11
• The list is 40,000 IPs and I want to create sets of CIDRs based on the list as it looks now. Tomorrow the list will be different. I cannot create a DB of CIDRs but want to group them on the fly Jul 1, 2014 at 12:42
• @mplungjan: What you want can't be done with the information you have. A list of IPs contains nothing that would help divine their CIDRs, which leaves you with no way to group them. The best you could do is calculate once CIDR that covers the entire list, but that isn't what you're after. If the IPs you're looking at are from the public Internet, the supplemental information you'd need to get a meaningful result is a database of all issued CIDR blocks globally. Jul 1, 2014 at 13:00
• Oops: That should read "... calculate one CIDR..." Jul 1, 2014 at 13:16

I have updated the solution which gave negative ints when using addresses with 255

fiddle

``````const dot2dec = ip => {
const octet = ip.split(".");
return (octet * 16777216) + (octet * 65536) + (octet * 256) + (octet * 1);
};

const num2dot = num => {
let d = num % 256;
num = Math.floor(num / 256);
let c = num % 256;
num = Math.floor(num / 256);
let b = num % 256;
num = Math.floor(num / 256);
let a = num % 256;
return a + "." + b + "." + c + "." + d;
};

const dec2bin = ip =>
ip
.split(".")
.map(num => ("00000000" + parseInt(num, 10).toString(2)).slice(-8))
.join(".");

const fixNegativeResult = result => result < 0 ? result >>> 0 : result;

\$(function() {
const res1 = \$("#res1");

const XOR = num2dot(dec1 ^ dec2);

const andResult = fixNegativeResult(dec1 & dec2);
const AND = num2dot(andResult);

res1.append("<hr>XOR:" + XOR);
res1.append("<hr>AND:" + AND);
});
``````

Old solition

Solution was simpler than expected. I appreciate Blrfl's time and explanation but the whole thing boiled down to the number to use is the two addresses ANDed masked by the number of leading 0s in the binary representation of the two addresses XORed

Fiddle

``````var adr1 = "111.163.224.0",
in this case `111.163.224.0/20`
• I'm getting negative integers in `AND`. May 11 at 16:02
• I put different IP addresses in `adr1` & `adr2`. Can't share those. I got what I needed using `cidr-generator` though. May 12 at 13:41