首页 > 试题广场 >

bit count

[编程题]bit count

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

输入一个long类型的数值, 求该数值的二进制表示中的1的个数 .

输入描述:

long 类型的数值

输出描述:

该数值二进制表示中1的个数

示例1

输入

输出

说明

3的二进制表示: 11, 所以1个数为2

示例2

输入

输出

说明

65的二进制为:1000001，所以１的个数为：２

算法知识视频讲解

C/C++

WindedMan

#include<bits/stdc++.h>
using namespace std;
int main(){
    long num;
    cin>>num;
    int count=0;
    long dev=1;
    int len=64;
    while(len--){
        if(num&dev)count++;
        dev<<=1;
    }
    cout<<count<<endl;
    return 0;
}

发表于 2020-04-28 23:22:41 回复(0)

更多回答

Hachiko123456

import java.util.Scanner;
 
/**
 * @author YHX
 * @date 2019/9/4 11:14
 * description
 */
public class Main {
   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        int cnt = 0;
        boolean flag = true;
        while (n != 0) {
           cnt++;
           n=n&(n-1);
        }
        System.out.println(cnt);
        in.close();
    }
}

如果n不为0，那么n肯定有一个为1的二进制位，当n-1的时候，就是把n最右边的1变成0，然后这个1最右边的0变成1，例如10（1010）-1就是1001，最右边的1变成0，最右边的0变成1。当把它们进行与操作的时候1010&1001=1000，就相当于把剩下的1保留了下来，然后再进行上述重复操作直到n等于0就能统计出n的1的个数了。

发表于 2019-09-05 10:05:21 回复(0)

cryinguo

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            Long n = sc.nextLong();
            System.out.println(Long.bitCount(n));  
        }
        sc.close();
    }
}

发表于 2019-09-03 22:10:41 回复(0)

你瞅啥瞅

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int t = 0;
        if(n>0){
            while(n>=2){
                if(n%2==1){
                    t++;
                }
                n=n/2;
            }
            System.out.print(t+1);
        }else if(n==0){
            System.out.println(0);
        }else{
            n=-n;
            String s = "";
            //转二进制
            while(n>=2){
                s=s+String.valueOf(n%2);
                n=n/2;
            }
            s=s+String.valueOf(n%2);
            int len = s.length();
            int []a = new int [len];
            //取反
            for(int i=0;i<s.length();i++){
                if(s.charAt(i)=='1'){
                    a[i]=0;
                }else{
                    a[i]=1;
                }
            }
            //取补
            a[0]=a[0]+1;
            for(int i=0;i<len-1;i++){
                if(a[i]==2){
                    a[i]=0;
                    a[i+1]=a[i+1]+1;
                }
            }
             
            for(int i=0;i<len;i++){
                if(a[i]==1){
                    t++;
                }
            }
             
 
            System.out.println(t+64-len);
             
   }
            
         
    }
}

发表于 2019-09-03 20:05:41 回复(1)

京东内推君

三种方法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long inputValue = sc.nextLong();
        int mask = 1;
        int count = 0;
        for (int i = 0; i < 64; i++) {
            if ((inputValue & mask) != 0) {
                count++;
            }
            mask <<= 1;
        }
        System.out.println(count);
    }

    // 方法二：
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long inputValue = sc.nextLong();
        int res = 0;
        // 注意 & 只能 Int 或者 long，double 不能用
        while (inputValue != 0) {
            inputValue = inputValue & (inputValue - 1);
            res++;
        }
        System.out.println(res);

    }

    // 方法三：
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long inputValue = sc.nextLong();
        // 方法二：调用 API
        int resNum = 0;
        // 只有 long 有这个方法
        String resString = Long.toBinaryString(inputValue);
        for (int i = 0; i < resString.length(); i++) {
            if (resString.charAt(i) == '1') {
                resNum++;
            }
        }
        System.out.println(resNum);
    }
}

发表于 2020-06-22 23:14:49 回复(0)

Java

何止hz

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        int ans = 0;
        while (n != 0){
            ans += (n & 1);
            n >>>= 1;
        }
        System.out.println(ans);
    }
}

发表于 2020-05-13 10:34:19 回复(0)

ceeeeeeeeeeeb

每次进行一次无符号右移一位，检查最右边是否是1

import java.util.Scanner;

public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
int result = 0;
while(n!=0){
result += n &1;
n >>>= 1;
}
System.out.println(result);
}
}

发表于 2019-08-08 21:20:07 回复(0)

C/C++

哟，我喜欢

#include<iostream>
using namespace std;
int main(){
    unsigned long int a;
    cin >> a;
    int res=0;
    while(a>0){
        res++;
        a &= a-1;
    }
    cout << res << endl;
    return 0;
}

发表于 2019-05-22 11:14:55 回复(0)

大咸鱼9527

golang：

package main

import (
    "fmt"
)

func main() {
    var num int64
    fmt.Scanln(&num)
    ans := 0
    for ; num != 0; {
        ans++
        num = num & (num-1)
    }
    fmt.Println(ans)
}

发表于 2019-05-19 17:21:23 回复(0)

C/C++

绅蓝

#include "bits/stdc++.h"
using namespace std;
int main()
{
long long n;
while(cin>>n)
{
int count=0;
while(n)
{
count++;
n=(n-1)&n;
}
cout<<count<<endl;
}
}

编辑于 2019-05-14 10:47:18 回复(3)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long n;
    cin>>n;
    int res=0;
    while(n)
    {
        n=n&(n-1);
        res++;
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-08-17 23:16:31 回复(2)

大虾s

import java.util.Scanner;
public clas***ain{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        String str = Long.toBinaryString(a);
        int count = 0;
        for(char ch:str.toCharArray()){
            if(ch=='1') count++;
        }
        System.out.println(count);
    }
}

