CIDR位运算 - 我能更聪明吗？

Question

我正在构建一个表示IPv4子网的类。我将网络地址和子网掩码存储为4字节二进制字符串，并在构造函数中根据参数构建它们。其中一个我希望构造函数接受的表示是CIDR表示法。

我的位操作有点生疏，我卡在了将子网掩码的十进制整数CIDR表示转换为4字节二进制字符串以及反之上。我还发现我无法对字符串执行左/右移操作 - 尽管我肯定以前成功过？

---

我已经成功地使用以下代码将转换为二进制字符串：

// 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));
}

我不喜欢这个逻辑，原因有两个：

• 我不喜欢把0作为一种特殊情况处理
• 我不喜欢右移后再左移的操作

我相信一定有更高效的方法来处理这个问题，并且可以正确地处理0而不需要把它当作一种特殊情况。

---

当将二进制字符串转换回CIDR前缀大小的十进制表示时，我目前正在使用下面的代码。我还有另一个非常相似的代码块，用于验证以其他格式提供的子网掩码，以确保设置的位是连续的。

// 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;

我不喜欢这个循环，因为我相信有更聪明的按位方式来处理它。

---

有没有更智能的方式来完成这些任务？

请分享您的想法/建议/意见...

---

编辑：

任何解决方案都需要在PHP 4.3.10及以上版本上运行，并且必须在32位和64位平台上运行。请记住，PHP中的所有整数都是有符号的，在32位平台上，任何>= 0x80000000的值将被存储为double（因此无法与位运算良好地配合使用）。

- DaveRandom

Answer 1

你的第二个问题可以换种方式理解，即在反转后的数字中找到第一个设置位（而不是在非反转后的数字中找到第一个未设置位），这相当于找到该数字的整数对数log2。

这是位运算领域中相当常见的问题，有许多经过速度优化的算法。你正在使用（较慢的）显而易见的算法：http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious 但我假设你并不真正关心速度，而更关心简洁性，在这种情况下，你可以像这样做：

$cidr = (int) (32 - log(~current(unpack('N', $mask)) & 0xffffffff, 2));

& 0xffffffff是为了兼容64位整数必须的。

- NikiC

---

啊，对数 - 这绝对是一种更加智能的方法。但是我有点难以理解 & 0xffffffff - 特别是，在32位平台上，这是否会导致它出现问题，因为 0xffffffff 将被视为浮点数，并且这可能会从按位操作中产生意外结果（如果我没记错的话）？ - DaveRandom

@DaveRandom 可能是这个链接 http://chat.stackoverflow.com/transcript/message/5062806#5062806 - Dejan Marjanović

@DaveRandom 是的，我在64位上测试了这个。我不确定浮点数是否会影响任何东西（因为它仍然在其精确范围内）。无论如何，“log”解决方案都相当不稳定；在位运算上应用浮点运算似乎并不顺利。我会删除这个答案。 - NikiC

经过尝试，即使修复了0xffffffff的问题，这仍然无法正常工作，因为log(2, 2) == 1和log(1, 2) == 0 - 这就是昨天你所说的，只是我当时没有理解。 - DaveRandom

Answer 2

第二个问题可以通过一种文本方法来解决：

$mask = "\xff\xff\xff\x00";

$cidr = strspn(sprintf('%b', current(unpack('N', $mask))), 1);

它使用sprintf()将整数转换为二进制文本表示，并使用strspn()计算初始1的数量。

更新

在64位机器上，二进制文本表示左侧填充32个零，因此需要使用ltrim()对代码进行修补，如下所示：

$cidr = strspn(ltrim(sprintf('%b', current(unpack('N', $mask))), 0), 1);

更新2

第一个问题也可以采用文本方法解决，但需要使用str_split()（在PHP 4.x中无法使用）：

$mask = vsprintf('%c%c%c%c', array_map('bindec', str_split(str_pad(str_repeat(1, $mask), 32, 0), 8)));

更新3

以下方法适用于我（在32位和64位上测试通过）：

$mask = pack('N', 0xffffffff << (32 - $mask));

在这个过程中，数字变成了浮点数，但保留了足够的精度来处理位移操作。

- Ja͢ck

---

在当前形式下，这将无法在64位上正常工作，strspn()函数将返回0，因为字符串将具有32个高位0。然而，添加一个ltrim($s , '0')将解决这个问题，并且这将确实成为一个无循环的一行代码，在任何地方都可以运行，感谢您的答案。在我对第一个块有更多意见之前，我会暂时保留接受的操作，但是你绝对值得得到一票的支持。 - DaveRandom

@DaveRandom 谢谢测试 :) 我在我的 EC2 实例上运行了它（应该是 64 位的），但显然 PHP 编译不支持 64 位？无论如何，我已经更新了答案，包括你的建议 :) - Ja͢ck

@DaveRandom 关于第一个代码块，我建议使用str_repeat()和str_pad()来创建二进制表示，然后使用str_split()和bindec()来创建一个字节数组，然后进行打包...但是在4.3版本中，str_split()无法正常工作 =( - Ja͢ck

你可以使用 preg_split() 在 PHP4 中轻松模仿 str_split()，我会试着玩一下它。 - DaveRandom

@DaveRandom 不确定你如何模仿 str_split()；无论如何，我已经更新了我的答案，包括一个可行的解决方案，假设这是可能的 :) - Ja͢ck

