精华内容
下载资源
问答
  • value) //每次运算n消去二进制最后一位1 { int count = 0 ; while (value!= 0 ){ value = value&(value - 1 ); count ++ ; } return count; } int main(){ printf( " %d\n " , print_one_bits01...
    #include<stdio.h>
    #include<stdlib.h>
    int print_one_bits01(unsigned int value){                   //0000 1111  
                                                                //&0000 0001   value右移i次 每次和1 &运算
        int count = 0;
        int i = 0;
        for (; i <32; i++)
        {
            if (((value >> i) & 1) == 1)
                count++;
        }
        return count;
    }
    int print_one_bits02(unsigned int value){                //移位操作符不会改变值大小,需要用=赋值
        int count = 0;                                         //思路:  i=0000 0001
        int i = 1;                                             //       value=0000 1111  &1

    for (i = 1; i != 0;i<<=1) // value>>=0000 0111 { // i=0000 0010 i只是测定是否溢出 value自己右移和1比较 if ((value & 1) == 1) { count++; } value = value >> 1; } return count; } int print_one_bits03(unsigned int value) //每次运算n消去二进制最后一位1 { int count = 0; while (value!=0){ value = value&(value - 1); count++; } return count; } int main(){ printf("%d\n", print_one_bits01(15)); printf("%d\n", print_one_bits02(15)); printf("%d\n", print_one_bits03(15)); system("pause"); return 0; }

     

    转载于:https://www.cnblogs.com/Duikerdd/p/9853006.html

    展开全文
  • 题目:程序读入一个整数 n,假设 n 不会大于 1000,请输出 1 到 n 每个数字的二进制表示 1 的个数

    题目一

    计算十进制数字在二进制表示 1 的个数

    举个例子:

    • 十进制数字为 1 时,它的二进制表示是 001,二进制表示 1 的个数为 1;
    • 十进制数字为 2 时,它的二进制表示是 010,二进制表示 1 的个数为 1;
    • 十进制数字为 3 时,它的二进制表示是 011,二进制表示 1 的个数为 2;
    • 十进制数字为 4 时,它的二进制表示是 100,二进制表示 1 的个数为 1;
    • 十进制数字为 5 时,它的二进制表示是 101,二进制表示 1 的个数为 2;
    • 十进制数字为 6 时,它的二进制表示是 110,二进制表示 1 的个数为 2;
    • 十进制数字为 7 时,它的二进制表示是 111,二进制表示 1 的个数为 3;

    时间复杂度 O(logn) 的解法

    对于这个题目比较容易想到的是如下代码:

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

    上述代码主要做了两个步骤:

    • n % 2 表示对数字求模运算,也就是计算二进制的末尾是 1 还是 0,如果二进制的末尾是 1 ,则 count 自增,count 表示的是二进制表示 1 的个数;
    • n = n >> 1 表示把二进制往右移走一位,比如十进制数字 7 的二进制表示是 111 ,那么通过右移一位后,则变成 011。

    这个解决方式虽然能计算出二进制表示 1 的个数,但是我们可以发现这个解法的时间复杂度是 O(logn),比如当 n 为 7 时,它的二进制表示是 111,那么它将会循环 3 次,也就是非常接近 log 以 2 为底 7 的对数的值。


    题目二

    程序读入一个整数 n,假设 n 不会大于 1000,请输出 1 到 n 每个数字的二进制表示 1 的个数。

    时间复杂度 O(nlogn) 的解法

    可能有的小伙伴说,这题目二还不简单?直接把上面的解法,增加个 for 循环不就得了。

    int main() 
    {
    	int i, j, n, count;
    	
    	scanf("%d", &n);
    	
    	for(i = 1; i <= n; i++)
    	{
    		j = i;
    	    count = 0;
    		
        	while(j != 0)
        	{
                if(j % 2 == 1)
                {
                    count++;
                }
        
        		j = j >> 1;
        	}
        	
        	printf("number:%d, count:%d\n", i, count);
    	}
    
    	return 0;
    }
    

    假设输入 7,则输出结果:

    number:1, count:1
    number:2, count:1
    number:3, count:2
    number:4, count:1
    number:5, count:2
    number:6, count:2
    number:7, count:3
    number:8, count:1
    

    没错,用上述的解法增加个 for 循环,确实可以解决题目二的要求,这值得鼓励,但是程序的时间复杂度是时间复杂度 O(nlogn) ,运行效率不高,所以我们必须要有种精神,就是要用时间复杂度最少的方式去解决算法的问题,这样才能一次一次的进步。

    时间复杂度 O(n) 的解法

    请先观察下面的位运算性质:

    y = x & (x - 1)
    

    我们看到,x 和与 x -1 这两个数字做按位与运算,所以我们要以二进制的角度去思考这个问题。

    比如:

    • 假设 x 是 3,它的二进制是 011;
    • 那么 x - 1 就是 2,它的二进制是 010;
    • x & (x - 1) 运算后的二进制就是 010。

    那么 x & (x - 1) 实际效果等效于去掉 x 二进制表示中的最后一位 1,从而我们发现原来 y 变量与 x 变量在二进制表示中,只差一个 1。

    如果我们用一个数组 f 记录相应数字二进制表示中 1 的数量,那么 f[i] 数组存放的值是 i 这个数字二进制表示中 1 的数量,从而我们可以推导得到 f[i] = f[i & (i - 1)] + 1,也就是说 i 数字比 i & (i - 1) 数字的二进制表示中的 1 的数量要多一个,这样我们通过一步计算就得到 f[i] 的结果,也就是相应数字二进制表示中 1 的数量结果。

    代码如下:

    int main() 
    {
        int n,i;
        int f[1001];
        
        f[0] = 0;
        
        scanf("%d", &n);
    
        for(i = 1; i <= n; i++) 
        {
            f[i] = f[i & (i - 1)] + 1;
        }
        
        for(i = 1; i <= n; i++) 
        {
            printf("%d ", f[i]);
        }
        printf("\n");
        
        return 0;
    }
    

    这个程序的过程如下:

    • 首先先读入一个整数 n,代表要求解的范围;
    • 然后循环 n 次,每一次通过 f[i] = f[i & (i - 1)] + 1 计算得到 f[i] 的值,也就是数字的二进制表示 1 的个数;
    • 最后输出 1 到 n 中每个数字二进制表示中 1 的个数。

    针对这个解法,程序的时间复杂度是 O(n)。

    在这里插入图片描述

    展开全文
  • 计算二进制1的个数

    2016-09-28 18:52:44
    问题:计算某个二进制1的个数

    问题:计算某个数的二进制中1的个数

    思路:x = x & (x-1) 将 x 的二进制最右面的一个 1 变为 0,其余保持不变。反复操作,直到变为 0 为止,计算操作次数,即为 x 的二进制中 1 的个数。

    证明:假设 x 的二进制末尾为 10...0 [末尾有 k 个 0,k = 0,1,2,...]。

    则 x - 1 的二进制末尾 k+1 位为 01...1 [末尾有 k 个 1,k = 0,1,2,...],其他与 x 相同。

    从而 x & (x-1) 的末尾 k+1 位为 00...0 [末尾有 k+1 个 0,k = 0,1,2,...],其他与 x 相同。

    即 x = x & (x-1) 将 x 的最右边的一个 1 变为 0,其余位数无变化。

    C++程序:

     
    #include <iostream>
    using namespace std;
     
    int manyOne(int x){
        int countx = 0;
        while(x){
            ++countx;
            x = x&(x-1);
        }
        return countx;
    }
     
    int main(){
        cout<<manyOne(9999)<<endl;
        return 0;
    }
    //Output: 8



    类似问题:x = x | (x+1) 将 x 的二进制最右面的一个 0 变为 1,其余保持不变。

    证明:假设 x 的二进制末尾为 01...1 [末尾有 k 个 1,k = 0,1,2,...]。

    则 x + 1 的二进制末尾 k+1 位为 10...0 [末尾有 k 个 0,k = 0,1,2,...],其他与 x 相同。

    从而 x | (x+1) 的末尾 k+1 位为 11...1 [末尾有 k+1 个 1,k = 0,1,2,...],其他与 x 相同。

    即 x = x | (x+1) 将 x 的最右边的一个 0 变为 1,其余位数无变化。


    应用:判断一个整数 x 是否为 2 的幂。

    思路:假如 x 为 2 的幂,则 x 只有最高位为 1,其余均为 0,因此按照上面的做法 x = x & (x-1) 将会为 0;反之,假如 x = x & (x-1) 为 0,则 x 只有一位为 1,其余均为 0,显然 x 为 2 的幂。

    C++程序:

    #include <iostream>
    using namespace std;
    int isTwoPow(int x){
        if( (x&(x-1)) == 0) return 1;
        else return 0;
    } 
    int main(){
        cout<<isTwoPow(256)<<endl;
        return 0;
    }
    //Output: 1

    展开全文
  • Java实现计算二进制数1的个数

    你可能以为我会用字符串遍历的方式做,但其实不是。

    建议先了解一下如何用位运算判断2的N次幂,然后再看此解:

    public int numberOfSetBits(int n) {
        int result = 0;
        for ( ; n > 0; result++) {
            n &= n-1;
        }
        return result;
    }
    
    展开全文
  • O(logn) 解法: int count = 0; while(n != 0) { if(n % 2 == 1) { count++; } n = n >> 1; } O(n) 解法: int main() { int n,i; int f[1001]; f[0] = 0; scanf("%d", &n); for...
  • * @param aLong :二进制数 * @return 1的个数 */ public static int Num1OfBinary(Long aLong){ int count = 0; // 取绝对值 Long l = Math.abs(aLong); while(l > 0) { count++; l&=(l-1...
  • 是一道网上看到前端笔试题,主要思想是利用JavaScripttoString方法将十进制数转换为二进制的字符串。然后for循环遍历计算字符串中”1″出现次数。
  • 请你将数组中元素按照其二进制表示中数字 1 数目升序排序。 如果存在多个数字二进制1 数目相同,则必须将它们按照数值大小升序排列。 请你返回排序后数组。 示例 1: 输入:arr = [0,1,2,3,4,5,6,7,8] ...
  • C++计算二进制数1的个数

    千次阅读 2019-06-20 21:14:19
    见到计算二进制数中的1的个数的比较精巧的做法,做个笔记(其实是之前被问到了,所以就查了下…) int CountOnes(int n) { int count = 0; while(n) { ++count; n = n & (n - 1); } return count; } 刚...
  • 输入一个N,统计N的二进制1的个数,如10的二进制是1010,则1的个数为2 解题方法 方法一 获取二进制位是1还是0可以先左移 做&运算,如3的二进制是11,将1左移一位与3做与运算,即11&10==10,再将10右移一...
  • #include &lt;iostream&gt; using namespace std; int func(int x) { int cnt = 0; while (x) { cnt++; x = x&...(x - 1); } return cnt; } int main() { cout &lt;&lt...
  • 二进制中有多少1 inline int count_bits
  • n-1计算二进制1的个数n&(n-1) n&(n-1) 遇到一道题,求二进制中1的个数。发现有大佬用来(n&n-1)。觉得很神奇。有空下来细想。确实是这么个道理。记录一下自己的分析过程 一、n-1发生了什么 ①、...
  • #include <stdio.h> #include <...// 计算 二进制 表示里头的 ‘1的个数 // 时间复杂度为 O (m) , m 为 bit 1 的个数 unsigned int popcnt (unsigned int num) { unsigned int ret =...
  • 输入一个10进制数字,请计算该数字相应二进制中0的个数,注意左第一个1之前的全部0都不须要计算。不须要考虑负数的情况。 题目类别: 位运算 难度: 0基础 执行时间限制: 无限制 ...
  • Java计算二进制数1的个数

    千次阅读 2018-11-18 15:18:18
    前言 逐位法 查表法 Brian Kernighan法 分治法 Hamming Weight法 Hamming Weight优化法 ... 昨天学习全组合时,突然涉及到如何计算二进制1的问题,我就直接使用的Integer.bitCount的...
  • 那么我们就来看下如何求取二进制数中的1的个数。 第一反应就是遍历数值中的二进制位,判断相应位数是否为1,若为1则累加。以下代码使用到与运算的特性: 由二元运算规则 1 & A = A 0 & A = 0 得: 假定 数值...

空空如也

空空如也

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

计算二进制数1的个数