Number of 1 Bits

描述

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer 11 has binary representation 00000000000000000000000000001011, so the function should return 3.

分析

最直接的方法，做32次右移，统计出1的个数。

第二个方法，来自 "Hacker's Delight" 这本书。

使用Java解题时，需要注意：

  • 输入值n可能为负数，但应视其为无符号整数，因为Java中实际上是没有无符号整数的
  • 使用无符号右移操作符>>>，可以忽略符号位

    解法1

  1. // Number of 1 Bits
  2. // Time Complexity: O(32), Space Complexity: O(1)
  3. public class Solution {
  4.     // you need to treat n as an unsigned value
  5.     public int hammingWeight(int n) {
  6.         int count = 0;
  7.         for (int i = 0; i < 32; ++i) {
  8.             count += n & 1;
  9.             n >>>= 1;
  10.         }
  11.         return count;
  12.     }
  13. }

解法2

  1. // Number of 1 Bits
  2. // Time Complexity: O(number of 1), Space Complexity: O(1)
  3. public class Solution {
  4.     // you need to treat n as an unsigned value
  5.     public int hammingWeight(int n) {
  6.         int count = 0;
  7.         while (n != 0) {
  8.             ++count;
  9.             n &= n - 1;
  10.         }
  11.         return count;
  12.     }
  13. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/bitwise-operations/number-of-1-bits.html