C++如何计算二进制数中1的个数

2024-10-04 09:47:54

计算二进制数中1的个数

见到计算二进制数中的1的个数的比较精巧的做法，做个笔记(其实是之前被问到了，所以就查了下…

int CountOnes(int n) {
    int count = 0;
    while(n) {
        ++count;
        n = n & (n - 1);
    }
    return count;
}

刚看见时不太明白思路，然后自己拿笔随便划拉了下，算是搞明白了思路，简单总结一下。这个方法的主要思想就是找到当前数字中最靠右的1。

思路简单总结

n - 1(n不为0时)会使得n的最右侧第一个1以及该位的右侧的所有位取反，此时进行与操作，就会将该位置为0。

其实看上面那句话就行了，思路很简单，完全理解不了思路才需要看下面的:

大致上可以分成两种情况，当然事实上可以看成是同一种情况

第一种：n的最右边是1。如果n最右边是1的话，n-1就只有最右边那一位变为0，此时n & (n - 1)就相当于是把n中右边第一位的1拿掉，比如n为0111时，n - 1就是0110，两者相与，结果就是n - 1，此时n - 1中1的个数比n中少1，且最右侧的位为0，已经转变为第二种情况。
第二种：n的最右边是0。此时计算n - 1时，需要向上借位，一直借到n的最右侧的第一个1。例如n为1000时，n - 1就是0111，此时可以发现，n的第一个1的右侧的所有位都变成了1，并且原来是1的位变成了0。注意初始时n的第一个1的右侧的所有位都是0，计算n - 1后这些位都变成了1，此时再做与操作，这些位都会变成0。所以效果就是"n的右侧第一个为1的位被置为0"。

最后当n中不存在为1的位时，n的值等于0，while循环退出。这种做法相对于直接从右往左靠移位和与的做法来说更好一些，不需要遍历所有的位，也少了不少的判断，运行时间与n中1的个数相关。

C++ 1的个数简单解法

问题描述

输入正整数n，判断从1到n之中，数字1一共要出现几次。例如1123这个数，则出现了两次1。

例如15，那么从1到15之中，一共出现了8个1。

输入格式

一个正整数n

输出格式

一个整数，表示1出现的资料

样例输入

15

样例输出

8

数据规模和约定

n不超过30000

#include <iostream>
using namespace std;

int main(){
    int n;
    int cnt = 0; //用来记录1的个数
    cin >> n;
    for(int i=1;i<=n;i++){
    int j = i; //j用来存放每次循环后更新过的i值
    while(j){ //循环依次对j的个位十位百位。。。位进行对一取余
        if(j%10==1){ 
            cnt++;    
        }
        j /= 10;
     }
    }
    cout << cnt << endl;
    return 0;
}

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。

C++实现LeetCode(191.位1的个数)

[LeetCode] 191.Number of 1 Bits 位1的个数 Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). For example, the 32-bit integer '11' has binary representation 00000000000000000000000
详解C++中二进制求补运算符与下标运算符的用法

二进制求补运算符:~ 语法 ~ cast-expression 备注二进制反码运算符 (~)(有时称为"按位反码"运算符)将生成其操作数的按位二进制反码.即,操作数中为 1 的每个位在结果中为 0.相反,操作数中为 0 的每个位在结果中为 1.二进制反码运算符的操作数必须为整型. ~ 的运算符关键字 compl 运算符是 ~ 的文本等效项.访问程序中的 compl 运算符有两种方式:包括头文件 iso646.h,或使用 /Za 进行编译. // expre_One_Compleme
C++求1到n中1出现的次数以及数的二进制表示中1的个数

在从 1 到 n 的正数中 1 出现的次数题目: 输入一个整数 n,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数. 例如输入 12,从 1 到 12 这些整数中包含 1 的数字有 1, 10, 1 1 和 12, 1 一共出现了 5 次代码实现(GCC编译通过): #include "stdio.h" #include "stdlib.h" int count1(int n); int count2(int n); int main(void
C++如何计算二进制数中1的个数

