Published on Sep 24, 2017, edited on Oct 3, 2017 • Ruslan Ledesma-Garza
Determine if a given string corresponds to a netmask.
Edit 2017.10.03. Added Python implementation of fast solution.
Our definition of netmask is the following. A netmask is a sequence
of 4-bytes that consists of a prefix of 1s followed by a suffix of 0s.
The prefix consists of at least 8 1s and the suffix consists of at
least 2 0s.
For example, string 255.255.0.0 is notation for a netmask. In the
example, each byte is given in decimal notation and the bytes are
separated by dots. The example is a netmask because the first two
bytes are all 1s and the last two bytes are all 0s.
Input.
The input consists of one or more test cases. Test cases
are separated by newlines and are terminated by EOF. Each test case
consists of 4 bytes in decimal notation separated by dots. Consider
the following example.
Output.
For each test case, there is one line of output. The output
corresponding to a test case is either true when the test case is
netmask and false otherwise. For the example input file, the output
is the following.
O.K. solution
We determine if a candidate is a netmask by binary search in the
following way.
Consider the search space. The search space consists of 23 netmasks.
The netmasks, their dot-decimal representation, and their decimal
representation are the following.
A candidate is a netmask when its value is in the previous list.
For a given candidate, we only consider the candidate when its value
is between 4278190080 and 4294967292 inclusive. The reason is that
all values for netmasks are in that range.
When a candidate is within range, we apply binary search over the
values of netmasks to try to find the candidate.
Implementation of O.K. solution
Here is a Ruby implementation.
Fast solution
We determine if a candidate is a netmask by checking the structure of
the candidate by bitwise operations.
Consider the set of all possible netmasks in section O.K. solution.
We only consider candidates between 4278190080 and 4294967292
inclusive.
We check the structure of a candidate within range by checking the
structure of its bitwise complement. Consider the binary
representation of candidate c = 255.255.255.128.
The binary representation of ~c consists of a sequence of 0s
followed by a sequence of 1s because (~c + 1) & c == 0, as
illustrated in the following diagram. The reason is that only when
~c has the expected structure, all 1s in ~c correspond to 0s in
~c + 1 and the least significant 0 in ~c (position 7 of octet D)
corresponds to a 1 in ~c + 1 (position 7 of octet D’).