算法基础学习之位运算符

前置知识学习:

1.逻辑运算符：与&& 或|| 非! 与运算: 1&&1=1 1&&0=0 0&&1=0 0&&0=0 或运算: 1||1=1 0||1=1 1||0=1 0||0=0 非运算: !1=0 !0=1 计算机中一般来说int存储32位的数据 -2147483648 ~ 2147483647

位运算符

定义：在处理整形数据的时候，我们可以采用位运算的形式对这个整形数据的二进制表达形式中的每一个位进行操作，通常来讲，同样的处理数据，使用位运算比使用加减乘除在计算机运行的快 操作：位运算通常有与(&)或(|)异或(^)非(~)左移(<<)右移(>>)等操作

小技巧

判断奇数偶数

int num=100; cout<<num<<"是:"<<(((num&1)==0)?"偶数":"奇数")<<endl;

判断某一个二进制位是1还是0

int x=86; cout<<((((1<<4)&x)>>4)==0?"是0":"是1")<<endl;//1右移 cout<<(((x>>4)&1)==0?"是0":"是1")<<endl;//数那位左移

交换两个整数变量的值

a=a^b;b=b^a;a=a^b;

介绍一下异或运算的妙用，消除重复数据 A^A=0 B^0=B 满足交换律

练习题目

1.找出唯一成对的数字，1-1000这1000个数字存放在一个长度为1001的数组里面，只有唯一的一个元素重复，其他的只出现一次，每一个数组元素只能访问一次且不能借助辅助数组来完成，设计一种算法完成它.

#include<iostream> #include<cstdio> #include <string.h> using namespace std; #define N 11 int main(){ int a[N]={1,2,3,4,5,6,7,8,9,10,4}; int sum=0; for(int i=1;i<=N-1;i++){ sum=sum^i; } for(int i=0;i<N;i++){ sum=sum^a[i]; } cout<<"重复的数字为"<<sum<<endl; int b[N]; memset(b, 0, sizeof(b)); for(int i=0;i<N;i++){ b[a[i]]++; } for(int i=1;i<N;i++){ if(b[i]==2) cout<<"重复的数字为"<<i<<endl; } return 0; }

2.找出落单的那个数，一个数组里面除了某一个数字之外，其他的数字都出现了两次，请找出这一个落单的数字

#include<iostream> #include<cstdio> using namespace std; #define N 11 int main(){ int a[N]={1,1,2,2,3,3,7,8,8,9,9}; int sum=0; for(int i=0;i<N;i++){ sum=sum^a[i]; } cout<<sum<<endl; return 0; }

3.二进制中1的个数，输入一个整数，输出该整数里面二进制表示1的个数

#include<iostream> #include<cstdio> using namespace std; #define N 11 int transfer(int x,int k){ int ans=0,yu,times=1; while(1){ yu=x%k; x=x/k; ans=times*yu+ans; times=times*10; if(x<k){ ans=ans+x*times; break; } } return ans; } int main(){ // cout<<transfer(1000,2)<<endl; int x=1000,count=0,count1=0,count2=0; for(int i=0;i<32;i++){ if((x&(1<<i))==(1<<i)) count++; } for(int i=0;i<32;i++){ if(((x>>i)&1)==1) count1++; } while(x!=0){ x=(x-1)&x; count2++; } cout<<count<<" "<<count1<<" "<<count2<<endl; return 0; }

4.用一条语句判断一个整数是不是2的整数次方

if((x-1)^x==0)cout<<"YES"<<endl;