首页 > > 程序设计 > C/C++ >

[NOIP模拟题] 位运算入门详解+富有诗意的模拟题

2018-06-17 21:41:15来源：未知阅读 ()

位运算

就是二进制下数的运算。。

1. and 运算 “&”

对于数 A , B 在二进制下的任意第 i 位 Ai，Bi，当且仅当 Ai=Bi=1 时，Ai & Bi=1

1101 & 100 ：

1 1 0 1

& 0 1 0 1

0 1 0 1

一般用于二进制取位操作，例如一个数 and 1的结果就是取二进制的最末位，

A & (1<<X) = 取出二进制下 A 的末第 X-1 位

2. or 运算 “ | ”

对于数 A , B 在二进制下的任意第 i 位 Ai，Bi，当 Ai=1 或 Bi=1 时，Ai | Bi=1

or运算通常用于二进制特定位上的无条件赋值，对二进制任意一位 or 1 就等于将这

一位赋值为 1

1101 | 100 ：

1 1 0 0 1

or 1 0 0 1 1

1 1 0 1 1

3. xor 运算 "^"

对于数 A , B 在二进制下的任意第 i 位 Ai，Bi，当 Ai=Bi 时，Ai ^ Bi=0，

Ai ！=Bi 时，Ai ^ Bi=1 按位异或运算, 对等长二进制模式按位或二进制

数的每一位执行逻辑按位异或操作. 操作的结果是如果某位不同则该位为1,

否则该位为 0

00101 ^ 11100 ：

0 0 1 0 1

^ 1 1 1 0 0

1 1 0 0 1

一件美妙的事情，xor运算的逆运算是它本身

就是（A xor B) xor B = A

所以，我们得到了一个神奇的swap的过程：

void swap(int &a,int &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    return；
}

注意：在交换两个数时，若出现 a == b 的情况，就会翻车

因为任意一个数 XOR 本身都会得到 0

4. not 运算 "~"

取反，顾名思义若 A = "10010" , B=~A，那么 B = "01101"

使用 not 运算时要格外小心，你需要注意整数类型有没有符号。如果 not 的对象是无符号整数（不能表示负数的那种）

那么会得到它与上界的差。

int main()
{
    unsigned short a=100;
    a = ~a;
    printf( "%dn", a );    
    return 0;
}

这其中的输出的 a = 65435.

若对于有符号的整数，计算机用 00 到 $7FFF 依次表示 0 到 32767 的数，剩下的 $8000 到 $FFFF 依次表示 -32768 到 -1 的数。

32位有符号整数的储存方式也是类似的。稍加注意你会发现，二进制的第一位是用来表示正负号的，0表示正，1表示负，那么

对于 0 来说，他不属于整数或负数，但是占用了 00 的位置，所以导致该范围中正数比负数少一个，对一个有符号的数进行not运算

后，最高位的变化将导致正负颠倒，并且数的绝对值会差1。

所以 not a实际上等于 -a-1（或 -a= not a+1）。这种整数储存方式叫做“补码”（正数的补码和原码相同，负数的补码是该数的绝对值的

二进制形式，按位取反后再加 1）。

5. shl运算 “ <<”和 shr 运算 “>>”

A << B 等于将 A 向左移 B 位（在二进制 A 后面添上 B 个0），A >> B 等于将 A 向右移 B 位（去掉最后 B 位）

所以 A << B = A * 2^B ， A >> B= A / 2^B （整除）

主要用于代替代码中连续乘除 2 的运算，要快一丢丢（二分查找，堆的插入）。

常用的就这么几个，按运算优先级排为

1 ~ not

2 << , >> shl ,shr

3 & and

4 ^ xor

5 | or

6 |= , &= , ^= .........

例题T1

（很诗意。。。）

信(believe.cpp/c/pas)

背景描述：

一切死亡都有冗长的回声 —— 《一切》北岛

给定一个N个元素的序列A，

定义Bi = (Ai and A1) + (Ai and A2) + (Ai and A3)+ ...... + (Ai and An)

定义Ci = (Ai or A1) + (Ai or A2) + ... + (Ai or An)

求B和C序列。

输入格式：

第一行一个整数N表示序列长度

接下来一行N个整数，第i个整数为Ai

输出格式：

第一行N个整数输出B序列

第二行N个整数输出C序列

样例输入：

3 5 1 1

样例输出：

6 8 4 4

16 22 10 10

数据规模：

对于50%的数据， N <= 1000

对于100%的数据， N <= 100000， Ai <= 100000

题目大意：

B , 对于每一个 Ai ，求 Ai 与每一个 A 的 & 值的和

C , 对于每一个 Ai ，求 Ai 与每一个 A 的 | 值的和

分析：

朴素算法，枚举 Ai，再枚举 Aj ，直接计算，复杂度 O（n²），能拿一半的分（暴力出奇迹）

正解：

因为 B[i]=(Ai and A1) + (Ai and A2) + (Ai and A3)+ ...... + (Ai and An)

假设两个数 X , Y . 因为 & 运算的值只与参与运算的两个二进制数相同的那一位有关

