位运算基础(Uva 1590,Uva 509题解)

逻辑运算 规则 符号
只有1 and 1 = 1,其他均为0 &
只有0 or 0 = 0,其他均为1 |
也就是取反 ~
异或 相异为1相同为0 ^
同或 相同为1相异为0,c中没有,但可以异或后取反
左移 各二进位全部左移若干位,高位丢弃,低位补0 <<
右移 各二进位全部右移若干位,对无符号数,高位补0,有符号数,有的补符号位(算术右移),有的补0(逻辑右移) >>

光这么说可能比较抽象,我们通过两道题开看这个知识点。

Uva 1590

题目链接

简单描述一下,就是给一组ip,然后计算出这组IP所在的最小子网掩码和最小的IP,例如:

输入:

3
194.85.160.177
194.85.160.183
194.85.160.178

输出:

194.85.160.176
255.255.255.248

我们简单来算一下,上述IP也就是

11000010.01010101.10100000.10110001
11000010.01010101.10100000.10110111
11000010.01010101.10100000.10110010

我们可以发现,前29位都是相同的,只有最后三位不同,所以自然最小IP与子网掩码就算出来了

11000010.01010101.10100000.10110000
11111111.11111111.11111111.11111000

转换为十进制也就是

194.85.160.176
255.255.255.248

所以,思路也很简单,我们只有从左开始按位同或,遇到不同的地方停止,后面补0便是子网掩码,然后再与IP进行按位与操作就可以得到最小IP了,下面我们来看代码。

首先是转换IP,很巧的是ipv4正好是32位,也就是和int整型的长度是相同的,不知道是巧合还是必然。

int n;
unsigned int num[1009] = {};
while(cin>>n)
{
    memset(num, 0, sizeof(num));
    char ip[40];
    cin>>ip;
    int c = 0;
    for(int j=0;j<strlen(ip);j++)
    {
        if(ip[j] == '.')
        {
            num = (num<<8) + c;
            c = 0;
        }
        else
            c = c*10 + ip[j]-'0';
    }
    num = (num<<8) + c;
}

这样我们就把IP转成int表示了,下面我们开始进行位运算,找到第一个不同的地方

unsigned int ans2 = ~0, ans1;
for(int i=1;i<n;i++)
{
    unsigned int q = num[i] ^ num[0]; // 与第一位按位异或
    while(q) //寻找第一位不同的地方然后停止
    {
        ans2 &= ~(q | (q-1));//与低一位按位或然后取反
        q = q&(q-1);//与低一位按位与
    }
    //ans2 &= q;
}
ans1 = ans2 & num[0]; //子网掩码与第一个与即为最小ip

与低一位进行按位或操作为的是防止后面的相同,举个栗子

000110010000100000

按位异或后得到

000010010

如果不与自身进行或操作,则会导致第一位不同的地方后面出现1,所以我们要循环与低一位进行或操作,比如上述进行第一次 ~(q | (q-1)) 操作后得到ans2

111101100

而第二个 q = q&(q-1) 则是消去后面的1,我们继续循环

q就便为 000010000

然后继续 ans2 &= ~(q | (q-1)) ,ans2就变为了

111100000 ,即为我们子网掩码,然后再与第一个IP进行与操作即得到最小IP,ans1。

最后我们转回IP表示形式

int sans[4]={};
int pos = 0;
while(ans1 != 0)
{
    sans[pos++] = ans1%(1<<8);
    ans1 >>= 8;
}
for(int i=3;i>=0;i--)
{
    cout<<sans[i];
    if(i)
        cout<<".";
}
cout<<endl;

Uva 509

题目链接

这题是关于某种Raid磁盘阵列的工作原理的题目,也就是说这种Raid分为校验位和数据位,

排列如下,可以看出校验位是的坐标为(row,n%col),n为0~row。

然后他会给你一组数据,例如

输入:

5 2 5
E
0001011111
0110111011
1011011111
1110101100
0010010111

