目录
传送门
知识点
位与运算的常见语法
1、判断奇偶性
2、取末尾x位
3、2的幂判定
课后习题
1.位1的个数
2.剑指offer 15.二进制中1的个数
3.根据数字二进制下1的数目排序
4.二进制表示中质数个数计算置位
5.2的幂
传送门
《算法零基础100讲》(第42讲) 位运算 (位与) 入门_英雄哪里出来-CSDN博客位运算位与的初步入门https://blog.csdn.net/WhereIsHeroFrom/article/details/120876417
知识点
位与运算符 &
运算规则 0&0=0; 0&1=0; 1&0=0; 1&1=1; （即只有当两者都为1才为1）
例如：
3 & 7 = 0000 0011
& 0000 0111
= 0000 0011
位与运算符 &
运算规则 0&0=0; 0&1=0; 1&0=0; 1&1=1; （即只有当两者都为1才为1）
例如：
3 & 7 = 0000 0011
& 0000 0111
= 0000 0011
位与运算的常见语法
1、判断奇偶性
原理：因为奇数的末尾位一定是为 1 的，而偶数的末尾数一定为 0
所有判断奇偶性我们可以写成下面这样：
if(x & 1){
printf("%d 为奇数n",x);
}
else{
printf("%d 为偶数n",x);
}
2、取末尾x位
当我们只需要保留一个数的后x位而其他位置零时，我们可以将该数和二进制下末尾x位为1的数进行按位与运算
例如：保留x的后5位
#include
int main() {
int x;
scanf("%d", &x);
printf("%dn", (x & 0b11111) );//(0b开头是表示二进制数)
return 0;
}
3、2的幂判定
判断一个数是不是正数2的幂时，可以这样判断
(x & (x-1)) == 0
因为一个数 k如果为2的幂，那么其的二进制形式一定为 100…00
而 k-1 为 011…11
这两个数执行按位与运算结果一定是为 0
原理：因为奇数的末尾位一定是为 1 的，而偶数的末尾数一定为 0
所有判断奇偶性我们可以写成下面这样：
if(x & 1){ printf("%d 为奇数n",x); } else{ printf("%d 为偶数n",x); }
2、取末尾x位
当我们只需要保留一个数的后x位而其他位置零时，我们可以将该数和二进制下末尾x位为1的数进行按位与运算
例如：保留x的后5位
#include
int main() {
int x;
scanf("%d", &x);
printf("%dn", (x & 0b11111) );//(0b开头是表示二进制数)
return 0;
}
3、2的幂判定
判断一个数是不是正数2的幂时，可以这样判断
(x & (x-1)) == 0
因为一个数 k如果为2的幂，那么其的二进制形式一定为 100…00
而 k-1 为 011…11
这两个数执行按位与运算结果一定是为 0
当我们只需要保留一个数的后x位而其他位置零时，我们可以将该数和二进制下末尾x位为1的数进行按位与运算
例如：保留x的后5位
#includeint main() { int x; scanf("%d", &x); printf("%dn", (x & 0b11111) );//(0b开头是表示二进制数) return 0; }
判断一个数是不是正数2的幂时，可以这样判断
(x & (x-1)) == 0因为一个数 k如果为2的幂，那么其的二进制形式一定为 100…00
而 k-1 为 011…11
这两个数执行按位与运算结果一定是为 0
课后习题
1.位1的个数
位1的个数https://leetcode-cn.com/problems/number-of-1-bits/
题目描述：
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
思路：每次判断其最低位是否位1，并执行左移
int hammingWeight(uint32_t n) {
int ans=0;
while(n){
if(n & 1) //判断最末位是不是 1
++ans;
n >>= 1; //每次左移一位(左边补零) 例如 1011 左移一位后 0101
}
return ans;
}
2.剑指offer 15.二进制中1的个数
剑指 Offer 15. 二进制中1的个数https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
题目描述：
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。
思路：和上题一模一样的题，也可以这样做
int hammingWeight(uint32_t n) {
int ans = 0,i;
for(i=0;i<=31;++i){
if(n & (1u<
3.根据数字二进制下1的数目排序
根据数字二进制下 1 的数目排序https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/
题目描述：
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
int count(int x){
int ans = 0;
while(x){
if(x & 1)
++ans;
x >>= 1;
}
return ans; //统计 1 的个数
}
int cmp(const void *a,const void *b){
int na = count(*(int*)a),nb = count(*(int*)b);
if(na != nb)
return na > nb; // 先按 1 的个数排序
else
return *(int*)a > *(int*)b; // 再按 大小排序
}
int* sortByBits(int* arr, int arrSize, int* returnSize){
qsort(arr,arrSize,sizeof(int),cmp);
*returnSize = arrSize;
return arr;
}
4.二进制表示中质数个数计算置位
二进制表示中质数个计算置位https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/
题目描述：
给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
思路：运用按位与运算统计每个数的二进制下1的个数，判断是不是质数（看到质数，复习复习之前学的质数筛选法，这题没必要，纯粹复习一下，结果慢的一批，还费内存藍）
#define maxn 1000001
int f[maxn];
void eth(int R){
memset(f,0,sizeof(f));
f[0] = f[1] = 1;
int i;
long long j;
for(i=2;i<=R;++i){
if(!f[i]){
for(j=(long long)i*i;j<=R;j+=i){
f[j] = 1;
}
}
}
}
int count(int x){
int ans = 0;
while(x){
if(x & 1)
++ans;
x >>= 1;
}
return ans; //统计 1 的个数
}
int countPrimeSetBits(int left, int right){
int ans = 0;
eth(right);
while(left <= right){
if(!f[count(left)])
++ans;
++left;
}
return ans;
}
5.2的幂
2 的幂https://leetcode-cn.com/problems/power-of-two/
题目描述：
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
bool isPowerOfTwo(int n){
return n <= 0 ? false:!(n & (n-1));
}
今天打卡完成！！！