X.1 & Y.1 + X.2 & Y.2+.....+ X.n & Y.n = X & Y （将 Y 的二进制拆分成每一位后逐一计算，值相等）

所以，我们只需要统计A1-An中二进制每一位上 1 的出现次数（0就不管了，任意一个数 & 0=0）sum[i]

如果 Ai.i =1 , B[i].i = sum[i]*(1<<i ); /*&值乘以出现次数*/ 若 Ai.i = 0, 那就 =0；

把每一位的值相加，就得到 B[i] 了

同理，对于 C[i] 也可以这样拆分，不同的是，

若 C[i].i=1 那么这一位 or 每一个Aj.i = 1, C[i].i = n*(1<<i);

若 C[i].i=0 那么就要考虑第 i 位上出现 1 的次数（同sum[i]） C[i].i = sum[i]*(1<<i);，再把每一位累加。

代码如下复杂度 O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define pr(x) printf("%lld ",x)
#define sc(x) scanf("%lld",&x)
#define go(i,x,a) for(int i=a;i<x;i++)
#define ll long long
using namespace std;
ll n,map[100005],sum[20]; 
ll b[100005],c[100005]; 
int main()
{
   cin>>n;
   go(i,n,0)
   {
         sc(map[i]);
         go(j,20,0)  
            if(map[i]&(1<<j)) sum[j]++;//统计第j位 1 的出现次数 
   }
   go(i,n,0)
   {
         go(j,20,0)
         {
              if(map[i]&(1<<j)) // map[i]的第j位=1 
              {
                   b[i]+=sum[j]*(1<<j);
                   c[i]+=n*(1<<j);
         }
         else {           // map[i]的第j位=0 
             c[i]+=sum[j]*(1<<j);
         }
      }
   }
   go(i,n,0) pr(b[i]); printf("\n");
   go(i,n,0) pr(c[i]);
   return 0;
}//ME.FORY

例题T2

（搞不懂这些人为什么非要加一句诗）

题(problem.cpp/c/pas)

背景描述：

黑夜给了我黑色的眼睛

我却用它寻找光明 ——《一代人》顾城

已知一个N个元素的非负整数序列A，

定义Bi = (Ai and A1) + (Ai and A2) + (Ai and A3)+ ...... + (Ai and An)

定义Ci = (Ai or A1) + (Ai or A2) + ... + (Ai or An)

给出B和C序列，构造一个满足条件的A序列，如果没有，输出-1

输入格式：

第一行一个整数N。

接下来一行N个整数表示B序列

接下来一行N个整数表示C序列

输出格式：

如果有解，输出一行N个整数表示你构造的A序列， SPJ很脆弱，所以你构造的序列每个整数必须在[0,8191]这个区间内，我们保证如果有解，那么定存在一个解满足每个元素均在[0,8191]内，否则输出-1

样例输入：

6 8 4 4

16 22 10 10

样例输出：

3 5 1 1

数据规模：

对于30%的数据， N = 2

对于70%的数据， N <= 200

对于100%的数据， N <= 100000， Bi , Ci<= 1000000000

题目大意：

和第一题正好反过来，但要考虑无解和超出范围的问题

分析：

在那遥远的地方，有一个神奇的式子

对于任何非0 A , B 有 A & B + A | B = A + B

又证

　　C[i] + B[i] = (A[i] & A[1])+(A[i] | A[1])+(A[i] & A[2])+(A[i] | A[2])+......

= (A[i] + A[1])+(A[i] + A[2])+(A[i] + A[3])+...

= n*A[i] + ∑(A[i])

所以 ∑(C[i] + B[i])= 2*n*∑(A[i])

在读入的同时我们可以直接得到 ∑(A[i])，再有 C[i] + B[i] -∑(A[i]) = n*A[i]

直接得到每一个 A[i] 就OK了

注意:

注意判断 A[i] 是否大于 8191 和无解的情况，当任意一步计算时不能整除则无解

注意变量要开long long，输出不能用 cout ，否则会超时

代码如下：复杂度O（n）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define pr(x) printf("%lld ",x)
#define sc(x) scanf("%lld",&x)
#define go(i,x,a) for(int i=a;i<x;i++)
#define ll long long
#define p_q priority_queue
#define maxx  8191*n
#define MM 100005
using namespace std;
ll n,map[MM],b[MM],c[MM],tt=0; 
int main()
{
   cin>>n;
   go(i,n,0)  
   {
        sc(b[i]);
        tt+=b[i];
   }
   go(i,n,0)  
   {
       sc(c[i]);
       tt+=c[i];//  累加 
   }
   if(tt%2!=0||tt%n!=0)// 判断是否无解 
   {
         cout<<"-1";
         return 0;
   } 
   tt=(tt/2)/n;
   if(tt>maxx) 
   {
         cout<<"-1";
         return 0;
   } 
   go(i,n,0)
   {
         map[i]=b[i]+c[i]-tt;
         if(map[i]%n!=0||map[i]>maxx) 
         {
             cout<<"-1"; return 0;    
      }
         map[i]=map[i]/n; //   直接计算 
   }
   go(i,n,0) pr(map[i]);
   return 0;
}//ME.FORY