输出:

Disk set 1 is valid, contents are: 6C7A79EDFC

先来解释一下前三个数字分别为d,s,b

d为磁盘数量,这里为5,s为每个block占据的位数,这里是2,b为有多少数据,其实就是有多少行,然后E代表的是偶校验,也就是异或等于0, O代表的是奇校验,异或等于1,举个栗子,如下图

假如disk3的第一位缺失了,那么我们就可以得到0^0^?^1^0=0,于是我们就可以计算出Disk3是1.

然后就是输入数据,它的一行代表第一个磁盘的数据,比如第一个disk就是 0001011111 ,然后一个block又是2,所以我们就得到

所有排列就为

然后我们就是计算出对应的十六进制数据了

6C7A79EDFC (01101100 01111010 01111001 11101101 11111100 in binary)

然后还有可能出现数据丢失,例如

3 5 1
O
11111
11xxx
x1111

x就是丢失数据。

题目很长,然后我们来看思路,思路其实很简单。

读入数据后,我们第一步首先是根据奇校验还是偶校验进行数据补全,如果出现一列中有两个丢失就是错误数据了,然后补全的同时我们要进行检测,看数据是否符合对应的校验规则。

然后如果数据错误,我们就输出 Disk set x is invalid. ,结束程序,否则我们就进行解码操作,将对应数据转成16进制输出就行了,所以这个程序就三个函数,

  • 检查并修补数据函数
  • 解码函数
  • 主函数

程序头

#include <stdio.h>
#include <string.h>
#include <iostream>
#define maxn 6400

using namespace std;

int d, s, b;
char type;
int itype;
char disk[7][maxn];

检查并修补数据函数

bool fix(int row, int col){
    for(int i = 0;i<col;i++){
        //printf("col%d\n", col);
        int init = -1, x, y, flag = 0;
        for(int j = 0;j<row;j++){
            if(disk[j][i] == 'x'){
                if(flag) return false;
                x=j;
                y=i;
                disk[j][i] = '0';
                flag = 1;
            }
            if(init == -1){
                init = disk[j][i] - '0';
            }else{
                init ^= disk[j][i] - '0';
            }
        }
        if(init != itype && flag == 0) return false;
        else if(init != itype && flag == 1) disk[x][y] = '1';
    }
    return true;
}

解码函数

void decode(int d, int s, int b){
    //int x = 0, y = 0;
    //char str[4];
    int idx = 0;
    int num = 0;
    for(int i=0;i<b;i++){
        for(int j=0;j<d;j++){
            if(i%d == j){
                continue;
            }
            for(int k=0;k<s;k++){
                num <<= 1;
                num += (disk[j][i*s+k] - '0');
                idx++;
                if(idx == 4){
                    printf("%X",num);
                    num = 0;
                    idx = 0;
                }
            }
        }
    }
    if(idx) printf("%X",num<<(4-idx));
}

主函数

int main(){
    int idx = 1;
    while(scanf("%d", &d) == 1 && d != 0){
        scanf("%d%d\n%c", &s, &b, &type);
        if(type == 'E') itype = 0;
        else itype = 1;
        for(int i=0;i<d;i++){
            scanf("%s", disk[i]);
        }
        printf("Disk set %d", idx++);
        if(fix(d, s*b)){
            printf(" is valid, contents are: ");
            decode(d, s, b);
            printf("\n");
        }
        else
            printf(" is invalid.\n");
    }
}

总结

为了备考pat,又捡起了算法题开始刷,慢慢从零基础开始学吧,很痛苦,感觉自己写代码还是不够优秀,很多地方逻辑存在一些问题,一些自认为优的地方还不够优化,看了别人的代码才发现自己的弊端和冗余。

还有很多基础的知识掌握的不够牢靠,比如下面说的位运算,很多取巧的地方哈市参考了其他的Blog才醍醐灌顶,感谢下面的blog文章给我的思路

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章