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.

Before you read our solution, try to solve the problem on your own. Remember that practice makes perfect.

2018-07-09 The Book of Problems currently supports Ruby, Python, Elixir, Java, C, OCaml, and now C++!

# 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.