文章目录
前言
一、位运算习题，模板
1.模板
2.AcWing801. 二进制中1的个数
AC代码
二、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：位运算，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上，本博客所有习题和模板来自：ACWing算法基础课
一、位运算习题，模板
1.模板
本模板来自：ACWing算法基础课
求n的第k位数字: n >> k & 1 返回n的最后一位1：lowbit(n) = n & -n
2.AcWing801. 二进制中1的个数
本题链接：AcWing801. 二进制中1的个数
本博客给出本题截图：
AC代码
#include <cstdio> using namespace std; int lowbit(int x) { return x & -x; } int main() { int n; scanf("%d", &n); while (n -- ) { int a, res = 0; scanf("%d", &a); while (a) { a -= lowbit(a); res ++; } printf("%d ", res); } return 0; }
二、时间复杂度
关于位运算的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
