精华内容
下载资源
问答
  • 统计二进制数中“1”的个数(懂二进制

    问题描述:世界上有10种人,一种懂二进制,一种不懂。那么你知道两个int32整数m和n的二进制表达,有多少个位(bit)不同么?

    函数原型: int countBitDiff(int m, int n)

    输入:

    1999 2299

    输出:

    7

    解析: 本题目来自2016年小米的在线笔试题,要比较mn的二进制位的不同,可以借助额外的变量v以及异或操作来实现,做法是:

    v=m^n;
    

    经过异或操作后v的二进制表示中的二进制数1的数量就是mn的不同二进制位的个数,问题转化为求一个二进制数v中二进制数1的个数。


    解法一:逐位比较

    最容易想到的方法是将v中各个位上的二进制值逐一与1比较,《C和指针》中使用移位运算符实现了这样的比较:

    /**
     * 获得两个整形二进制表达位数不同的数量
     * @param m 整数m
     * @param n 整数n
     * @return 整型
     */
    int countBitDiff(int m, int n) {
        unsigned int c = m ^ n; 
        char ones;
        for (ones = 0; c != 0; c >>= 1) {
            if ((c & 1) != 0)
                ones += 1;
        }
        return ones;
    }

    解法二:借助n&(n-1)

    第二种方法比较特殊,用到了按位与特一个特殊性质,即:

    假设二进制数n中有k位上的二进制值是1,
    那么n&(n-1)中二进制值为1的位数为k-1.

    使用n&(n-1)的特殊性质,可以编写如下代码:

    /**
     * 获得两个整形二进制表达位数不同的数量
     * @param m 整数m
     * @param n 整数n
     * @return 整型
     */
    int countBitDiff(int m, int n) {
        int c = m ^ n; //按位异或
        char counter = 0;
        for (; c; ++counter) c &= (c - 1);
        return counter;
    }
    展开全文
  • 容易想到,将与1按位与,然后右移,每次都跟1相与统计1的个数,这种方法对于无符号是可以的,但是对于有符号而言,其右移后再高位空出部分会添加1,也就是说,该方法对于无符号而言会陷入死循环。...

    容易想到,将数与1按位与,然后右移,每次都跟1相与统计1的个数,这种方法对于无符号数是可以的,但是对于有符号数而言,其右移后再高位空出部分会添加1,也就是说,该方法对于无符号数而言会陷入死循环。
    方法一
    由于左移是始终在空出的低位添加0的,那么不妨使用一个1来和待统计的二进制数进行按位与操作,然后将1进行二进制的左移操作,从低位到高位依次统计每个位置是否为1。

    int CountNumUseFlag(int n){
        int flag = 1;
        int count = 0;
        //通过flag左移与n按位与的方式来“遍历”n,统计1的个数
        while (flag){
            if (n&flag){
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }

    方法二
    将待统计的二进制数字n和n-1**按位与**,按位与后的结果相当于除去了最右边的1,即二进制序列中少了一个1,循环进行按位与操作,每次得到的结果都使得二进制序列1的数量少1个,那么当最后二进制序列为0的时候,即可得到其中1的数量。
    其原理是利用了二进制进位的特点,每次减1,由于借位,那么最右边的1会变为0,而该位右边的所有位都变为1,即n&(n-1)之后,n中位置最靠右的那个1变为了0,此时计数器+1计数,直至n全为0,则表示计数完毕。

    int CountNum(int n){
        int count = 0;
    //刚开始移n&(n-1)作为循环条件,是错误的,因为最后一个1的时候,想与是为0的,因而会少统计一个
        while ( n )        //只要n非零,就代表肯定存在1
        {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
    

    测试代码

    void Test(int number, unsigned int expected){
        int actual = CountNumUseFlag(number);
        if (actual == expected)
            printf("Solution1: Test for %p passed.\n", number);
        else
            printf("Solution1: Test for %p failed.\n", number);
    
        actual = CountNum(number);
        if (actual == expected)
            printf("Solution2: Test for %p passed.\n", number);
        else
            printf("Solution2: Test for %p failed.\n", number);
    
        printf("\n");
    }
    
    int main(int argc, char* argv[]){
        // 输入0,期待的输出是0
        Test(0, 0);
        // 输入1,期待的输出是1
        Test(1, 1);
        // 输入10,期待的输出是2
        Test(10, 2);
        // 输入0x7FFFFFFF,期待的输出是31
        Test(0x7FFFFFFF, 31);
        // 输入0xFFFFFFFF(负数),期待的输出是32
        Test(0xFFFFFFFF, 32);
        // 输入0x80000000(负数),期待的输出是1
        Test(0x80000000, 1);
        return 0;
    }
    展开全文
  • 统计二进制数字中1的个数

    千次阅读 2013-09-09 18:32:49
    统计二进制数字中1的个数 三种方法 1.逐位比较 O(n) = 32 int Count1(int n) { int count = 0; while (n != 0) { count += n&1; n >>= 1; } return count; } 2.最低1位清零 O(n) = ...

    统计二进制数字中1的个数
    三种方法 
    1.逐位比较 O(n) = 32

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

    2.最低1位清零 O(n) = count(n) //适用于1很稀疏的情况

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

    3.直接位运算 O(n) = 5

    int Count3(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;
    }

    统计二进制数字中1的个数,这个问题有个专业的名字:Hamming_weight problem

    int Hamming_weight(int n, int type)
    {
    	switch (type)
    	{
    	case 1:
    		return Count1(n);
    		break;
    	case 2:
    		return Count2(n);
    		break;
    	case 3:
    		return Count3(n);
    		break;
    	default:
    		return -1;
    		break;
    	}
    }

    wiki百科参考:
     http://en.wikipedia.org/wiki/Hamming_weight

    展开全文
  • 在平时的工作当中,会遇到很多需要使用bitmap的情况,那么,针对这种状况,统计二进制位中值为1的位一共有多少个的时候,我们需要慎重的根据当前的使用场景来选择自己的算法,比如需要考虑当前的时间复杂度、空间...

    背景

    在平时的工作当中,会遇到很多需要使用bitmap的情况,那么,针对这种状况,统计二进制位中值为1的位一共有多少个的时候,我们需要慎重的根据当前的使用场景来选择自己的算法,比如需要考虑当前的时间复杂度、空间复杂度等等。

    问题

    统计二进制位中值为1的位的总数

    算法

    1.遍历法

    使用循环按位统计1的个数,其时间复杂度为O(n),空间复杂度为O(1)。

    2.查表法

    利用一个数组或哈希生成一张表,存储不同二进制编码对应的值为1的二进制位数,那么在使用时,只需要去进行查询,即可在O(1)的时间复杂度内得到结果。

    但是,此算法有个弊端,由于算法是采用空间换取时间的方法,当一个二进制数的位长超过一定限度时,对应的表也就会占据很大的空间,也就是说节约时间越多,花费的存储越多。另外此方法还会收到CPU缓存的限制,如果表太大,表在缓存的上下文切换也就越多,可能会导致性能没有想象中那么高。

    所以,为了解决此问题,一般情况下,采用适当的二进制位长度来建表,比如8位、16位,这样情况下,可以对上述问题得到一个平衡,不仅可以享受到优越的性能,而且时间开销也没有遍历法高。

    当二进制总长度为n,建表的二进制长度为m时,总的时间复杂度为 O ( ⌊ m n ⌋ ) O(\lfloor \frac{m}{n} \rfloor) O(nm)

    3.variable-precision SWAR算法

    在数学上,我们一般称上述问题为“计算汉明重量”,而当前一直效率最好的通用算法为variable-precision SWAR算法,该算法不仅在常数时间计算多个字节的汉明重量,而且不需要使用任何额外的内存。

    //注:此处函数的参数必须为无符号数。如果是有符号数,可以先强转为无符号,再使用此算法。
    
    //计算32位长度位数组的算法实现
    uint32_t swar(uint32_t i){
    	//相邻两位一组,就是各组的汉明重量
    	i = ( i & 0x55555555 ) + ( ( i >> 1 ) & 0x55555555 );
    
    	//相邻四位一组,就是各组的汉明重量
    	i = ( i & 0x33333333 ) + ( ( i >> 2 ) & 0x33333333 );
    
    	//相邻八位一组,就是各组的汉明重量
    	i = ( i & 0x0F0F0F0F ) + ( ( i >> 4 ) & 0x0F0F0F0F );
    
    	//将结果保存带低八位
    	i = ( ( i * 0x01010101 ) >> 24 );
    	
    	return i;
    }
    

    对应算法的详细过程及数学原理,可参考《variable-precision SWAR算法“计算汉明重量”》《variable-precision SWAR算法:计算Hamming Weight》这两篇文章。

    Redis中的使用

    在Redis中,使用了上述后两种算法来实现BITCOUNT命令。

    • 当处理的二进制位数大于128位,采用variable-precision SWAR算法来计算;
    • 当处理的二进制位数小于128位,采用查表算法来计算;

    注:上述数值参考《Redis设计与实现》

    展开全文
  • Redis源码解析——统计二进制数1的个数
  • 那么我们会发现,10%2是判断二进制数的最后一位是0还是1,判断完成后向右移一位即10/2得到5,接着5%2判断二进制数的倒数第二位是0还是1,判断完成后向右移一位即5/2得2,重复这个过程,直到0/2结束。最终我们得到了...
  • 二进制1的个数统计

    2018-04-25 17:03:27
    方法一:先将整数通过方法转化为二进制数,然后统计其中1数量即可。 public class Solution {  public int NumberOf1(int n) {  String str=Integer.toBinaryString(n);  int num=0;  ...
  • LeetCode题解(0191):判断二进制数中为1的位的数量(Python) 题目:原题链接(简单) 解法 执行用时 Ans 1 (Python) 28ms (>99.12%) Ans 2 (Python) 44ms (>52.18%) 解法一(转换为字符串统计): ...
  • 主要介绍了php实现统计二进制1的个数算法,结合实例形式分析了php字符串遍历、判断、统计等相关操作技巧,需要的朋友可以参考下
  • 21. 二进制位数组

    2020-06-08 16:14:10
    3)BITCOUNT:统计位数组里面,值为1二进制位的数量 4)BITOP:既可以对多个位数组进行按位与(and)、按位或(or)、按位异或(xor)运算,也可以对给定的位数组进行取反运算。(异或:一正一
  • 二进制数1的个数

    2016-04-23 17:07:51
    二进制数1的个数 本文主要转载自zzd的算法-求二进制数1的个数。除此之外,本文还对原文中供的几种算法进行测试以及做了一定的分析。 问题描述 任意给定一个32位无符号整数n,求n的二进制表示中1的个数,...
  • 统计非负整数二进制展开中1的总数。如整数64 的二进制展开为00000000 00000000 00000000 00100000 ,1的总数为1。 输入格式: 输入一个整数n , 题目保证n 不大于 10的18次方。 输出格式: 输出该整数...
  • 经典算法-统计0~n之间的数字二进制1的个数 题目描述: 给定一个数字n,统计0~n之间的数字二进制1的个数,并用数字输出 例子: 当n = 5 时 返回的结果应该是:[0,1,1,2,1,2] 要求: 算法复杂度o (n) 空间复杂度...
  • 题目:程序读入一个整数 n,假设 n 不会大于 1000,请输出 1 到 n 每个数字的二进制表示 1 的个数。
  • 利用异或判断二进制数中的1的个数的奇偶性

    千次阅读 多人点赞 2018-11-25 16:21:30
    二进制数中的1的个数的奇偶性: 如果一个二进制数中的1的个数为奇数,那么返回1;如果为偶数,那么返回0。 给定二进制数01,它只有两位,那么它的奇偶性可以通过0^1 = 1获得,这里返回1,与它是奇数相符合。 给定...
  • 统计[L,R]区间内的所有二进制下包含的“1”的个数之和。  如5的二进制为101,包含2个“1”。 输入格式  第一行包含2个L,R 输出格式  一个S,表示[L,R]区间内的所有二进制下包含的“1”的个数之和。 ...
  • DATA SEGMENT ...二进制为01111011故总共有6个1 Y DB ? ;计算的结果存放在 这里 DATA ENDS CODE SEGMENT ASSUME CS:CODE,DS:DATA  BEGIN:MOV AX,DATA  MOV DS,AX  MOV BX,0  MOV CL,8  
  • Python统计二进制1的个数

    千次阅读 2020-02-14 14:50:12
    现有一个整数,将该整数转化为二进制形式,并统计二进制中1的个数(如果是负数,按补码统计1的个数) 涉及知识点讲解 进制介绍 在计算机中,有四种进制,分别是 2进制、8进制、10进制和16进制。具体内容如下所示: ...
  • Java计算二进制数1的个数

    千次阅读 2018-11-18 15:18:18
    前言 逐位法 查表法 Brian Kernighan法 分治法 Hamming Weight法 Hamming Weight优化法 ... 昨天学习全组合时,突然涉及到如何计算二进制1的问题,我就直接使用的Integer.bitCount的...
  • 当然另外一种思路是,一个数二进制1的个数是它除去最高位那个1之后1的个数再➕1(因为2^n的二进制只有最高位为1)。 比如7的二进制表示为:111(100+011),其中1的个数为1➕011中1的个数,即f(7) = 1+f(3)。 ...
  • Redis提供了SETBIT,GETBIT,BITCOUNT,BITOP四个命令用于处理二进制位数组(bit array,又称"位数组"). 位数组的表示 使用SDS结构保存位数组,使用SDS的操作函数处理位数组。但是,为了简化SETBIT的实现,保存位数组的...
  • O(logn) 的解法: ... 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(i = 1; i <= n; i++
  • 快速统计二进制1的个数(分析篇)

    万次阅读 多人点赞 2016-08-16 15:12:46
    今天做了一道题,发现n&=(n-1)这个式子很好奇,然后试着算了一遍发现它竟然能够快速统计二进制1的个数,特此拿来分享一下。 首先,分析一下该式子,先可以简化为 n=n&(n-1); 我们先做一个实例, n ...
  • 欢迎点击「算法与编程之美」↑关注我们!题目:对于一个字节(8bit)的变量,求其二进制中“1”的个数,要求算法的执行效率尽可能地高。举例:十进制整数162的二进制表示...
  • 统计一个对应二进制中【1】的个数或者【0】的个数最佳方法 一、二进制中【1】的个数 /** * countOne TODO : 统计一个所对应二进制1 的个数最好的方法 * @param num 该所对应的十进制 * @return 该...
  • 算法理解——统计二进制1的个数

    千次阅读 2013-05-06 10:44:00
    最近读了一篇关于统计二进制位中1的文章:http://www.cnblogs.com/kaikai/archive/2006/02/15/330901.html  里面提到的第三种算法对于解决1比较多的情形,显然是比较高效的。因为算法三的时间复杂度是log...
  • 本题首先要将数字转变为二进制,然后再统计二进制中的1数量。 如果1数量相同,则按数值的大小排列。 所以本题的关键在于compare的重写 代码 class Solution { public int[] sortByBits(int[] arr) { Integer[]...
  • 如何求二进制数中丁的个数 腾讯笔试 题目描述: 给定一个整数,输出这个整数的二进制表示中 l 的个数。例如 : 给定整数 7,其二进制表示为 111, 因此输出结果为 3。 方法一: 移位法 可以采用位操作来完成 。具体思路...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,919
精华内容 32,367
关键字:

二进制数1的数量统计