发表于 2019-05-19 08:26:32 回复(1)

C/C++

infiniteft

四种方法:

方法一：

思路: 该方法的思路来源：对于任意N=2^n(其中n >= 0)，都有N & (N - 1) = 0（N的二进制表示中只有一位为1，其他位都为0），因为N - 1之后，N原来为1的那一位变为0，低于原来为1那一位的所有位都变为0，两者相与便为0，例如128=10000000b，128 - 1= 127 = 01111111b，128 & 127 = 0。

对于任意数M的BCD编码(包括负数)都可以表示为多个2的不同次幂的数之和，例如：10 = 2^3 + 2^1, 9 = 2^3 + 2^0，求取M中1的个数，就相当于求M由多少个2的不同次幂的数相加得到，所以只需要每次M & M - 1便从M减去一个2的次幂数，直到所有2的次幂数都减掉，M便等于0。对于M为负数时，M的二进制编码看成BCD编码，也满足此性质，所以不需要对M为负数情况进行特殊处理。

long n;
cin >> n;
int cnt = 0;
while(n)
{
    n = n & n - 1;
    cnt++;
}
cout << cnt << endl;

方法二：

思路：从左到右依次对n的每一位进行检查，如果位为1，cnt加1，mask 每次左移一位，超过类型长度之后，会自动溢出变为0，即可退出循环条件。这个方法不需要考虑n为负数的情况，通用处理。

long n;
cin >> n;
int cnt = 0;
long mask = 1;
while(mask)
{
    if(n & mask) cnt++;
    mask <<= 1;
}
cout << cnt << endl;

方法三：

思路：每次检测n的最低位是否为1，然后n右移一位。但该方法需要对n为负数的情况进行特殊处理，因为n为负数的时候，右移的时候是进行算术右移，最高位自动补1，导致n不能为0。那怎样处理呢？

如果n为负数，去掉最高位（符号位)，让n变为正数，并保证余下的位不变：用n减去最大的负数，即可保证符号位变为0，其他位不变。n为变为正数之后，就可以对n按bit进行右移了，统计其中1的个数。

if(n < 0)
{
        //需要注意，这里的0x01需要强制转为long,默认为int,导致结果不正确
    n = n - ((long)0x01 << (sizeof(long) * 8 - 1));
        cnt++;
}
while(n != 0)
{
    if(n & 0x01) cnt++;
    n = n >> 1;
}
cout << cnt << endl;

方法四：

这个思路方法二类似，只不过每次对需要左移位数加1，从左到右依次检测每一位。

long shift = 0;
while(shift < (sizeof(long) * 8))
{
        // 同样需要注意，0x01需要强制转为long类型，
    if(n & ((long)0x01 << shift)) cnt++;
    shift++;
}
cout << cnt << endl;

编辑于 2020-04-17 23:59:18 回复(0)

C/C++

nbgao

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

int main(){
    long n;
    int cnt = 0;
    cin>>n;
    while(n){
        n &= (n-1);
        cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

发表于 2019-10-11 23:28:03 回复(0)

C/C++

昔遥暮云

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,sum=0,a=1;
    cin>>n;
    while(a){
        if(n&a)
            sum++;
        a<<=1;
    }
    cout<<sum;
    return 0;
}

发表于 2019-10-19 17:16:31 回复(1)

bug_making()

位运算

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long n;
    cin >> n;
	int num = 0;
    while (n) {
		if (n & 1) num++;       // 统计最后一位是否为 1
		n >>= 1;
	}
	cout << num << endl;
    return 0;
}

发表于 2022-04-28 17:34:15 回复(0)

牛客136657590号

逻辑很简答，每次判断低位是否为1，然后整体右移一位。需要注意的是，java中逻辑右移需要>>>=1，不然负数高位会有问题。

import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long num = sc.nextLong();
        int count = 0;
        while(num != 0){
            count += num & 1;
            num >>>= 1;
        }
        System.out.println(count);
    }
}

发表于 2022-03-24 11:44:36 回复(0)

C/C++

codewind

#include<cstdio>
#define lowbit(x) (x&(-x))

int main(void) {
    long long x ,res=0;
    scanf("%lld", &x);
    while(x) x-=lowbit(x),res++;
    printf("%lld\n",res);
    return 0;
}

发表于 2021-04-10 19:10:01 回复(0)

天下无题

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        long num = Long.parseLong(sc.nextLine());
 
        int count = 0;
 
        while(num != 0){
            count += num & 1;
            num >>>= 1;
        }
 
        System.out.println(count);
 
    }
}

发表于 2021-04-01 15:57:18 回复(0)

派派派big星

int res = 0;
        while (n != 0) {
            res += n & 1;
            n >>>=1;//无符号右移
        }
        return res;

使用无符号右移进行操作

发表于 2021-03-03 21:40:50 回复(0)

我是阿凤啊

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

int main()
{
long a;
cin >> a;
int ret = bitset<64>(a).count();
cout << ret << endl;
system("pause");
return 0;
}

发表于 2020-08-11 12:03:00 回复(0)

提交观点

问题信息

C++工程师 iOS工程师进制转化安卓工程师位运算运维工程师前端工程师携程 PHP工程师 2019 数学 Java工程师

上传者：小小

难度：

31条回答 66收藏 7741浏览

通过挑战的用户

查看代码

在线蹲牛友的华...

2023-08-06 21:06:23
Sorryma...

2023-03-14 16:47:06
ringoringo

2023-03-07 17:02:52
joae

2023-03-07 11:51:24
梦回昨天

2023-03-06 21:21:47

bit count

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题