关于位运算的一些小记

目录

1.判断一个整数是不是2的幂

2.判断一个整数是不是3的幂

3.大于n的最小的2次幂的数

4.交换两个数

 5.找到1-n中缺失的数字

6.判断数组中2个出现次数为奇数的数

6.求给定范围内所有数字&的结果

7. 求出现次数少于m的数 

---

1.判断一个整数是不是2的幂

 提取出二进制里最右侧的1

bool is_mi(int n){//注意运算符的优先级，这里要加括号 return n>0&&n==(n&(~n+1));
}

2.判断一个整数是不是3的幂

如果一个数字是3的次幂，那么这个数一定 只含有3的这个质数因子，1162261467是int范围内最大的3次幂，如果1162261467%n!=0那么就不是3的次幂

bool is_mi(int n){return n>0&&1162261467%n==0;
} 

3.大于n的最小的2次幂的数

如果n是负数直接返回1，否则的话进行位运算的操作

int  mi(int n){if(n<0)return 1;n--;n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;return n+1;
}

4.交换两个数

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

 5.找到1-n中缺失的数字

int missing(int n,int a[]){int x=0;for(int i=0;i<n;i++){x^=i;x^=a[i];}x^=n;return x;
} 

6.判断数组中2个出现次数为奇数的数

void que2(){
int x=0;
for(int i=0;i<12;i++)
x^=a[i];
int y=x&(~x+1);
int x1=0;
for(int i=0;i<12;i++){if((a[i]&y)==0)x1^=a[i];
}
x^=x1;
cout<<x<<" "<<x1; 
}

6.求给定范围内所有数字&的结果

int rek(int l,int r){while(l<r)r-=r&(~r+1);return r;
}

7. 求出现次数少于m的数 

void  kk(int m){
memset(cnt,0,sizeof(cnt));
for(int i=0;i<12;i++){for(int j=0;j<32;j++)cnt[j]+=(a[i]>>j)&1;
}
int ans=0;
for(int i=0;i<32;i++){if(cnt[i]>0&&cnt[i]<m){ans|=1<<i;}
}
cout<<ans; }