CIDR bitwise operations - could I be a bit wiser?

Question

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

Answer 1

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.