剑指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一直为真,而且在左移过程中一直都为真。
欢迎选择我的课程,让我们一起见证您的进步~~
一个int通常是32位, 最多左移32次后flag就成0了.
int
32位
32次
flag
0
不过话说, 求1个数不应该是这样做么:
int NumberOf1_Solution1(int n) { int count = 0; while (n) { n = n & (n-1); count++; } return count; }
不会一直为真的。反复左移,总会有把1移出的那一刻。
在vs2010 SP1环境下测试了一下,运行正常。 首先,进行左移的时候如果移出最高位,那么移出的比特位会被舍弃,所以不会死循环 其次,题主的写法效率不高,复杂度是满的log(n)的,通常采用如下写法
log(n)
cppwhile(n) n-=n&-n,count++;
cpp
while(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)
O(count)
n&-n
f[i]
f[i]=f[i>>1]+(i&1)
f[(unsigned)n>>16]+f[n&65535]
一个
int
通常是32位
, 最多左移32次
后flag
就成0
了.不过话说, 求1个数不应该是这样做么:
不会一直为真的。反复左移,总会有把1移出的那一刻。
在vs2010 SP1环境下测试了一下,运行正常。
首先,进行左移的时候如果移出最高位,那么移出的比特位会被舍弃,所以不会死循环
其次,题主的写法效率不高,复杂度是满的
log(n)
的,通常采用如下写法复杂度为
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)