二进制中 1 的个数
题目描述:请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。
例如: 9 表示成二进制是 1001, 有 2 位是 1 。因此如果输入 9 ,该函数输出 2 。
先看一种错误的解法:
intNumberOf1(intn){intcount=0;while(n){if(n&1)count++;n=n>>1;}returncount;}
注意:在使用乘法或者除法的运算时,尽量使用移位运算代替,因为移位运算的效率要比乘除法高很多!
上述解法的问题在于:输入一个正数,结果没有问题,但是,如果输入一个负数的话,会发生什么情况?
我们知道,负数的二进制的最高位为 1 ,当进行右移操作时,最高位要补上符号位也就是 1 ,因此每右移一位,最高位就补 1 ,最终这个数字就会变成0xFFFFFFFF,而陷入死循环。
常规解法
intNumberOf1_Solution1(intn){intcount=0;unsignedintflag=1;while(flag){if(n&flag)count++;flag=flag<<1;}returncount;}
此解法中循环的次数等于整数二进制的位数,32位的整数需要循环32次。
高效的解法
intNumberOf1(intn){intcount=0;while(n){++count;n=(n-1)&n;}returncount;}
该解法在整数中有几个 1 就只需要循环几次。
相关题目
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。