目录
传送门
知识点
位与运算符 &
运算规则 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 <stdio.h> int main() { int x; scanf("%d", &x); printf("%d\n", (x & 0b11111) );//(0b开头是表示二进制数) return 0; }
3、2的幂判定
判断一个数是不是正数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<<i)){ //判断第i位的状态
++ans;
}
}
return ans;
}3.根据数字二进制下1的数目排序
根据数字二进制下 1 的数目排序https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/
题目描述：
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
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的个数，判断是不是质数（看到质数，复习复习之前学的质数筛选法，这题没必要，纯粹复习一下，结果慢的一批，还费内存