目录计算二进制数中1的个数思路简单总结 C++ 1的个数简单解法问题描述输入格式输出格式计算二进制数中1的个数见到计算二进制数中的1的个数的比较精巧的做法,做个笔记(其实是之前被问到了,所以就查了下… int CountOnes(int n) { int count = 0; while(n) { ++count; n = n & (n - 1); } return count; } 刚看见时不太明白思路,然后自己拿笔
Java数据结构及算法实例：快速计算二进制数中1的个数(Fast Bit Counting)

/** * 快速计算二进制数中1的个数(Fast Bit Counting) * 该算法的思想如下: * 每次将该数与该数减一后的数值相与,从而将最右边的一位1消掉 * 直到该数为0 * 中间循环的次数即为其中1的个数 * 例如给定"10100",减一后为"10011",相与为"10000",这样就消掉最右边的1 * Sparse Ones and Dense Ones were first described by Peter Wegner i
JavaScript中使用参数个数实现重载功能

利用参数的个数实现重载,马上想到的方法就是 function overload(){ switch(arguments.length){ case 0: console.log("一个朋友都没有"); break; case 1: console.log("有一个朋友"); break; case 2: console.log("有两个朋友"); break; case 3: console.log("有三个朋友"); bre
asp.net中C#获取字符串中汉字的个数的具体实现方法

符串可以包括数字,字母,汉字或者其他的字符.使用Char类型的IsDigit静态方法可以判断字符串中的字符是否为数字,使用Char类型中的IsLetter静态方法可以判断字符串中是否为字母.我们来实现一种方法来实现判断字符串中是否为汉字,通过此方法可以计算字符串中汉字的个数,运行效果如图: 首先根据效果图设置好Form的界面和内容,Box1.Text为输入的字符串,我们对该字符串的处理,来计算汉字的个数,双击Buton控件,编辑其单击事件代码. 我们看下汉字的Unicode范围,普遍给出了0x4
java中实现递归计算二进制表示中1的个数

借助Java语言,运用递归算法计算整数N的二进制表示中1的个数 /*use the recursive algorithme to calculate * the number of "1" in the binary expression * of an Integer N. * Note:if N is an odd, then * the result is the result of N/2 plus 1. * And the program use the bit opera
C语言回溯法实现组合数从N个数中选择M个数

前言在平时的算法的题目中,时常会遇到组合数相关的问题,暴力枚举.在N个数中挑选M个数出来.利用for循环也可以处理,但是可拓展性不强,于是写这个模板供以后参考. 两个函数和全局变量可以直接用. 代码: #include<iostream> #include<cstdio> #define N 10 //被选择的数目 #define M 5 //要选出来的数目 using namespace std; int vis[N+1]; //标志, int ans=0;
python从list列表中选出一个数和其对应的坐标方法

例1:给一个列表如下,里面每个元素对应的是x和y的值 a = [[5,2],[6,3],[8,8],[1,3]] 现在要挑出y的值为3对应的x的值,即6和1 import numpy as np a = [[5,2],[6,3],[8,8],[1,3]] #c=np.mat(a),因为只有矩阵(也可以用array)才能用a[0,0]这样的调用 #表示第一个数的用法而list没有,故在最后append需要用到 #注意:array也没有index这样的用法(只有list有,此题a已经是list),
golang 中获取字符串个数的方法

在 golang 中不能直接用 len 函数来统计字符串长度,查看了下源码发现字符串是以 UTF-8 为格式存储的,说明 len 函数是取得包含 byte 的个数 // string is the set of all strings of 8-bit bytes, conventionally but not // necessarily representing UTF-8-encoded text. A string may be empty, but // not nil. Values
C语言统计一篇英文短文中单词的个数实例代码

具体代码如下所述: #include<stdio.h> #define N 1000 void main(){ char en[N][81]; int i,j,num=0,n,state; //num 用来统计单词的个数 //state 用来记录程序当前是否处于一个单词之中,初值为0,表示不在单词中,值为1,表示正处于在一个单词中 printf("Please input the number of lines for English passage:"); scanf(&