poj 2799 IP Networks 模拟位运算

浏览数：38 / 时间：2015年06月09日

poj链接：http://poj.org/problem?id=2799

这题实在是非常的有趣...

写的时候也非常的开心...

然后就写跪了...

刚好讲了ip地址和子网掩码的只是

整个学期的通信导论我就只有这节课有事没去结果昨晚把这方面的只是补起来了有种功德圆满的感觉

network address是前(32-n)随意后n位全零

network mask是前(32-n)全一后n位全零

其次是练习了各种移位操作

我发现移位操作是个非常好用的东西因为它自填充0

所以对一个二进制数往右移8位再往左移8位就相当于把最右的八位抹掉利用这个原理就可以很容易提取出一个数的二进制形式的中间某些位

剔去一个数的二进制形式的中间某些位另一个方法是

用位运算去并上一个筛

这题我就是用这种方法

然后有一个坑爹的地方就是

对于unsigned int 它的移位的操作数会先对32取模以至于如果对a执行“a >> 32”它还是a 相当于“a >> 0”（不要问我是怎么知道的再次哭晕在厕所T^T

所以这次学习了用位运算去并上一个筛来取数这一点要学起来

而且貌似对于string类也可用

然后练了练常数的写法

1ULL表示无符号长整型的常数1

依次类推

此种写法能有效防止不必要的溢出

(1ULL<<i)-1U表示2^i-1 之所以前面要ULL请看上一段（不要再问我是怎么知道的了！

然后取个反~ 就可以作为mask的枚举

然后拿mask和mins或者maxs并一下就得到address了

姿势太美

最后我想说 “写跪了就换姿势”常有奇效

就用你能想到的与现有解法有不小差距的另一种做法去写

说不定就过了

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

const int maxn = 70;

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    int n;
    while(scanf("%d", &n) == 1)
    {
        unsigned int maxs = 0;
        unsigned int mins = 0-1;

        int a, b, c, d;
        unsigned int e;
        for(int i = 0; i < n; i++)
        {
            scanf("%d.%d.%d.%d", &a, &b, &c, &d);
            e = ((unsigned int)a << 24) + (b << 16) + (c << 8) + d;

            if(e < mins)
                mins = e;
            if(e > maxs)
                maxs = e;
        }

        unsigned int mask;
            for (int i = 0; i <= 32; i++) 
            {
                mask = ~((1ULL<<i)-1U);
                if ((mins & mask) == (maxs & mask)) 
                    break;
            }
        unsigned int ans = mins & mask;

        printf("%u.%u.%u.%u\n", ans >> 24, (ans << 8) >> 24, (ans << 16) >> 24, (ans << 24) >> 24);
        printf("%u.%u.%u.%u\n", mask >> 24, (mask << 8) >> 24, (mask << 16) >> 24, (mask << 24) >> 24);

    }

    return 0;
}