Count 1 in Binary

Question

  1. Count how many 1 in binary representation of a 32-bit integer.
  3. Example
  4. Given 32, return 1
  6. Given 5, return 2
  8. Given 1023, return 9
  10. Challenge
  11. If the integer is n bits with m 1 bits. Can you do it in O(m) time?

題解

題 O1 Check Power of 2 的進階版，x & (x - 1) 的含義爲去掉二進制數中1的最後一位，無論 x 是正數還是負數都成立。

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.         int count=0;
  9.         while (num) {
  10.             num &= num-1;
  11.             count++;
  12.         }
  13.         return count;
  14.     }
  15. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param num: an integer
  4.      * @return: an integer, the number of ones in num
  5.      */
  6.     public int countOnes(int num) {
  7.         int count = 0;
  8.         while (num != 0) {
  9.             num = num & (num - 1);
  10.             count++;
  11.         }
  13.         return count;
  14.     }
  15. }

源碼分析

累加計數器即可。

複雜度分析

這種算法依賴於數中1的個數，時間複雜度爲 O(m). 空間複雜度 O(1).

Reference