n的二进制表示中第k位是几

知识点

按位与运算符

• &位运算符
  • 用于两个数字之间时，&运算符会将两个数字的二进制表示进行逐位与运算
  • 运算规则为：只有当两个位都为1时，结果才为1，否则为0

计算机语言中的各种码

• 给定$(x)_2 = 1010$，x为32位整数
• 原码：0000 … 1010
• 反码：1111 … 0101
• 补码：1111 … 0110 (取反加一)

假设n = 6
n的二进制表示为0110
1的二进制表示为0001
那么n & 1的结果为0000

解题思路

• 求数字n的第k位，就将数字n右移k位并
  • 先把第k位移动到最后1位
  • 并把移动后的个位数 &1

实现代码

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n = 10;

	for(int k = 3; k >= 0; k --){
		cout << (n >> k & 1);
	}
	return 0;
}

lowbit 操作

• 返回x的最后一位1，并且是一个二进制数
  • 如果$(x)_2 = 1010$，那么lowbit(x) = 10
  • 如果$(x)_2 = 101000$，那么lowbit(x) = 1000

实现原理

• x & -x
• 在c++中，-x的二进制表示与~x + 1的二进制表示是相同的，其中~x是x的补码

           x = 1010 ... 100 ... 0
          ~x = 0101 ... 011 ... 1
      ~x + 1 = 0101 ... 100 ... 0
x & (~x + 1) = 0000 ... 100 ... 0

• 可以看到，x & (~x + 1)的结果返回的就是最后一位1的二进制数

二进制中1的个数

解题思路

• 通过多次lowbit操作，找到数字二进制中1的个数。每次进行玩lowbit操作，都会将最后1位1减去，实现数字的更新

实现代码

#include <bits/stdc++.h>

using namespace std;

int lowbit(int x){
    return x & -x;
}

int main(){
    int n;
    cin >> n;

    while(n --){
        int x;
        cin >> x;

        int cnt = 0;
        while(x){
            x -= lowbit(x);
            cnt ++;
        }


        cout << cnt << " ";
    }

    return 0;
}