# Netmask

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’).

# Implementation of fast solution

Here is a Ruby implementation.

Here is a Python implementation.