首页 > 试题广场 >

二进制计数-研发

[编程题]二进制计数-研发

热度指数：4643 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小A刚学了二进制，他十分激动。为了确定他的确掌握了二进制，你给他出了这样一道题目：给定N个非负整数，将这N个数字按照二进制下1的个数分类，二进制下1的个数相同的数字属于同一类。求最后一共有几类数字？

输入描述:

输入的第一行是一个正整数T（0<T<=10），表示样例个数。对于每一个样例，第一行是一个正整数N（0<N<=100），表示有多少个数字。接下来一行是N个由空格分隔的非负整数，大小不超过2^31 – 1。，

输出描述:

对于每一组样例，输出一个正整数，表示输入的数字一共有几类。

示例1

输入

1
5
8 3 5 7 2

输出

算法知识视频讲解

C/C++

天命剑主

#include <iostream>
#include <string.h>
using namespace std;

int getcount(int num)
{
	int count = 0;
	int i = 0;
	while (num)
	{
          num = num&(num - 1);
          count++;
 	}
	return count;
}

void one(){
    int n;
    cin >> n;
    int counts[32];
    memset(counts,0,32*sizeof(int));
    for(int i=0;i<n;i++){
        int num;
        cin >> num;
        int count = getcount(num);
        counts[count]++;
    }
    int sum = 0;
    for(int i=0;i<32;i++){
        if(counts[i]>0){
            sum++;
        }
    }
    cout << sum << endl;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        one();
    }
}

编辑于 2019-12-17 16:45:37 回复(1)

(●--●)

思路：位运算 + 去重，速度应该是很快的。n = n & (n - 1) 一次可以去掉n的二进制里的一个1。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main(){
    int T;
    cin>>T;
    int n;
    int num;
    while(T--){
        cin>>n;
        unordered_map<int, int> mp;
        for(int i = 0; i < n; ++i){
            cin>>num;
            int count = 0;
            while(num){
                num = num & (num - 1);
                count++;
            }
            mp[count]++;
        }
        cout<<mp.size()<<endl;
    }
    return 0;
}

发表于 2021-03-29 20:36:08 回复(0)

Python

maoxiaomao

T=int(input())
for i in range(T):       #T组数据
    N=int(input())       #这组数据N个数
    A=list(map(int,input().strip().split()))
    s=set()
    for num in A:
        t=bin(num).replace('0b', '')
        tmp=t.count('1')
        s.add(tmp)
    print(len(s))

发表于 2021-08-05 20:43:30 回复(0)

ASHBRINGER201806271637325

#include <iostream>
(720)#include <map>
using namespace std;
 
int main()
{
    int T,N;
    cin>>T;
    while(T--)
    {
        cin>>N;
        int temp;
        map<int,int> hash;
        for(int i=0; i!=N; ++i)
        {
            cin>>temp;
            int onecnt=0;
            while(temp)
            {
                onecnt+=(temp%2?1:0);
                temp/=2;
            }
            ++hash[onecnt];
        }
        cout<<hash.size()<<endl;
    }
    return 0;
}

发表于 2020-03-31 22:31:16 回复(0)

Frost-Nova

运用__builtin_popcount()函数直接得出一个整数的二进制位上1的数量。

#include<bits/stdc++.h>

using namespace std;

int main()

{

int _, n, t;

cin >> _;

while(_ --)

{

map<int,int> mp;

cin >> n;

while(n --)cin >> t,mp[__builtin_popcount(t)] ++;

cout << mp.size() << endl;

}

发表于 2020-07-17 16:59:20 回复(0)

daluhaiyang

求每个整数二进制中1的个数，再把个数插入到set中，最后统计set大小，就是类别个数。

#include<iostream>
(720)#include<set>
using namespace std;
int BinaryCount(int n){
    int count=0;
    while(n>0){
        if(n%2==1)
            ++count;
        n=n/2;
    }
    return count;
}
int main(){
    int T;
    while(cin>>T){
        while(T>0){
            --T;
            int N;
            cin>>N;
            set<int> res;
            while(N>0){
                --N;
                int n;
                cin>>n;
                res.insert(BinaryCount(n));
            }
            cout<<res.size()<<endl;
        }
    }
}

编辑于 2020-04-09 14:15:53 回复(0)

阿金要努力

unordered_set去重，统计其大小

#include<iostream>
#include<unordered_set>
using namespace std;
int BinaryCount(int n)
{
    int count=0;
    while(n)
    {
        n&=n-1;
        count++;
    }
    return count;
}
int main()
{
    int T=0;
    cin>>T;
    while(T--)
    {
        unordered_set<int> result;
        int N=0;
        cin>>N;
        while(N--)
        {
            int n=0;
            cin>>n;
            result.insert(BinaryCount(n));
        }
        cout<<result.size()<<endl;
    }
    return 0;
}

发表于 2023-02-08 16:01:40 回复(0)

C/C++

蓬岐

算法入门 c++解题思路：位运算+排序去重

运行时间4ms

占用内存408KB

用位运算+哈希表计数更简洁

#include<iostream>
#include<vector>
#include<string>
using namespace std;
//快速排序算法
class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    void randomized_quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            randomized_quicksort(nums, l, pos - 1);
            randomized_quicksort(nums, pos + 1, r);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};
