CIDR bitwise operations - could I be a bit wiser?
binary, bit-manipulation, cidr, php
Solution
Your second problem can be alternatively seen as finding the first set bit in the inverted number (instead of finding the first not set bit in the non-inverted number), which is equivalent to finding the integer log2 of the number.
This is a fairly common problem in the bitwise world and there are numerous speed-optimized algorithms for it. You are using the (slow) obvious algorithm: http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
But I assume that you don't really care about speed, but rather about brevity, in that case you could do something like this:
$cidr = (int) (32 - log(~current(unpack('N', $mask)) & 0xffffffff, 2));
The `& 0xffffffff` is necessary to be compatible with 64 bit integers.
Problem
I am building a class to represent an IPv4 subnet. I am storing the network address and the subnet mask as 4 byte binary strings, which are built during the constructor based on the arguments. One of the representations I would like the constructor to accept is CIDR notation. My bitwise operations are a little rusty, and where I have got stuck is in converting a decimal integer CIDR representation of the subnet mask into a 4 byte binary string, and vice versa. I have also found I am unable to perform left/right shifts on string - which I'm sure I have successfully done before? I have managed to get the conversion to the binary string to work with the following code: ``` // An example input value. $mask = 24; // 255.255.255.0 if ($mask < 0 || $mask > 32) { // Invalid prefix size throw new RangeException('Invalid CIDR prefix size'); } else if ($mask === 0) { // Handle 0 $mask = "\x00\x00\x00\x00"; } else { // Left-pad a 4-byte string with $mask set bits $mask = pack('N', (0x01 << 31) >> ($mask - 1)); } ``` I don't like this logic for two reasons: - I don't like treating `0` as a special case - I don't like the right-shift followed by a left-shift I feel sure there is a way to do this more efficiently in a way that will handle `0` correctly without treating it as a special case. When converting a binary string back to the decimal representation of a CIDR prefix size, I am currently using the code below. I have another very similar block of code when validating a subnet mask provided in other formats to ensure the set bits are contiguous. ``` // An example input value. $mask = "\xff\xff\xff\x00"; // /24 // Convert the binary string to an int so bit shifts will work $mask = current(unpack('N', $mask)); // A counter to represent the CIDR $cidr = 0; // Loop and check each bit for ($i = 31; $i > 0; $i--) { if (($mask >> $i) & 0x01) { $cidr++; } else { break; } } // Return the result return $cidr; ``` I don't like this because of the loop - I feel sure there is a more intelligent bitwise way to do it. Is there a more intelligent way to do either of these tasks? Thoughts/suggestions/general abuse please... EDIT: Any solutions need to work on PHP 4.3.10 and upwards, and must work on both 32- and 64-bit platforms. Please keep in mind that all integers in PHP are signed, and on a 32-bit platform anything `>= 0x80000000` will be stored as a double (and will therefore not play nice with bitwise operations).