算法基础班–第一章–14.位运算模板

算法模板

1. 求n的第k位数字 ： n>>k & 1

• 先把第k位移到最后一位， n>>k
• 看个位是几， x & 1

2. lowbit(n) = n & -n : 返回n的二进制形式的最后1位是多少

• -x = ~x + 1
• x & -x = x & (~x + 1)

例1：

int main() {
    int n = 10;
    for (int k = 3; k >= 0; k-- ) cout << (n >> k & 1); //结果是1010
    return 0;
}

例2：（本题完整代码）

• 方法：
  统计x中1的个数：每次把最后的1去掉（减掉），当x=0，里面没有1时，统计减了多少次，就有多少个1

#include <iostream>
#include <cstdio>

using namespace std;

int lowbit(int x) { //返回x的二进制形式的的最后一位1是多少
    return x & -x;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        int res = 0;
        while (x)   x -= lowbit(x), res++; //每次减去x的最后一位1
        cout << res << ' ';
    }
    return 0;
}