191. Number of 1 Bits

题目

题意分析

求出一个无符号二进制整数中1的个数。

本题考点

基本位运算操作。

解法I - 循环法

通过循环，每次取出最后一位，判断是否为1，每次循环右移一位，直至n == 0，求出结果。

实现

public class Solution {
  // you need to treat n as an unsigned value
  public int hammingWeight(int n) {
    int numberOf1s = 0;
    
    while (n != 0) {
      numberOf1s += n & 1;
      n >>>= 1;
    }
    
    return numberOf1s;
  }
}

解法II - 位运算

对于本题，有一个位运算的小技巧，n & (n - 1)操作，

这个操作可以将一个二级制数的最后一位清零。

我们以假设一个二级制数为a1b, 其中a为任意值，b为任意个0。

为直观展示，我们假设n = 111000110100000

则 n & (n - 1) = 111000110100000 & 111000110011111

111000110100000

&)

111000110011111

================

111000110000000

我们成功的将最后一个1清0。

也就是说，如果我们进行完n次清0操作，整个二进制数才变成0，那么说明我们原数字中有n个1。

本方法的循环次数，取决于整个二级制中有多少个1，优于循环算法中，最左边的1所在的位置。

实现

public class Solution {
  // you need to treat n as an unsigned value
  public int hammingWeight(int n) {
    int numberOf1s = 0;
    
    while (n != 0) {
      n &= (n - 1);
      numberOf1s++;
    }
    
    return numberOf1s;
  }
}