「Codewars」IP转换器

Published on:
Tags: CodeWars ruby

CodeWars是个很有意思的编程学习网站,这上面有很多有意思高质量的小题目,之前登陆这个网站的时候感觉很慢,今天又登陆上去看了一下,感觉速度比以前快多了,可能是做了一些优化。这样的话,打算抽空就去做一些小题目,练练脑子。然后把解题思路写成blog,我希望可以做完codewars的所有题目。


今天做的这个题目是:IP转换器。实际上只是实现一个IP转换的方法而已。

题目(难度6kyu:IPv4 to int32):

简单翻译一下:

有一个IPv4地址: 128.32.10.1。 这个地址实际由4个8位的字节组成:

第一个128,它的二进制是: 10000000
第二个32, 它的二进制是: 00100000
第三个10, 它的二进制是: 00001010
第四个1, 它的二进制是: 00000001

所以, 128.32.10.1 相当于 10000000.00100000.00001010.00000001

这样的话,IP地址就是由32位的了,于是我们就根据这32位字节得到一个数字:2149583361。

要求:

写一个函数:ip_to_int32(ip) 可以让这个IPv4的地址返回那个数字:
iptoint32("128.32.10.1") = 2149583361


解题思路:

可以看得出来,codewars的题目,多是来源于实践中的一些基础知识。这里隐含的知识是:

为什么要把IP转换为一个数字呢?
TCP/IP协议规定,IP地址是由32位二进制数组成,简单来说,是为了便于查询或做一些根据IP设置的登陆限制,比如一些IP数据库,里面存储的就是根据32位二进制转化成的数。

在知道这个基础知识的前提下,这个题目才变得有意义。

那么我最初的解题思路是这样的:

  1. 需要把"128.32.10.1"这个字符串里的每一个ip数字转换为二进制。
  2. 把4段二进制拼接在一起形成一个32位二进制串。
  3. 把32位二进制串变成十进制。

于是我得到了下面这个方法:

def ip_to_int32(ip)
  ip.gsub(/(\d+)/){|i|i = i.to_i.to_s(2); "0"*(8-i.size)<< i} \
    .gsub(/\./, "")\
    .to_i(2)
end

测试是成功的:

Test.assert_equals(ip_to_int32("128.32.10.1"), 2149583361)

解释:

  1. gsub方法有一个用法就是可以传递块, 这样就避免了我另外去迭代处理。/(\d)+/,这个正则不太严谨,只是取数字,但没有判断不合法的IP地址,这里就不考虑那么多了。
  2. "0"*(8-i.size)<< i 这段代码是个笨方法,是为了给转换为二进制的IP数字补足8位。
  3. 128.to_s(2)是十进制转二进制的一个方法, "1010".to_i(2)是二进制转十进制的方法。

答案通过以后,就可以看到别人写的答案了,大致看了一下,有几个很有启发:

第一个:使用字符串格式化的思路:

def ip_to_int32(ip)
  ("%02x%02x%02x%02x" % ip.split('.')).to_i(16)
end

解释:

  1. "%02x"是把一个字符串格式化为16进制,2为指定的输出字段的宽度.如果位数小于2,则左端补0
  2. % 操作符, 用于字符串格式化。
  3. to_i(16), 把16进制转换为10进制。

受这个思路的启发,我又改了下我的代码:

def ip_to_int32(ip)
  ("%08b"*4 % ip.split('.')).to_i(2)
end

解释:

  1. 使用2进制、8进制、16进制的指示符分别是(b',o', x',X')
  2. 所以,"%08b"是把一个十进制数格式化为一个二进制数,8位宽度,如果位数小于8,则左端补0.

这种写法比我之前那种简洁多了。

第二个: 使用位操作:
看到有一个人用了位移操作,是这样的:

def ip_to_int32(ip)
  ip.split('.').inject(0) { |total, val| (total << 8) + val.to_i}
end

这是我用他的思路改的代码:

def ip_to_int32(ip)
  ip.split('.').each_with_index.inject(0) do |total, (ip, index)|
    total += (ip.to_i << (8*(3 - index)))
  end
end

解释:
IP地址都是基于256来计算的:

128 * (256)3 + 32 * (256)2 + 10 * (256)1 + 1 * (256)0 = ?
2147483648 + 2097152 + 2560 + 1 = 2149583361

当然,可以直接把这个等式写成代码,也可以求得结果,但是我们用位操作更快:

//  128 << 24
//  32  << 16
//  10  << 8
//  1   << 0

当然还有其他解法,都是一般的数组拼接,我就不罗列了。

从十进制数字转换为IP地址的方法,就是一个逆向过程,我也不多写了。

感兴趣的朋友,可以去玩玩CodeWars。

Comments

comments powered by Disqus