鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

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

来源:互联网 作者:佚名 时间:2018-02-27 09:48
位运算 就是二进制下数的运算。。 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 (1X) =

位运算

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

      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 * 2B   , A  >> B= A / 2 (整除)    

      主要用于代替代码中连续乘除 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序列

        样例输入:

        4

        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(n2),能拿一半的分(暴力出奇迹)

      正解:

              因为  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

样例输入:

4

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

 

                  

 

                                                                                                                                                                     (第一次写,写的不好请见谅,溜了溜了)

                                                                                                                                                            

网友评论
<