位运算--二进制中1的个数(含常见的二进制运算操作)

2024-01-07 21:09:00


原题链接:

二进制中1的个数

给定一个长度为 n
的数列,请你求出数列中每个数的二进制表示中 1
的个数。

输入格式
第一行包含整数 n

第二行包含 n
个整数,表示整个数列。

输出格式
共一行,包含 n
个整数,其中的第 i
个数表示数列中的第 i
个数的二进制表示中 1
的个数。

数据范围
1≤n≤100000
,
0≤数列中元素的值≤109
输入样例:
5
1 2 3 4 5
输出样例:
1 1 2 1 2

思路:
二进制题目中最常见的操作

操作 1 查看第k位的数字是否为1

查看数字当前第k位的数字是几?
在这里插入图片描述
以图上的数字排序为例子
我们想查看一个数字第几位的数字 就可以用下面的方式

num>>k & 1

操作2 lowbit操作

树状数组的基本操作
功能 是返回 当前数字的最后一位1
比如数字 x=110100 返回的就是第2位 1
lowbit(x)=100

lowbit 具体实现

源码: return (x & -x)
-x =~x +1
x &(~x +1)

解题代码:

个人思路

#include<iostream>
using namespace std;


int main()
{
    int n ;
    cin>>n;
    for(int i= 0; i < n;i++)
    {
        int tmp = 0 ;
        cin >> tmp;
        int num=0;
        while(tmp != 0)
        {
            if(tmp & 1)
                num++;
            tmp>>=1;
        }
        cout<<num<<" ";
    }
    return 0;         
}

y总思路

#include <iostream>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int x, s = 0;
        scanf("%d", &x);
		//lowbit 每次减去最后一位数字 来计算 它有多少个1 
        for (int i = x; i; i -= i & -i) s ++ ;

        printf("%d ", s);
    }

    return 0;
}

文章来源:https://blog.csdn.net/weixin_52243202/article/details/135443181
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。