//解题思路：位运算+排序去重
int main() {
    int T;
    while (cin >> T) {
        while(T--){
            int N;
            cin >> N;
            if(N==0){
                return 0;
            }
            vector<int> vec(N);
            for (int i = 0; i < N; i++) cin >> vec[i];

            // 处理逻辑 
            vector<int> pre_ans(N);
            for(int j=0; j<N; j++){
                for (int i=0; i<32; i++){

                    pre_ans[j]+=(vec[j] >> i) & 1;  
                }
            }

                        //排序
            Solution a;
            a.sortArray(pre_ans);


                        //去重
            int fast = 1, slow = 1;
            while (fast < N) {
                if (pre_ans[fast] != pre_ans[slow - 1]) {
                    pre_ans[slow] = pre_ans[fast];
                    ++slow;
                }
                ++fast;
            }
            cout << slow << endl;
        }
        
    }
    return 0;
}

编辑于 2022-08-14 09:44:44 回复(0)

福克斯牌饼干

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {            
            int itemNum = 0;
            itemNum = int.Parse(Console.ReadLine());

            int[] Num = new int[itemNum];

            while (itemNum != 0)
            {
                int[] NumberClass = new int[32];
                int Class_num = 0;

                Num[itemNum-1] = int.Parse(Console.ReadLine());
                String[] NumString = Console.ReadLine().Split(' ');

                for (int i = 0; i < Num[itemNum - 1]; i++)
                {
                    //判断二进制
                    int number = int.Parse(NumString[i]);
                    int count = 0;
                    while (number != 0)
                    {
                        number = number & (number - 1);
                        count++;
                    }
                    NumberClass[count] += 1;
                }
                for (int i = 0; i < NumberClass.Length; i++)
                {
                    if (NumberClass[i] > 0)
                        Class_num += 1;
                }
                Console.WriteLine(Class_num);

                itemNum -= 1;
            }
        }
    }
}

发表于 2022-03-02 17:47:13 回复(0)

文和906

核心思想是通过模2运算来判断最末位是否为1，然后向右移位运算，直到移位为0。

#include <iostream>
#include <set>
using namespace std;
 
int main(){
    int bn = 0;
    cin>>bn;
    for(int k = 0;k<bn;k++){
        int num = 0;
        cin>>num;
        int arr[num];
        set<int> st;
        for(int i = 0;i < num;i++){
            cin>>arr[i];
            int count = 0;
            int temp = arr[i];
            while(temp>0){
                if(temp%2){
                    count++;
                }
                temp = temp>>1;
            }
            st.insert(count);
        }
        cout<<st.size()<<endl;
    }
     
    return 0;
}

发表于 2021-09-23 15:19:15 回复(0)

BIGSDD

我编程能力很差，只能写个残次品😫 #include <stdio.h>
int main()
{
    int a[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
    int i,n,j;
    int x=0,sum=0;
    printf("请输入数字的数量:");
    scanf("%d",&n);
    int b[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
    for(i=0;i<n;i++)
    {
        printf("请输入第%d个数:",i+1);
        scanf("%d",&b[i]);
    }
    for(i=0;i<n;i++)
    {
        x=0;
        while(b[i]!=0)
        {
            if(b[i]%2==1)
            {
                x++;
            }
            b[i]=b[i]/2;
        }
        for(j=0;j<=i;)
        {
            if(a[j]==x)
            break;
            j++;
        }
        if(j>i)
        {
            sum++;
            a[j-1]=x;
        }
    }
    printf("一共有%d类!",sum);
}

发表于 2021-09-17 16:45:32 回复(0)

VagrantSven

#include <iostream>
#include <bitset>
#include <unordered_map>

using namespace std;

int main() {
    int i;
    cin >> i;
    while (i--) {
        int j;
        cin >> j;
        unordered_map<int, int> times;
        while (j--) {
            unsigned x;
            cin >> x;
            bitset<32> bs(x);
            times[bs.count()]++;
        }
        cout << times.size() << endl;
        
    }
    return 0;
}

发表于 2021-09-02 10:45:45 回复(0)

山海意明

#include<iostream>
using namespace std;
  
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int map[32] = { 0 }; // 1的个数有可能有0-31
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int num;
            cin >> num;
            int count = 0;
            while (num) {
                if (num & 1) count++; // 探测最后一位是否为1，是则加一
                num >>= 1; // 右移一位
            }
            map[count]++;
        }
        int size = 0;
        for (auto& it : map) {
            if (it > 0) {
                size++;
            }
        }
        cout << size << endl;
    }
}

