suchen

Heim  >  Fragen und Antworten  >  Hauptteil

c++ - 二进制中1的个数

剑指offer中关于二进制中1的个数有一种解法如下:

int NumberOf1_Solution1(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag)
            count ++;

        flag = flag << 1;
    }

    return count;
}

我有一个疑问,用flag做循环判断,会不会造成无限循环,我用vs2013调试出现无限循环的情况。
个人见解:flag一直为真,而且在左移过程中一直都为真。

天蓬老师天蓬老师2807 Tage vor672

Antworte allen(3)Ich werde antworten

  • 天蓬老师

    天蓬老师2017-04-17 11:55:38

    一个int通常是32位, 最多左移32次flag就成0了.

    不过话说, 求1个数不应该是这样做么:

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

    Antwort
    0
  • 阿神

    阿神2017-04-17 11:55:38

    不会一直为真的。反复左移,总会有把1移出的那一刻。

    Antwort
    0
  • PHP中文网

    PHP中文网2017-04-17 11:55:38

    在vs2010 SP1环境下测试了一下,运行正常。
    首先,进行左移的时候如果移出最高位,那么移出的比特位会被舍弃,所以不会死循环
    其次,题主的写法效率不高,复杂度是满的log(n)的,通常采用如下写法

    cppwhile(n) n-=n&-n,count++;
    

    复杂度为O(count),其中n&-n一句是取出n的二进制中最低的为1的比特位,和楼上iSayme的写法基本相同;
    如果有大量的调用,可以通过预处理来进一步降低复杂度
    我们用f[i]表示i的二进制中1的个数,使用f[i]=f[i>>1]+(i&1)进行预处理,f数组只需要开到65536即可,预处理复杂度为O(65536)
    询问时直接返回f[(unsigned)n>>16]+f[n&65535]即可,复杂度为O(1)

    Antwort
    0
  • StornierenAntwort