文章/答案/技术大牛

发布

社区首页 >问答首页 >分解大小为2^n的对齐块中的范围

问分解大小为2^n的对齐块中的范围
EN

Code Golf用户

提问于 2013-11-29 01:55:06

回答 1查看 321关注 0票数 4

给定任意连续的正整数范围，求出在最小子范围内的分解，其大小为L= 2^n，且每个范围必须对齐，即子区间中的第一个整数I必须满足i=0 (mod L)。

背景:一些(特别是旧的)网卡并不是一个简单的CIDR，即192.0.2.0/24号格式的范围，而是由几个连续块组成的，whois查询显式地返回块中的第一个和最后一个ip。尝试使用whois 220.72.0.0：

[...]
IPv4 Address       : 220.72.0.0 - 220.91.255.255 (/12+/14)
[...]

解决这个问题意味着找到有效的CIDR块的列表，这些块的总和构成了这个范围。

number-theory

programming-puzzle

回答 1

Code Golf用户

发布于 2013-11-29 07:24:13

以下贪婪算法最优地工作：

选择允许与下限对齐且不超过总范围的larges块。将此范围添加到结果集并从搜索空间中删除。循环直到整个范围被覆盖。

在下面的行中，我以您的例子为例，将其简化为有趣的部分，即范围为72-91：

0)  Range: 72 - 91 (Size 20)

1a) Largest block size allowed @72: 8
1b) Subrange #1: 72 - 79
1c) Remaining: 80 - 91 (Size 12)

2a) Largest  block size allowed @80: 16 (exceeds size) -> 8
2b) Subrange #2: 80 - 87
2c) Remaining: 88 - 91 (Size 4)

3a) Largest  block size allowed @88: 8 (exceeds size) -> 4
3b) Subrange #3: 88 - 91
3c) Remaining: empty

Result: (72-79) (80-87) (88-91)

如果我们用二进制格式表示数字，则可以更好地看到结构。

0)  Range: 01001000, Size 10100

1a) Largest block size allowed @01001000: 1000
1b) Subrange #1: 01001000, Size 1000
1c) Remaining: 01010000, Size 1100

2a) Largest block size allowed @01010000: 10000 (exceeds size) -> 1000
2b) Subrange #2: 01010000, Size 1000
2c) Remaining: 01011000, Size 100

3a) Largest  block size allowed @01011000: 1000 (exceeds size) -> 100
3b) Subrange #3: 01011000, Size 100
3c) Remaining: empty

实现注意:要选择的子范围的块大小要么对应于下限的最右边1位，要么对应于范围大小的最左边1位(以较小者为准)。

票数 2

页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codegolf.stackexchange.com/questions/15508

复制

相似问题

问分解大小为2^n的对齐块中的范围
EN

回答 1

Code Golf用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问分解大小为2^n的对齐块中的范围EN

回答 1

Code Golf用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问分解大小为2^n的对齐块中的范围
EN