精华内容
下载资源
问答
  • 0871-统计整数的数字和函数 时间限制: 1000 毫秒 内存限制: 32768 K字节 总提次数: 829 次 版权文档请勿用做商业用途 成功提交次数: 607 次 版权文档请勿用做商业用途 判题规则: 严格比较 问题描述 统计整数n的保...
  • C语言 统计整数二进制表示中1的个数 这是一个很有意思的问题,也是在面试中最容易被问到的问题之一。这个问题有个正式的名字叫Hamming_weight,而且wikipedia上也提供了很好的位运算解决的方法,这个下面也...

    C语言 统计整数二进制表示中1的个数

    这是一个很有意思的问题,也是在面试中最容易被问到的问题之一。这个问题有个正式的名字叫Hamming_weight,而且wikipedia上也提供了很好的位运算解决的方法,这个下面也会提到。

    解决这个问题的第一想法是一位一位的观察,判断是否为1,是则计数器加一,否则跳到下一位,于是很容易有这样的程序。

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int test(int n)
    {
        int count=0;
        while(n != 0){
            if(n%2 ==1)
                count++;
            n /= 2;
        }
        return count;
    }

    或者和其等价的位运算版本:

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int test(int n)
    {
        int count=0;
        while(n != 0){
            count += n&1;
            n >>= 1;
        }
        return count;
    }

    这样的方法复杂度为二进制的位数,即,于是可是想一下,有没有只与二进制中1的位数相关的算法呢。

    可以考虑每次找到从最低位开始遇到的第一个1,计数,再把它清零,清零的位运算操作是与一个零,但是在有1的这一位与零的操作要同时不影响未统计过的位数和已经统计过的位数,于是可以有这样一个操作 n&(n-1) ,这个操作对比当前操作位高的位没有影响,对低位则完全清零。拿6(110)来做例子,第一次 110&101=100,这次操作成功的把从低位起第一个1消掉了,同时计数器加1,第二次100&011=000,同理又统计了高位的一个1,此时n已变为0,不需要再继续了,于是110中有2个1。

    代码如下:

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int test(int n)
    {
        int count=0;
        while(n != 0){
            n &= n-1;
            count ++;
        }
        return count;
    }

    这几个方法虽然也用到了位运算,但是并没有体现其神奇之处,下面这个版本则彰显位运算的强大能力,若不告诉这个函数的功能,一般一眼看上去是想不到这是做什么的,这也是wikipedia上给出的计算hamming_weight方法。

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int test(int n)
    {
        n = (n&0x55555555) + ((n>>1)&0x55555555);
        n = (n&0x33333333) + ((n>>2)&0x33333333);
        n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
        n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
        n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);
      
        return n;
    }

    没有循环,5个位运算语句,一次搞定。

    比如这个例子,143的二进制表示是10001111,这里只有8位,高位的0怎么进行与的位运算也是0,所以只考虑低位的运算,按照这个算法走一次

    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |   <---143
    +---+---+---+---+---+---+---+---+
    |  0 1  |  0 0  |  1 0  |  1 0  |   <---第一次运算后
    +-------+-------+-------+-------+
    |    0 0 0 1    |    0 1 0 0    |   <---第二次运算后
    +---------------+---------------+
    |        0 0 0 0 0 1 0 1        |   <---第三次运算后,得数为5
    +-------------------------------+

    这里运用了分治的思想,先计算每对相邻的2位中有几个1,再计算每相邻的4位中有几个1,下来8位,16位,32位,因为2^5=32,所以对于32位的机器,5条位运算语句就够了。

    像这里第二行第一个格子中,01就表示前两位有1个1,00表示下来的两位中没有1,其实同理。再下来01+00=0001表示前四位中有1个1,同样的10+10=0100表示低四位中有4个1,最后一步0001+0100=00000101表示整个8位中有5个1。

    展开全文
  • C语言计算变量二进制中1的个数 方法一 #include <stdio.h> unsigned char func(unsigned char para) { int i = 0,num = 0; for(;i < 8;i++) { if(para & 0x80) num++; para <<= 1; }...

    C语言计算变量二进制中1的个数

    方法一

    #include <stdio.h>
    
    unsigned char func(unsigned char para)
    {
    	int i = 0,num = 0;
    	for(;i < 8;i++)
    	{
    		if(para & 0x80)
    			num++;
    		para <<= 1;
    	}
    	return num;
    }
    
    int main(void)
    {
    	unsigned char input = 0;
    	
    	printf("请输入小于等于255的值:\n");
    	scanf("%d",&input);
    	printf("输数据的二进制数中1的位数为:%d",func(input));
    	
    	return 0;
    }
    

    方法一思想:定义num计算1的个数,因为形参是unsigned char型变量,所以设置8次循环,每一次拿形参的最高位和1相比(代码中的实现为para & 0x80),如果为真值(运算结果不为0即为真值),则num++,不管运算结果为什么,para都要左移一位(当前位比较过后让下一位顶替当前位成为最高位,然后再与0x80比较),8次循环完成,8个bit也就比较完成了,然后返回num作为1的个数即可。

    方法二

    #include <stdio.h>
    
    unsigned char func(unsigned char para)
    {
    	if(para & 0x01)	para = para;	//这句可以注释掉
    	if(para & 0x02)	para = (para & 0xfd) + 1;
    	if(para & 0x04)	para = (para & 0xfb) + 1;
    	if(para & 0x08)	para = (para & 0xf7) + 1;
    	if(para & 0x10)	para = (para & 0xef) + 1;
    	if(para & 0x20)	para = (para & 0xdf) + 1;
    	if(para & 0x40)	para = (para & 0xbf) + 1;
    	if(para & 0x80)	para = (para & 0x7f) + 1;
    	return para;
    }
    
    int main(void)
    {
    	unsigned char input = 0;
    	
    	printf("请输入小于等于255的值:\n");
    	scanf("%d",&input);
    	printf("输数据的二进制数中1的位数为:%d",func(input));
    	
    	return 0;
    }
    

    方法二思想:方法二这个思想作为面试题,我也是想了两个小时才想出来(能力有限,大神有更简单的方法欢迎指点一二)。
    该函数的特点是内部不使用其他变量,这种方法可以用于极限减少栈使用的情况(不过一般也不差这点)。其思想是8个if语句用于分别判断参数
    的1到8位,1的个数放在低位,如果判断为真值,那么必然1的值就+1,这时候只需要把当前位置零并加上1,那么包含当前位以下的所有位就表示1的数量。比如:
    输入56 56的二进制为0011 1000
    因为低三位均为0,我们直接判断第4、5、6个if语句。
    先看第4个if语句:

    if(para & 0x08)	para = (para & 0xf7) + 1;
    if条件是用于判断第4个位是否为1,明显条件成立,第4位为1。
    para = 0011 1000								0xf7 = 1111 0111
    para & 0xf7 + 1 = 0011 0000 + 1 = 0x0011 0001
    

    再看第5个if语句:

    if(para & 0x10)	para = (para & 0xef) + 1;
    if条件是用于判断第5个位是否为1,明显条件成立,第5位为1。
    para = 0011 0001(语句4的运算结果)				0xef = 1110 1111
    para & 0xef + 1 = 0010 0001 + 1 = 0x0010 0010
    

    最后看第6个if语句:

    if(para & 0x20)	para = (para & 0xdf) + 1;
    if条件是用于判断第6个位是否为1,明显条件成立,第6位为1。
    para = 0x0010 0010(语句5的运算结果)				0xdf = 1101 1111
    para & 0xef + 1 = 0000 0010 + 1 = 0x0000 0011
    

    后面的7和8位均为0,就不用做比较了,结果为para = 0x0000 0011 = 3
    最初的para为65(二进制为0011 1000),1的位数确实为3,结果正确。
    原理不麻烦,就是表述起来繁琐而已,读者多输入数据自己验证就好了。

    其他的方法还有好几种,都是很基础但是很精辟的方法,读者可以参考一下下面这篇文章,除了上面两种以外的4种方法:
    C语言 统计整数二进制中表示1的个数

    展开全文
  • 可以考虑每次找到从最低位开始遇到的第一个1,计数,再把它清零,清零的位运算操作是与一个零,但是在有1的这一位与零的操作要同时不影响未统计过 的位数和已经统计过的位数,于是可以有这样一个操作 n&(n-1) ,这个...

    主要是为了记录最后一种神奇的方法。

    原文地址:http://www.cnblogs.com/xianghang123/archive/2011/08/24/2152408.html

     

    这是一个很有意思的问题,也是在面试中最容易被问到的问题之一。这个问题有个正式的名字叫Hamming_weight,而且wikipedia上也提供了很好的位运算解决的方法,这个下面也会提到。

    解决这个问题的第一想法是一位一位的观察,判断是否为1,是则计数器加一,否则跳到下一位,于是很容易有这样的程序。

    int test(int n)
    {
        int count=0;
        while(n != 0){
            if(n%2 ==1)
                count++;
            n /= 2;
        }
        return count;
    }

    或者和其等价的位运算版本:

    int test(int n)
    {
        int count=0;
        while(n != 0){
            count += n&1;
            n >>= 1;
        }
        return count;
    }

    这样的方法复杂度为二进制的位数,即,于是可是想一下,有没有只与二进制中1的位数相关的算法呢。

    可以考虑每次找到从最低位开始遇到的第一个1,计数,再把它清零,清零的位运算操作是与一个零,但是在有1的这一位与零的操作要同时不影响未统计过 的位数和已经统计过的位数,于是可以有这样一个操作 n&(n-1) ,这个操作对比当前操作位高的位没有影响,对低位则完全清零。拿6(110)来做例子,第一次 110&101=100,这次操作成功的把从低位起第一个1消掉了,同时计数器加1,第二次100&011=000,同理又统计了高位的 一个1,此时n已变为0,不需要再继续了,于是110中有2个1。

    代码如下:

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

    这几个方法虽然也用到了位运算,但是并没有体现其神奇之处,下面这个版本则彰显位运算的强大能力,若不告诉这个函数的功能,一般一眼看上去是想不到这是做什么的,这也是wikipedia上给出的计算hamming_weight方法。

    int test(int n)
    {
        n = (n&0x55555555) + ((n>>1)&0x55555555);
        n = (n&0x33333333) + ((n>>2)&0x33333333);
        n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
        n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
        n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);
      
        return n;
    }

    没有循环,5个位运算语句,一次搞定。

    比如这个例子,143的二进制表示是10001111,这里只有8位,高位的0怎么进行与的位运算也是0,所以只考虑低位的运算,按照这个算法走一次

    +---+---+---+---+---+---+---+---+
    | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |   <---143
    +---+---+---+---+---+---+---+---+
    |  0 1  |  0 0  |  1 0  |  1 0  |   <---第一次运算后
    +-------+-------+-------+-------+
    |    0 0 0 1    |    0 1 0 0    |   <---第二次运算后
    +---------------+---------------+
    |        0 0 0 0 0 1 0 1        |   <---第三次运算后,得数为5
    +-------------------------------+

    这里运用了分治的思想,先计算每对相邻的2位中有几个1,再计算每相邻的4位中有几个1,下来8位,16位,32位,因为2^5=32,所以对于32位的机器,5条位运算语句就够了。

    像这里第二行第一个格子中,01就表示前两位有1个1,00表示下来的两位中没有1,其实同理。再下来01+00=0001表示前四位中有1个1,同样的10+10=0100表示低四位中有4个1,最后一步0001+0100=00000101表示整个8位中有5个1。

    转载于:https://www.cnblogs.com/cyttina/archive/2012/10/24/2736974.html

    展开全文
  • C语言实现统计整数出现次数

    千次阅读 2018-04-10 09:55:10
    统计每一个整数出现的次数 输入-1表示结束 */ #include &lt;stdio.h&gt; int main() { const int MAX_NUMBER = 10; int x; scanf("%d",&amp;x); int a[MAX_NUMBER]; ...
    /**
        写一个程序,输入数量不确定的[0,9]范围内的整数
        统计每一个整数出现的次数
        输入-1表示结束 
    */
    #include <stdio.h>
    int main()
    {
        const int MAX_NUMBER = 10; 
        int x;
        scanf("%d",&x);
        int a[MAX_NUMBER];      //a[0]统计0出现的次数 a[9]统计9出现的次数... 
        //初始化数组
        for(int i = 0; i < MAX_NUMBER; i++){
            a[i] = 0;
        } 
        while( x != -1 ){
            if(x >= 0 && x <= 9){
                a[x] ++;
            }
            scanf("%d",&x);
        }   
        //输出相对应的结果
        for(int i = 0; i < MAX_NUMBER; i++){
            printf("%d:%d\t",i,a[i]); 
        } 
        return 0;
    }
    展开全文
  • 统计一个整数中, 某个数字出现的次数, 并将统计结果. 一个整数为12131415, 那么它里面出现了4次1. 请用程序实现 统计一个整数中, 某个数字出现的次数, 并将统计结果. 函数定义 int count_digit (int number1, int ...
  • 题要求统计一个整型序列中出现次数最多的整数及其出现次数。 输入格式: 输入在一行中给出序列中整数个数N(0<N≤1000),以及N个整数。数字间以空格分隔。 输出格式: 在一行中输出出现次数最多的整数及其出现...
  • c语言:统计整数二进制表示中1的个数(汉明重量)

    万次阅读 多人点赞 2013-08-20 21:29:32
    刚刚接触这个问题的时候是上学期吧,大一,还刚接触软件工程,接触c语言,对一些问题的看法也比较单纯。 那时候,就想着纯粹的一个个数来着,声明一个计数变量,满足条件(尾数是1),就加一,然后 / 2(二进制),...
  • C语言 统计整数二进制表示中1的个数(转载) 这是一个很有意思的问题,也是在面试中最容易被问到的问题之一。这个问题有个正式的名字叫Hamming_weight,而且wikipedia上也提供了很好的位运算解决的方法,这个...
  • C语言经典例题--统计整数出现次数

    千次阅读 2018-07-26 10:18:18
    输入不确定数量的【0,9】范围内的整数统计每一个整数出现的次数,输入-1表示结束 #include &lt;stdio.h&gt; int main() { const int number = 10; int x; int i; int count[number]; for (i = 0;...
  • 统计一个整数的位数 本题要求编写程序,对于给定的整数N,求它的位数。 输入格式: 输入在一行中给出一个绝对值不超过10​9的整数N。 输出格式: 在一行中输出N的位数。 输入样例1: 12534 输出样例1: 5 输入样例2:...
  • C语言统计素数并求和

    千次阅读 2020-08-10 19:21:45
    统计给定整数M和N区间内素数的个数并对它们求和。 输入格式: 输入在一行中给出两个正整数M和N(1≤M≤N≤500)。 输出格式: 在一行中顺序输出M和N区间内素数的个数以及它们的和,数字间以空格分隔。 输入样例: 10 31...
  • c语言 统计素数并求和

    千次阅读 2020-03-07 23:07:10
    本题要求统计给定整数 M 和 N 区间内素数的个数并对它们求和。 输入格式: 输入在一行中给出两个正整数 M 和 N(1≤M≤N≤500)。 输出格式: 在一行中顺序输出 M 和 N 区间内素数的个数以及它们的和,数字间以空格...
  • #include "stdio.h" #include "stdlib.h" #include "string.h" ... printf("请输入一个整数:"); scanf("%d", &in_int); //printf("输入的整数:%d\n", c); char buf[100]={0}; int len
  • ⑴ 随机生成乘法或除法运算符。 ⑵ 随机生成100以内的两个正整数。 ⑶ 乘法的计算结果不得大于100,否则重新生成题目。...⑺ 练习结束后,统计并输出回答正确和错误的题目数、最后得分,并给出相应的评语。
  • c语言整数算法训练

    2018-07-24 19:22:21
    题目:通过编程实现,统计1~n有多少个9 提示:n通过参数传入 #include &lt;stdio.h&gt; int main() { int n,i,j; int k = 0; printf("Please input a number :"); scanf("%d",&...
  • /*《C语言程序设计》江宝钏主编-习题5-1-统计整数 Description 从键盘输入任意20个整数,统计其中的负数个数,并求所有整数的平均值。 Input 20个整数 Output 负数个数和整数平均值(保留1位小数) Sample Input...
  • C语言整数乘除法练习器 任务描述:编写一个整数乘除法练习器,提供给小学生使用。可进行100以内任意两个整数的乘除法练习。 功能要求:(1)随机生成乘法或除法运算符。 (2)随机生成100以内的两个正整数。 (3)...
  • c语言 统计学生平均成绩与及格人数

    千次阅读 2020-03-15 10:39:43
    **本题要求编写程序,计算学生们的平均成绩,并统计及格(成绩不低于60分)的人数。题目保证输入与输出均在整型范围内。 输入格式: 输入在第一行中给出非负整数N,即学生人数。第二行给出N个非负整数,即这N位学生的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,026
精华内容 410
关键字:

c语言统计整数

c语言 订阅