劍指Offer(牛客網)-二進制中1的個數

題目來源：

https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11164&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

題目描述：

輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。

解題思路：

1.  思路一(正常思路)：整數n與1進行按位與，并進行移位操作來判斷；因為存在負數情況，負數n右移最高位補1，是以可采用1與n的每位進行位與，1自身進行左移運算，來判斷1的個數。
2. 思路二(巧妙思路)：n = n & (n - 1)進行計算，将n與n-1按位與會把n的最右邊的1去掉。舉例 1100&1011 = 1000 1100最右邊的1去掉變成了1000。 原理：如果一個整數不為0，那麼這個整數至少有一位是1。如果我們把這個整數減1，那麼原來處在整數最右邊的1就會變為0，原來在1後面的所有的0都會變成1(如果最右邊的1後面還有0的話)。其餘所有位将不會受到影響。 也就是說，把一個整數減去1，再和原整數做與運算，會把該整數最右邊一個1變成0。那麼一個整數的二進制有多少個1，就可以進行多少次這樣的操作。

代碼如下：

//思路一：
public class Solution {
	public int NumberOf1(int n) {
		int count = 0;
		int tag = 1;
		while (tag != 0) {
			if ((n & tag) != 0) {
				count++;
			}
			tag = tag << 1;
		}
		return count;
	}
}

//思路二
public class Solution {
	public int NumberOf1(int n) {
		int count = 0;
		while (n != 0) {
			count++;
			n = n & (n - 1);
		}
		return count;
	}
}