发表于 2021-08-06 15:42:54 回复(0)

Java

风之恋_7

import java.util.*;

public class Main{
public static void main(String[]args){
Scanner s = new Scanner(System.in);
int sample = s.nextInt();
while (sample > 0) {
sample--;
int num = s.nextInt();
Set<Integer> set = new HashSet<>();
while (num > 0) {
num--;
set.add(intToBinary(s.nextInt()));
}
System.out.println(set.size());
}
}

public static int intToBinary (int num) {
int count = 0;
while (num > 0) {
if (num % 2 == 1) {
count++;
}
num /= 2;
}
return count;
}

}

//借鉴了以下楼上大佬的思路，这道题因为只要求1的种类个数，所以用set数据结构，因为set是无序不重复的，这样可以直接用set的长度计数。

发表于 2021-04-17 14:04:35 回复(0)

牛客734064397号

import java.util.*;
public class Main{
public static void main(String args[]){
Scanner scanner = new Scanner(System.in);
ArrayList<Integer> answer = new ArrayList<Integer>();
int zeroL = scanner.nextInt();
while(scanner.hasNextInt()){
int firstL = scanner.nextInt();
ArrayList<Integer> num = new ArrayList<>();
Set<Integer> result = new HashSet<Integer>();
for(int i = 0;i<firstL;i++){
    num.add(scanner.nextInt());
}
for(int i=0;i<firstL;i++){
    int tem = num.get(i);
    int sum = 0;
    int j = 2;
    while(tem!=0){
        if(tem%j>0){
            sum+=1;
        }
        tem-=tem%j;
        j*=2;
    }
    result.add(sum);
}
answer.add(result.size());}
int s = answer.size();
for(int i = 0;i<s;i++){
    System.out.println(answer.get(i));
}
}}

发表于 2021-03-30 20:16:34 回复(0)

cloudKing

#include<iostream>
#include<set>
using namespace std;

int countBin(int num)
{
int count = 0;
while(num)
{
num = num & (num-1);
count++;

}
return count;
}
int main()
{
int exmple_group;
cin>>exmple_group;
while(exmple_group)
{
int exmple_num;
cin>>exmple_num;
set<int> kind;
while(exmple_num)
{

int num;
cin>>num;
kind.insert(countBin(num));
exmple_num--;
}
cout<<kind.size()<<endl;
exmple_group--;
}
return 0;
}

发表于 2021-03-30 10:10:31 回复(0)

牛客802680790号

求每个整数二进制中1的个数，再把个数插入到字典或集合中，最后统计字典或集合大小。

T = int(input())
for _ in range(T):
    N = int(input())
    alist = input().split()
    myans = dict()
    for j in range(N):
        in_num = int(alist[j])
        temp = bin(in_num).count('1')
        myans[temp] = 1
    print(len(myans))

发表于 2021-03-12 18:23:16 回复(0)

offer保命

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>

using namespace std;

int main()
{
    int T=0,N=0,num=0;
    cin>>T;
    set<int> mySet;
    
    while(T)
    {
        cin>>N;
        while(N)
        {
            cin>>num;
            int count=0;
            while(num)
            {
                if(num%2)
                    count++;
                num/=2;
            }
            mySet.insert(count);
            N--;
        }
        int sum =mySet.size();
        cout<<sum<<endl;
        mySet.clear();
        T--;
    }
    return 0;
}

发表于 2021-02-19 10:26:51 回复(0)

露西恩缇努维尔

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

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int N;
        cin>>N;
        int num;
        set<int> S;
        for(int i=0;i<N;i++)
        {
            cin>>num;
            bitset<32> bs(num);
            S.insert(bs.count());
        }
        cout<<S.size()<<endl;
    }
    return 0;
}

发表于 2020-09-27 16:28:41 回复(0)

讨厌动态规划

只过了%10为啥？呜呜，输出一样的为啥说我不对

int main()

{
    int T;
    cin>>T;
    if(T<0||T>10){
        return 0;
    }
    int N;
    int a[100];
    set<int> s;
    int times=0;
    for(int i=0; i<T; i++){
        cin>>N;
        if(N<=0||N>100){
            return 0;
        }
        for(int j=0; j<N; j++){
            cin>>a[j];
        }
        for(int k=0; k<N; k++){
            while (a[k]/2!=0) {
                if(a[k]%2==1){
                    times++;
                }
                a[k]=a[k]/2;
            }
            if(a[k]%2==1){
                times++;
            }
            s.insert(times);
            times=0;
        }
        if(i!=T-1){
            cout<<s.size()<<" ";
            s.clear();
        }else{
            cout<<s.size()<<endl;
            s.clear();
        }
    }
    return 0;
}