二进制中1的个数

# 题目描述

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

# 解决方法

• bitCount(int i)

  这是 Integer 源码中的一个方法，就是返回 i 的补码中 1 的个数。

  	public static int bitCount(int i) {
  	// 每两位存储每两位值为 1 的个数。
  	i = i - ((i >>> 1) & 0x55555555);
  	// 每四位存储每四位值为 1 的个数。
  	i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  	// 每八位存储每八位值为 1 的个数。
  	i = (i + (i >>> 4)) & 0x0f0f0f0f;
  	// 每十六位存储每十六位值为 1 的个数。
  	i = i + (i >>> 8);
  	// 每三十二位存储每三十二位值为 1 的个数。
  	i = i + (i >>> 16);
  	// 由于值最大为 32，所以只关注后六位即可。
  	return i & 0x3f;
  	}

• n = n & (n-1)

  一个二进制只要不为 0，一定有一位是 1。一个二进制数减 1，如果最后一位为 1，那么最后一位变为 0，其他位不变，如果最后一位为 0，那么最后一位变为 1，其上一位如果为 0 则变 1，再上一位如果为 1 则变 0，直到遇到为 1 的位变 0，其他位不变。即二进制数减 1 就是从右到左的第一个 1 变为补码，其余位数不变。二进制与其减 1 进行与操作，就是将最右边的 1 变为 0 的结果，所以二进制可以做多少次这样的操作，就是二进制中有一个 1。

  	public int NumberOf1(int n) {
  	int count = 0;
  	while (n != 0) {
  	count++;
  	n = n & (n - 1);
  	}
  	return count;
  	}