二进制中1的个数

• 参与人数：3525时间限制：1秒空间限制：32768K
• 通过比例：32.44%
• 最佳记录：0 ms|0K（来自  ）

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

1 解法1： 2 /* 3     这样，当n为负数的时候（eg: n = 0x80000000），会导致死循环。 4     因为在右移时，如果数字是一个无符号数值，则用0填补最左边的n位， 5     如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。 6     即，如果数字原先是一个正数，则右移之后在最左边补n个0； 7     如果数字原先是一个负数，则右移之后在最左边补n个1。 8     eg: 负数0x80000000右移一位后变为0xC0000000，如果一直做右移运算， 9     最终该数字会变成0xFFFFFFFF而陷入死循环。10 */11 int  NumberOf1(int n) {12     int cnt = 0;13     while (n){14         if (n & 1)15             cnt++;16         n = n >> 1;17     }18     return cnt;19 }

 

1 解法2： 2 /* 3     不用右移输入的数字n，而是将unsigned int类型的1进行左移运算， 4     然后将n和1做与运算，从右向左依次判断n的第i位是否为1。 5     但是该解法中，循环的次数等于整数二进制的位数，32位整数需要循环32次。 6 */ 7 class Solution { 8 public: 9      int  NumberOf1(int n) {10         int cnt = 0;11         unsigned int tmp = 1;12         while (tmp){13             if (n & tmp)14                 cnt++;15             tmp = tmp << 1;16         }17         return cnt;18     }19 };

 

1 解法3： 2 /*  3     把一个整数n减1，然后再与原整数n做与运算，可以将该整数最右边的1变为0。 4     即 (n-1) & n 将n的最右边的1变为0。 5     eg: n = 1100, 则n-1 = 1011， (n-1)&n = 1000. 6     因此，该解法，数字n中有多少个1，就循环多少次。 7 */ 8 class Solution { 9 public:10      int  NumberOf1(int n) {11         int cnt = 0;12         while(n){13             cnt++;14             n = (n-1) & n;15         }16         return cnt;17     }18 };