Bitwise Operations and Subnetting

By Brandon James on 2019-07-29

Back in September of 2016 I wrote a subnet calculator in C and then blogged about it. This entry is based on that old blog post.

IPv4 Addresses are simply unsigned 32-bit integers. This makes it easy to perform calculations on them using bitwise operations. It's common to see IP addresses represented as four seperate octets. This is done primarily for readablity, but it also aids in intuition when you start looking at the math behind IP subnets.

In order to do anything useful, we first need to take the human provided dotted decimal notation and convert it to a 32 bit unsigned integer.

unsigned int dotted_decimal_to_int(char ip[]){ // char is exactly 1 byte unsigned char bytes[4] = {0}; sscanf(ip, "%hhd.%hhd.%hhd.%hhd", &bytes[3], &bytes[2], &bytes[1], &bytes[0]); // set 1 byte at a time by left shifting (<<) and ORing (|) return bytes[0] | bytes[1] << 8 | bytes[2] << 16 | bytes[3] << 24; }

This function works by scanning the C string containing the IP address provided by the user into an array of bytes. It then returns an unsigned integer. Using 192.168.0.1 as an example, we first read the octets into an arry of bytes. This results in something similar to the following in memory:

Byte 0 | Byte 1 | Byte 2 | Byte 3 | Base |
---|---|---|---|---|

192 | 168 | 0 | 1 | Decimal |

11000000 |
10101000 | 00000000 | 00000001 | Binary |

As we return the unsigned int, the bytes are left shifted so that they are properly aligned and then a logical OR is applied to combine the bytes. The result of this is a 32-bit representation of the IP address. In this case, the resulting integer in decimal is 3,232,235,521. The table below shows what the left shift looks like in memory.

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

Byte[3] | 00000001 | N/A |

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

Byte[2] | 00000000 | >>8 | |||

Result | 00000000 | 00000000 |

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

Byte[1] | 10101000 | >>16 | |||

Result | 10101000 | 00000000 | 00000000 |

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

Byte[0] | 11000000 | >>24 | |||

Result | 11000000 | 00000000 | 00000000 | 00000000 |

And the OR operation:

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

Byte[0] | 11000000 | 00000000 | 00000000 | 00000000 | |

Byte[1] | 10101000 | 00000000 | 00000000 | OR | |

Result | 11000000 | 10101000 | 00000000 | 00000000 | |

Byte[2] | 00000000 | 00000000 | OR | ||

Result | 11000000 | 10101000 | 00000000 | 00000000 | |

Byte[3] | 00000001 | OR | |||

Result | 11000000 | 10101000 | 00000000 | 00000001 |

After we've finished performing our calculations, we need to return the subnet to a human readable format. This can be done with the following function:

void printip(int ip){ // takes a 32 bit integer and prints it as 4 decimal separate octets unsigned char bytes[4]; // set the byte to the first byte of the ip bytes[0] = ip; bytes[1] = ip >> 8; // right shift by a byte and repeat bytes[2] = ip >> 16; bytes[3] = ip >> 24; printf("%d.%d.%d.%d\n", bytes[3], bytes[2], bytes[1], bytes[0]); return; }

This function works by taking our 32-bit integer and breaking it into 4 separate bytes that can be evaluated separately. We do this by assigning each separate byte to a member of a char array. This is done by right shifting the number by 8 bits prior to each assignment. Note that the right shift operator causes the bits at the end get rotated to the front.

Using 192.168.0.1 as our example again:

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

byte[0] | 11000000 |
10101000 | 00000000 | 00000001 | |

byte[1] | 10101000 |
00000000 | 00000001 | 11000000 | <<8 |

byte[2] | 00000000 |
00000001 | 11000000 | 10101000 | <<16 |

byte[3] | 00000001 |
11000000 | 10101000 | 10101000 | <<24 |

In the above example, after each shift we are setting the contents of byte 1 to the current index of our byte array. Then we simply use printf to display the integer in dotted decimal notation.

Subnets are commonly referenced using CIDR notation (eg 192.168.0.0/24). Since CIDR notation is simply the number of most significant bits set, it's pretty easy to create a function to do the conversion.

unsigned int cidr_to_mask(unsigned int cidrValue){ // left shift 1 by 32 - cidr, subtract 1 from the result and XORing // it with a mask that has all bits set, yeilds the subnet mask return -1 ^ ((1 << (32 - cidrValue)) - 1); }

I'll show how this works by using a /24 mask. First we subtract 32 by 24, which yields 8. Then we left shift 1 8 times, which yields 1 00000000. Next, we subtract the result by 1, yielding 11111111. Finally, we XOR the result with -1 (when working with unsigned values, -1 sets all bits), which results in 11111111 11111111 11111111 00000000.

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

00000000 | 00000000 | 00000000 | 00000001 | <<8 | |

Result | 00000000 | 00000000 | 00000001 | 00000000 | -1 |

Result | 00000000 | 00000000 | 00000000 | 11111111 | |

-1 | 11111111 | 11111111 | 11111111 | 11111111 | XOR |

Result | 11111111 | 11111111 | 11111111 | 00000000 |

Additionally, if the user gives us a subnet mask using dotted decimal notation, we'll want to give them the mask in CIDR notation. This can be done by counting the number of bits set in the subnet mask.

unsigned int cidr_to_mask(unsigned int cidrValue){ // left shift 1 by 32 - cidr, subtract 1 from the result and XORing // it with a mask that has all bits set, yeilds the subnet mask return -1 ^ ((1 << (32 - cidrValue)) - 1); }

This function works as follows:

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation | CIDR |
---|---|---|---|---|---|---|

Mask | 11111111 | 11111111 | 11111111 | 00000000 | ||

Mask - 1 | 11111111 | 11111111 | 11111110 | 00000000 | AND | |

Result | 11111111 | 11111111 | 11111110 | 00000000 | 1 | |

Result - 1 | 11111111 | 11111111 | 11111101 | 00000000 | AND | |

Result | 11111111 | 11111111 | 11111100 | 00000000 | 2 | |

Result - 1 | 11111111 | 11111111 | 11111011 | 00000000 | AND | |

Result | 11111111 | 11111111 | 11111000 | 00000000 | 3 | |

Result | 11111111 | 11111111 | 11110111 | 00000000 | AND | |

Result | 11111111 | 11111111 | 11110000 | 00000000 | 4 |

...

continue until no bits are set

Now that we've dealt with the human readability issues. Let's take a look at the operations that actually deal with subnet calculations.

First off, to calculate the Network or Subnet address, we simply take the IP address and netmask and apply the AND operation. The truth table below is for an IP address of 192.168.0.10 with a /24 mask.

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

IP | 11000000 | 10101000 | 00000000 | 00001010 | |

Mask | 11111111 | 11111111 | 11111111 | 00000000 | AND |

Result | 11000000 | 10101000 | 00000000 | 00000000 |

In C this function is simply expressed as:

unsigned int calc_network_address(unsigned int ipaddress, unsigned int netmask){ return ipaddress & netmask; }

Calculating the broadcast address is as simple as adding the network address to the subnet's complement (ie the result of the NOT operation on the subnet mask). Again using the same network as our previous example.

Variable | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Operation |
---|---|---|---|---|---|

IP | 11000000 | 10101000 | 00000000 | 00000000 | |

~Mask | 00000000 | 00000000 | 00000000 | 11111111 | + |

Result | 11000000 | 10101000 | 00000000 | 11111111 |

The dotted decimal result is 192.168.0.255. This is another operation that is easily expressed in C.

unsigned int calc_broadcast(unsigned int network, unsigned int netmask){ return network + (~netmask); }

Once we have the network address and the subnet mask, it's trivial to calculate our first host (network address + 1), last host (broadcast address - 1) and number of hosts (broadcast - first host).

This is not the most complete subnet calculator on the internet, nor is it supposed to be. However, I think it provides several good examples of things that can be done with bitwise operations and provides additional intuition for why we use subnet masks.