輸入一個整數,輸出該數二進制表示中1的個數。其中負數用補碼表示。
一個整數
該數二進制表示中1的個數
解法一 運行時間:29m 占用內存:629k
public int NumberOf1(int n) {
String s=Integer.toBinaryString(n);
char[] c=s.toCharArray();
int j=0;
for(int i=0;i
解析:
public static String toBinaryString(int i)
以二進制(基數 2)無符號整數形式返回一個整數參數的字符串表示形式。
①先把整數轉換成二進制字符串
②把字符串轉換成字符數組
③遍歷該數組,判斷每位是否為1,為1 計數加1。
④遍歷完成返回1的個數
解法二 運行時間:30ms 占用內存:629k
public class Solution {
public int NumberOf1(int n) {
int count =0;
while(n!=0){
count++;
n = n&(n-1);
}
return count;
}
}
解析:
如果一個整數不為0,那麼這個整數至少有一位是1。如果我們把這個整數減1,那麼原來處在整數最右邊的1就會變為0,原來在1後面的所有的0都會變成1(如果最右邊的1後面還有0的話)。其余所有位將不會受到影響。
舉個例子:
①二進制數 1100
② 減1後,得 1011
③1100&1011=1000
對比①和③你會發現,把一個整數減去1,再和原整數做與運算,會把該整數最右邊一個1變成0.那麼一個整數的二進制有多少個1,就可以進行多少次這樣的操作。