整数转换成对应2进制位整数和的集合

#move from old blog 编辑

说起来题目比较拗口, 比较常见到的是IP地址, 由8个2进制位, 转换成十进制最大为255, 这都知道.

以前学网络的时候, 经常碰到, 一个ip的一段, 比如 192.168.1.211中的211, 211转换成2进制是11010011,

这个2进制的8个位上对应的是:

[128, 64, 32, 16, 8, 4, 2, 1]

好了, 问题就是这个, 用一个程序实现, 把任意整数A, 分拆成一个集合, 集合内数字相加等于A, 且集合内

数字刚好是在 [128, 64, 32, 16, 8, 4, 2, 1]内的.

自己写了个比较搓的:

f = lambda x:[2**i for i in range(len(bin(x)[2:][::-1])) if bin(x)[2:][::-1][i] != '0']

  • f(211)

  • [1, 2, 16, 64, 128]

  • f(124)

  • [4, 8, 16, 32, 64]

用大于255的数字呢?

  • f(500)

  • [4, 16, 32, 64, 128, 256]

出来了个256, 256已经不在 [128, 64, 32, 16, 8, 4, 2, 1]内了, 意思就是超过8位2进制了. 因为8位2进制最大表示十进制数只能到255.

注解:

字符串或list的切片操作: [::-1], 是将字符串或list倒转,比如:

‘123456789’[::-1] ==> ‘987654321’

有一个更精妙的实现是:

通过位于和位移操作, 可以实现的比较简洁:

f = lambda x:[1<<i for i in range(len(bin(127))-1) if 1<<i& x]

执行:

  • f(211)

  • [1, 2, 16, 64, 128]

如果要适用于超过8个2进制位的整数, 那么改进为:

f = lambda x:[1<<i for i in range(len(bin(x))-1) if 1<<i& x]

在2.7和3.0的版本里, len(bin(x)-1) 可以用内置函数: n.bit_length() 代替, 最后就是:

[ 1 << i for i in range(n.bit_length()) if n & (1 << i) ]