位运算基础（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

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

000110010与000100000

按位异或后得到

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。

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

输入：

输出:

Disk set 1 is valid, contents are: 6C7A79EDFC

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

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

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

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

所有排列就为

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

6C7A79EDFC (01101100 01111010 01111001 11101101 11111100 in binary)

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

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文章给我的思路

位操作基础篇之位操作全面总结

位运算——强大得令人害怕

巴特西

位运算基础（Uva 1590，Uva 509题解）

Uva 1590

Uva 509

总结

最新文章

热门文章