Answer 3

为什么不这样做：

$netmask = ( (1<<32) -1 ) << ( 32 - $cidr);

你说你不喜欢左移右移操作，那两次左移呢 ;)

之后，我将其投入到 ip2long 或 long2ip 中。要从掩码转换为CIDR，我会执行以下操作：

$mask = ip2long($mask);
$base = ( ( 1 << 32 ) - 1 );
$cidr = 32 - log( ( $mask ^ $base ) + 1 , 2);

当然，您可以根据需要使用pack、dechex或unpack来调整存储类型。

- Mike Mackintosh

---

$netmask = ((1 << 32) - 1) << (32 - $cidr);在32位平台上不起作用，因为（可笑的是）PHP不允许你移动32位。然而（同样可笑的是），您可以通过$netmask = (((1 << 31) << 1) - 1) << (32 - $cidr);解决这个问题。我不特别喜欢使用“-1”的方法，我宁愿使用~((~0 << 31) << 1)来设置最低的32位。但是<<(32-$cidr)肯定更好。 - DaveRandom

同样的“无法移位32位”问题也适用于反向操作，但可以通过相同的方式解决，关键是使用log(2)函数。我会忽略ip2long()需要点分十进制的事实 :-P - +1 - DaveRandom

我使用的另一种解决方案是inet_pton和ntop，而不是ip2long。你之前有研究过它们吗？ - Mike Mackintosh

PHP 5 >= 5.1.0 - 除此之外，打包操作并不是问题，具体是将整数CIDR转换成字符串的过程让我遇到了问题。我已经非常熟悉pton/ntop，但还是感谢您的建议 :-) - DaveRandom

你能安装自定义扩展吗？我现在正在开发一个支持IPv6并将添加IPv4支持的扩展。 - Mike Mackintosh

如果我可以为这个盒子构建任何东西，我只会在上面安装PHP5.4。不幸的是，制造商没有提供任何编译器，而且我还没有成功地为它构建交叉编译器 - 尽管我已经尝试过并继续尝试。 - DaveRandom

Answer 4

为什么要计算它？只需创建一个包含32个子网掩码的数组即可。

$cidr2mask = array( "\x00\x00\x00\x00", "\x80\x00\x00\x00", "\xc0\x00\x00\x00", "\xe0\x00\x00\x00",
                    "\xf0\x00\x00\x00", "\xf8\x00\x00\x00", "\xfc\x00\x00\x00", "\xfe\x00\x00\x00", 
                    "\xff\x00\x00\x00", "\xff\x80\x00\x00", "\xff\xc0\x00\x00", "\xff\xe0\x00\x00", 
                    "\xff\xf0\x00\x00", "\xff\xf8\x00\x00", "\xff\xfc\x00\x00", "\xff\xfe\x00\x00", 
                    "\xff\xff\x00\x00", "\xff\xff\x80\x00", "\xff\xff\xc0\x00", "\xff\xff\xe0\x00", 
                    "\xff\xff\xf0\x00", "\xff\xff\xf8\x00", "\xff\xff\xfc\x00", "\xff\xff\xfe\x00", 
                    "\xff\xff\xff\x00", "\xff\xff\xff\x80", "\xff\xff\xff\xc0", "\xff\xff\xff\xe0", 
                    "\xff\xff\xff\xf0", "\xff\xff\xff\xf8", "\xff\xff\xff\xfc", "\xff\xff\xff\xfe");

$mask2cidr = array_flip($cidr2mask);

然后只需使用$cidr2mask[$cidr];和$mask2cidr[$mask]即可。

- Barmar

---

虽然这不是一个完全愚蠢的想法，但我希望如果可能的话避免这样做 - 主要是基于原则，而且如果我决定将其扩展支持IPv6，它会变得更加混乱。不过，你的努力值得肯定。 - DaveRandom

IPv6 只是比 IPv4 大 4 倍，完全不会更混乱。而 bit-twiddling 的成本将增加 4 倍。使用类似这样的数组是 O(1)，算法通常是 O(n)。当我们尝试寻找“聪明”的算法时，很容易被困住。像这样简单的方法就可以解决问题。查阅任何有关程序优化的参考资料，它们都应该在适用时推荐像这样的解决方案。 - Barmar

这是一个公正的观点，我不反对你 - 我只是觉得有点荒谬，因为（引用维基百科）“CIDR主要是一种基于位和前缀的标准，用于解释IP地址”，但并没有一种好的、简单的、按位的方法来实现它。但我理解你的观点，也许我只是想太多了。我承认，这部分的目的是通过尝试改善我的按位技能/理解来进行技术练习。 - DaveRandom

Answer 5

（不要介意我自己宣传一下）

我建立了一个PHP库，用于处理IP地址的类似功能。

以下是我如何构建IPv4子网掩码：

<?php
$mask = (~0) << (32 - $cidr);
$binary_mask = pack('N', $mask);
echo implode('.', unpack('C4', $binary_mask));

由于命名空间的原因，它无法在旧版本的PHP上运行，但是我有一些分支是在命名空间添加之前创建的，如果有人愿意提交拉取请求以解决兼容性问题，我会很高兴接受。

该代码（几乎）100％由单元测试覆盖：）

唯一的依赖项是pear Math_BigInteger package。

- Lethargy