全文目录
☘前言☘
🎁主要知识点
位与运算
位与的常见使用
✨奇偶判定
✨取末尾几位
✨消除末尾几位
✨判断2的幂
📓课后习题
191. 位1的个数
剑指 Offer 15. 二进制中1的个数
1356. 根据数字二进制下 1 的数目排序
762. 二进制表示中质数个计算置位
231. 2 的幂
📑写在最后
☘前言☘
今天是算法零基础打卡的第42天，题目本身不难，主要是为了理解位运算的。上链接：
《算法零基础100讲》(第42讲) 位运算 (位与) 入门
全文大约阅读时间： 20min
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
🎁主要知识点
位与运算
基本逻辑就是与或非，与操作就是两个同为1结果为1，否则为0，真值表如下
x y 结果(x&y)
1 1 1
0 1 0
1 0 0
0 0 0
通过这个真值表我们可以用来取数等操作，我们看下常见的操作
位与的常见使用
✨奇偶判定
- 二进制末位
偶数 0
奇数 1
所以我们很容易写出来代码
if(n&1) xxx;
上面的就是表示判断是否是奇数 因为奇数末尾为1
✨取末尾几位
#include <stdio.h> int main() { int x; scanf("%d", &x); printf("%d\n", (x & 0b11111) ); return 0; }
在计算机中ob是表示的是二进制数，我们把末尾五个作为1其它为零按位与的结果就是最后五位的值。
✨消除末尾几位
#include <stdio.h> int main() { int x; scanf("%d", &x); printf("%d\n", (x & 0xffffffe0) ); return 0; }
相同的道理，如果我们把末尾五位0，其它的置为1就可以抹去最后五位。
✨判断2的幂
2的幂减去1与之相与一定结果是0.
例如 10000000 与 01111111 结果是0
(x & (x-1)) == 0
📓课后习题
191. 位1的个数
191. 位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
解题思路
按照计算2的幂的思路 每次n&(n-1)会消去最低位的1 所以多次循环就好了。
int hammingWeight(uint32_t n) { int count = 0; while(n){ n = n & (n - 1);//消去最低位1 count ++; } return count; }
剑指 Offer 15. 二进制中1的个数
剑指 Offer 15. 二进制中1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。
解题思路
直接用位移来比较计算就好了。。换个思路。(这貌似和上题一毛一样。。)
int hammingWeight(uint32_t n) { int count = 0; for(int i = 0;i < 32;i++) if(n & ((uint32_t)1 << i)) count++; return count; }
1356. 根据数字二进制下 1 的数目排序
1356. 根据数字二进制下 1 的数目排序
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
解题思路
人类的本质就是套娃呗？这个就是把昨天的排序api套上今天的位预算康康。
int cmp(int *a,int *b){ int lena = 0,lenb = 0; for(int i = 0; i < 32;i++){//算1的个数 if((*a)>>i&1) lena++; if((*b)>>i&1) lenb++; } if(lena == lenb) return *a > *b;//一样直接比大小 return lena > lenb; //不一样升序排列 } int* sortByBits(int* arr, int arrSize, int* returnSize){ qsort(arr,arrSize,sizeof(int),cmp); *returnSize = arrSize; return arr; }
762. 二进制表示中质数个计算置位
762. 二进制表示中质数个计算置位
给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
解题思路
看了看数据范围，最多也就只有撑死也就有20个1 所以我把20以内所有的质数干了个表，查表就完事了。这我没用任何算法，20以内。直接算就完事了。。。
bool f[21] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0};//质数表 bool isright(int n){ int len = 0; for(int i = 0;i <32;i++) if((n>>i) & 1) len++;//统计个数 return f[len]; //是否是质数 } int countPrimeSetBits(int left, int right){ int ans = 0; while(left<=right) if(isright(left++)) ans++; //判断是否符合条件 return ans; }
231. 2 的幂
231. 2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
解题思路
根据大哥说的，算就完事了。注意<=0都是false
bool isPowerOfTwo(int n){ if(n <=0 ) return false; return !(n &(n-1)); }
一行代码版
bool isPowerOfTwo(int n){ return n <=0 ? false : !(n &(n-1)); }
