当前位置:Gxlcms > mysql > 【编程之美】2.1求二进制中1的个数

【编程之美】2.1求二进制中1的个数

时间:2021-07-01 10:21:17 帮助过:39人阅读

题目: 对于一个字节的无符号整数变量,求其中的二进制表示中1的个数,要求算法执行效率尽可能高效。 题目解析: 这道题同样在【剑指offer】面试题10:二进制中1的个数中出现,不过在剑指offer中没有提到无符号数,因此比该题目中多考虑一个层次。下面总结这


题目:

对于一个字节的无符号整数变量,求其中的二进制表示中1的个数,要求算法执行效率尽可能高效。


题目解析:

这道题同样在【剑指offer】面试题10:二进制中1的个数 中出现,不过在剑指offer中没有提到无符号数,因此比该题目中多考虑一个层次。下面总结这道题的几种解法。


解法一(用于该题目):

我们通常会想到除以2就是将二进制右移一位,但要判断移除的是0还是1,就要对2取余。思路很简单,通过四则运算来解答:

int Count(Byte v)
{
    int num = 0;
    while(v){
        if(v%2)
            num++;
        v /= 2;
    }
    return num;
}

解法二(用于该题目)

对于除以2来表示二进制右移,除法的效率比直接移位的效率低得多。碰到这样的题目,尽量用移位来代替。位运算就五种形式:与、或、异或、左移和右移。在这些范围里面找到自己想要的运算。移位时要判断移除的是0还是1,那么这里就应该通过与操作判断最后一位是否为1。

int Count2(Byte v)
{
    int num = 0;
    while(v){
        if(v & 1)
            num++;
    //也可以用 num += v&1; 来代替上面两行
        v = v >> 1;
    }
    return num;
}

解法三(可以用于有符号数):

如果这个题目是有符号的话,当右移的时候,会在高位补充符号位,用上面两种方法的话,会陷入死循环。如何避免?可以先判断最高位,然后遍历n-1次判断除了最高位以外的位是否为1。这样的方法比较麻烦。我们可以变通一个思路,让与的那一位1不断的左移,直到将1移到最高位。

int Count3(Byte v)
{
    int num = 0;
    int flag = 1;
    while(flag){
        if(v & flag)
            ++num;
        flag = flag << 1;
    }
    return num;
}

解法四(更加高效的算法):

这种方法,充分利用了二进制的相关操作,平时应该多收集这样的运算。

一个数不为0,那么二进制中肯定含1。当让这个数减去1时,最低位的1由1->0,更低位的0由0->1。当让n与n-1相与以后,n中最低位的1变成0。一次这样的操作,消去一个1,那么二进制中有多少个1,就循环多少次即可。

int Count4(Byte v)
{
    int num = 0;
    while(v){
        ++num;
        v = v & (v-1);
    }
    return num;
}


解法五(空间换时间方法):

其实方法四已经够好了,但是因为只涉及到八位,我们可以利用选择直接选取相应的数据。比如0x1-0x2-0x4...这些都包含1个1;0x3-0x6...包含两个1;等等。通过switch语句选择相应的结果。但是这种方法效率可能比较低,因为,当输入v为255的时候,得比较到最后才能找到相应的数据。

int Count5(Byte v)
{
    int num = 0;
    switch(v){
    case 0x0:
        num = 0;
        break;
    case 0x1:
    case 0x2:
        ....
    }

    return num;
}

解法六(哈希表法):

既然想到了利用空间换时间,我们干脆用个数组来表示,index为要查找的数,counttable[index]为该数据包含1的个数。







人气教程排行