本系列導航：劍指offer（第二版）java實現(xiàn)導航帖
面試題14：剪繩子
題目要求：
實現(xiàn)一個函數(shù)，輸入一個int型整數(shù)吁朦，輸出該數(shù)字在計算機中二進制表示形式的1的個數(shù)忍啤。例如9->1001,輸出2；-3->11111111111111111111111111111101,輸出31胎食。
解題思路：
考查位運算扰才，此題要注意負數(shù)的處理。首先要明確計算機中厕怜，數(shù)字是以補碼的形式存儲的衩匣，原碼反碼補碼不清楚的話請自己谷歌百度。其次粥航，明確位運算符琅捏，與&，或|递雀，非~柄延，異或^,<<左移位，>>帶符號右移位缀程，>>>無符號右移位(java有此符號搜吧，c++沒有)
- 解法一：將數(shù)字無符號右移，直到為0杨凑。
- 解法二：使用一個標記滤奈，初始為1，讓標記值與原輸入數(shù)字異或蠢甲，然后標記值左移僵刮。解法一是原數(shù)字右移，而解法二是標記左移鹦牛，從java來看思路類似但換了個角度搞糕；但這個思路在C++就很關鍵，因為C++中沒有>>>運算符曼追，只能用解法二窍仰。
- 解法三：沒接觸過的人應該會覺得比較新穎。對于二進制數(shù)有如下結論：【把一個整數(shù)減去1之后再和原來的整數(shù)做位與運算礼殊，得到的結果相當于把原整數(shù)的二進制表示形式的最右邊的1變成0】驹吮。比如1001，執(zhí)行一次上述結論晶伦，1001&1000=1000碟狞，將最右邊的1改為了0；再執(zhí)行一次婚陪，1000&0111=0000族沃，第二個1也改成了0。因此能執(zhí)行幾次該結論，就有幾個1脆淹。對于解法一二常空，都需要循環(huán)32次，判斷每一個比特位是否為1盖溺，而解法三漓糙，循環(huán)次數(shù)等于比特位為1的個數(shù)。時間上是有改進的烘嘱。
package chapter2;
/**
* Created by ryder on 2017/7/6.
* 二進制中的1的個數(shù)
*/
public class P100_NumberOf1InBinary {
public static int numberOfOne1(int n){
int count=0;
while(n!=0){
if((n&1)!=0)
count++;
n>>>=1;
}
return count;
}
public static int numberOfOne2(int n){
int count=0;
int flag=1;
while(flag!=0){
if((n&flag)!=0)
count++;
flag<<=1;
}
return count;
}
public static int numberOfOne3(int n){
int count=0;
while(n!=0){
n = n&(n-1);
count++;
}
return count;
}
public static void main(String[] args){
System.out.println(numberOfOne1(3));
System.out.println(numberOfOne1(-3));
System.out.println(numberOfOne2(3));
System.out.println(numberOfOne2(-3));
System.out.println(numberOfOne3(3));
System.out.println(numberOfOne3(-3));
}
}
運行結果
2
31
2
31
2
31
其他相關
- 使用一條語句判斷一個正整數(shù)是不是2的整數(shù)次方
public static boolean isPowerOfTwo(int n){
return (n&(n-1))==0;
}
- 輸入兩個整數(shù)m昆禽，n，計算最少需要改變m的多少位才能得到n
先對m蝇庭，n進行異或为狸，再統(tǒng)計異或結果中1的位數(shù)
