n的二进制表示中第k位是几
思想
-
先把第k位移到最后一位
实现方式是用右移运算
n >> k -
再看最低位是几
假设前一步得到x， 最低位为
x & 1
代码
# include<iostream>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
int res = n >> k & 1; // 注意 k = 0 就是第 0 位
cout << res;
return 0;
}
lowbit(x)
lowbit(x)是x的二进制表达式中最低位的1所对应的值， 是树状数组的一个基本操作
举个例子
\(x = (1010)_2\) 则 \(lowbit(x) = (10)_2\)
\(x = (101000)_2\) 则 \(lowbit(x) = (1000)_2\)
思想
\(lowbit(x) = x \& (-x)\)
拿上面的例子一来看 \(x = (0 000 1010)_2, -x = (11110110)_2\)
解释一下为什么， 在存储过程中是补码， 最高位为符号位， 在与运算时符号位也会参与运算
上面相与得到 \((00001010)_2 \& (11110110)_2 = (00000010)_2\)
又有 \((-x) = {\sim}x + 1\) ~是非运算比如 \(x = (0 000 1010)_2, {\sim}x = (11110101)_2\)
代码
# include <iostream>
using namespace std;
int lowbit1(int x) {
return x & (-x);
}
int lowbit2(int x) {
return x & (~x + 1);
}
int main()
{
int x;
cin >> x;
cout << lowbit1(x) << endl << lowbit2(x);
}
应用
求x二进制表示中1的个数
题目
给定一个长度为 n 的数列，请你求出数列中每个数的二进制表示中 1 的个数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，表示整个数列。
输出格式
共一行，包含 n个整数，其中的第 i个数表示数列中的第 i 个数的二进制表示中 1的个数。
数据范围
\(1≤n≤100000\)
\(0≤数列中元素的值≤10^9\)
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
代码
# include<iostream>
using namespace std;
int lowbit(int x) {
return x & (-x);
}
int count_one(int x) {
int count = 0;
while(x != 0) {
x -= lowbit(x);
count ++;
}
return count;
}
int main(){
int n, x;
cin >> n;
for(int i = 0; i < n; i ++){
cin >> x;
cout << count_one(x) << " ";
}
}