Deriving the Inverse of a subnet definition

Question

An IP Subnet is defined with two parts, a network and a prefix-length or mask.
For example 192.168.0.0/16 (or, 192.168.0.0/255.255.0.0).

An IP address like 192.168.1.1 is said to match this subnet because,

(192.168.1.1 & 255.255.0.0) == 192.168.0.0

I am interested in what might be called the inverse of a subnet
which is described like this,

For a given SubnetA (say, NetworkA / MaskA),
The inverse of SubnetA is the list of k subnets, such that,

If an IP address A, matches SubnetA,
A will not match any of these k subnets, and
Every IP address B that does not match SubnetA,
will match exactly 1 of these k subnets.

Code is not necessary, I am interested in a correct and optimal method.

---

I have the optimized answer noted for reference in this code snippet.

unsigned int network; // 32-bit network. Say (192.168.0.0 or 0xC0A80000)
unsigned int mask; // 32-bit mask (0xFFFF0000 for the example case)

i = 0; // to iterate over the network bits
do {
    bitmask = (unsigned int)(0x80000000 >> i)
    invmask = (unsigned int)(0xFFFFFFFF << (31-i));

    invnet = (invmask & network) ^ bitmask;
    printSubnet(invnet, invmask); // this stores/prints the subnet

} while (mask && i<32); // only while we have valid mask

Accepted Rafał's answer since he also got it right first.

---

Here is the inverse for 192.168.0.0/16, to check correctness.

[1] 0.0.0.0 / 128.0.0.0         ;    00000000
[2] 128.0.0.0 / 192.0.0.0       ;    80000000
[3] 224.0.0.0 / 224.0.0.0       ;    e0000000
[4] 208.0.0.0 / 240.0.0.0       ;    d0000000
[5] 200.0.0.0 / 248.0.0.0       ;    c8000000
[6] 196.0.0.0 / 252.0.0.0       ;    c4000000
[7] 194.0.0.0 / 254.0.0.0       ;    c2000000
[8] 193.0.0.0 / 255.0.0.0       ;    c1000000
[9] 192.0.0.0 / 255.128.0.0     ;    c0000000
[10] 192.192.0.0 / 255.192.0.0  ;    c0c00000
[11] 192.128.0.0 / 255.224.0.0  ;    c0800000
[12] 192.176.0.0 / 255.240.0.0  ;    c0b00000
[13] 192.160.0.0 / 255.248.0.0  ;    c0a00000
[14] 192.172.0.0 / 255.252.0.0  ;    c0ac0000
[15] 192.170.0.0 / 255.254.0.0  ;    c0aa0000
[16] 192.169.0.0 / 255.255.0.0  ;    c0a90000

Answer 1

Hm. I'd say that it is basically any subnet other than A with the same mask...

Answer 2

One subnet for every unmasked bit b in A, matching all the previous bits in A, differing on b, masking all the following bits. This way each address i not in A will match only one of the above networks, namely the one responsible for the first bit of i that does not match A.

Answer 3

If you imagine tree of all subnets starting at 0.0.0.0/32, branching at every bit, you want all the branches that don't lead to your subnet. You go up one step (bit), null this bit and add sibling (has different bit on the appropriate place) of this node to your set. (It's the same as Rafał says, only expressed differently.) You can do it like this (working C# code):

using System;
using System.Text;

namespace so_subnet_complement
{
 class Program
 {
  static void Main(string[] args)
  {
   Console.WriteLine("Enter subnet in the 192.168.0.0/16 format.");
   string[] line = Console.ReadLine().Split('/');
   string[] segments = line[0].Split('.');
   uint ip = 0;
   uint multiplier = 1;
   for (int i = 3; i >= 0; i--)
   {
    ip += byte.Parse(segments[i]) * multiplier;
    multiplier *= 0x100;
   }
   int mask = int.Parse(line[1]);

   Console.WriteLine("Complement subnets:");
   writeComplementSubnets(ip, mask);
  }

  static void writeComplementSubnets(uint ip, int mask)
  {
   for (;mask < 32; mask++)
   {
    uint newIp =(uint)(ip & (0xFFFFFFFF << mask) ^ (1 << mask));
    Console.WriteLine("{0}/{1}", ipToString(newIp), mask);
   }
  }

  static string ipToString(uint ip)
  {
   StringBuilder result = new StringBuilder(15);
   uint mask = 0xFF000000;
   int shift = 24;
   for (int i = 0; i < 4; i++)
   {
    result.Append((ip & mask) >> shift);
    mask >>= 8;
    shift -= 8;
    if (i < 3)
     result.Append('.');
   }
   return result.ToString();
  }
 }
}

Most important is the writeComplementSubnets method. IP adress is represented in natural (for me) representation, so that 192.168.0.0 becomes 0xC0A80000.

EDIT: I realised that recursion is absolutelly unnecessary here. It seems functional programming causes wrong thinking sometimes.