C++
1 class Solution {
2 public:
3 /**
4 * @param num: an integer
5 * @return: an integer, the number of ones in num
6 */
7 int countOnes(int num) {
8 // write your code here
9 int sum = 0;
10 while (num) {
11 sum ++;
12 num = num&(num-1);
13 }
14 return sum;
15 }
16 };
每次“&”都会去掉num最右边的1.如果一个整数不为0,那么这个整数至少有一位是1。如果我们把这个整数减1,那么原来处在整数最右边的1就会变为0,原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。举个例子:一个二进制数1100,从右边数起第三位是处于最右边的一个1。减去1后,第三位变成0,它后面的两位0变成了1,而前面的1保持不变,因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算,从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说,把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1,就可以进行多少次这样的操作。C++,使用右移操作, -1>>1之后还是-1,也即是说负数需要特殊处理,为了解决这个问题,只需要把int型转换成unsigned int型。
1 class Solution {
2 public:
3 /**
4 * @param num: an integer
5 * @return: an integer, the number of ones in num
6 */
7 int countOnes(int num) {
8 // write your code here
9 unsigned int n = num;
10 int sum = 0;
11 while (n) {
12 sum += n&1;
13 n>>=1;
14 }
15 return sum;
16 }
17 };
原文链接: https://www.cnblogs.com/CheeseZH/p/4999835.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/225037
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!