| 邏輯運算 | 規則 | 符號 |
|---|---|---|
| 與 | 只有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，
然后他會給你一組資料，例如
輸入：
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，所以我們就得到
00
01
01
11
11
所有排列就為
然后我們就是計算出對應的十六進制資料了
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文章給我的思路
位操作基礎篇之位操作全面總結
位運算——強大得令人害怕
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/77828.html
標籤：其他