目录

传送门

知识点

位与运算的常见语法

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

位与运算的常见语法

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的个数，判断是不是质数（看到质数，复习复习之前学的质数筛选法，这题没必要，纯粹复习一下，结果慢的一批，还费内存