輸入一個整數，輸出該數 32 位二進制表示中 1 的個數，其中負數用補碼表示
要解決這道題，必須清楚以下幾個知識點：
- 對于位運算子 &，,當兩個位同時為 1 時結果為 1,否則為 0
- >> 代表有符號右移，>>> 代表無符號右移，<< 代表無符號左移
錯誤的解法
從 n 的二進制形式的最右邊開始判斷是不是 1，但如果輸入的是一個負數，則會陷入死回圈，因為負數右移的話，最高位補的是 1，而本題的最終目的是求 1 的個數，結果就是會有無數個 1
public class Solution {
// 可能陷入死回圈的解法
public static int NumberOf1_CanNotUse(int n) {
int count = 0;
while (n != 0) {
if ((n & 1) == 1) {
count++;
}
//把n的2進制形式往右推一位
n = n >> 1;
}
return count;
}
}
解法一
用 1 和 n 的每位進行來判斷，然后 1 自身再做一次左移
public class Solution {
public int NumberOf1(int n) {
int count = 0;
int flag = 1;
while(flag != 0) {
if((n & flag) != 0) {
count++;
}
flag = flag << 1;
}
return count;
}
}
解法二
分析以下代碼，如果一個整數不為 0，那么這個整數至少有一位是 1，如果我們把這個整數減 1，那么原來處在整數最右邊的 1 就會變為 0，原來在 1 后面的所有的 0 都會變成 1（如果最右邊的 1 后面還有 0 的話），其余所有位將不會受到影響，
舉個例子：一個二進制數 1100，從右邊數起第三位是處于最右邊的一個 1，減去 1 后，第三位變成 0，它后面的兩位 0 變成了 1，而前面的 1 保持不變，因此得到的結果是 1011，我們發現減 1 的結果是把最右邊的一個 1 開始的所有位都取反了，這個時候如果我們再把原來的整數和減去 1 之后的結果做與運算，從原來整數最右邊一個 1 那一位開始所有位都會變成 0，如 1100 & 1011 = 1000，也就是說，把一個整數減去 1，再和原整數做與運算，會把該整數最右邊一個 1 變成 0，那么一個整數的二進制有多少個 1，就可以進行多少次這樣的操作，
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0) {
count++;
n = n & (n - 1);
}
return count;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/132242.html
標籤：其他