關(guān)于二進(jìn)制數(shù)
求二進(jìn)制數(shù)1的個(gè)數(shù)：
知識(shí)點(diǎn)：在計(jì)算機(jī)中所有數(shù)據(jù)都是二進(jìn)制類型的，所以不用特意的去轉(zhuǎn)換。
n & (n - 1)，會(huì)把該整數(shù)n最右邊一個(gè)1變成0。
/*
一個(gè)二進(jìn)制數(shù)1100，從右邊數(shù)起第三位是處于最右邊的一個(gè)1。減去1后，第三位變成0，它后面的兩位0變成了1，
而前面的1保持不變，因此得到的結(jié)果是1011.我們發(fā)現(xiàn)減1的結(jié)果是把最右邊的一個(gè)1開始的所有位都取反了。
這個(gè)時(shí)候如果我們?cè)侔言瓉淼恼麛?shù)和減去1之后的結(jié)果做與運(yùn)算，從原來整數(shù)最右邊一個(gè)1那一位開始所有位都會(huì)變成0。
如1100&1011=1000.也就是說，把一個(gè)整數(shù)減去1，再和原整數(shù)做與運(yùn)算，會(huì)把該整數(shù)最右邊一個(gè)1變成0.
那么一個(gè)整數(shù)的二進(jìn)制有多少個(gè)1，就可以進(jìn)行多少次這樣的操作。
*/
public int NumberOf1(int n) {
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);
}
return count;
}
如果一個(gè)整數(shù)不為0，那么這個(gè)整數(shù)至少有一位是1。如果我們把這個(gè)整數(shù)減1，那么原來處在整數(shù)最右邊的1就會(huì)變?yōu)?，原來在1后面的所有的0都會(huì)變成1(如果最右邊的1后面還有0的話)。其余所有位將不會(huì)受到影響。
關(guān)于數(shù)值的冪次運(yùn)算
有符號(hào)左移（<<）向左移動(dòng)n位，就相當(dāng)于乘以2^n。
帶符號(hào)右移（>>）如果該數(shù)為正，則高位補(bǔ)0，若為負(fù)數(shù)，則高位補(bǔ)1。右移一位相當(dāng)于除2，右移n位相當(dāng)于除以2的n次方。
不帶符號(hào)右移>>>表示不帶符號(hào)向右移動(dòng)二進(jìn)制數(shù)，移動(dòng)后前面統(tǒng)統(tǒng)補(bǔ)0。
如 -12 的二進(jìn)制為：1111 1111 1111 1111 1111 1111 1111 0100；
-12 >> 3 即帶符號(hào)右移3位，結(jié)果是：1111 1111 1111 1111 1111 1111 1111 1110，十進(jìn)制為： -2；
-12 >>> 3 就是右移三位，前面補(bǔ)零，為：0001 1111 1111 1111 1111 1111 1111 1110，十進(jìn)制為：536870910。
給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。
(快速冪運(yùn)算)
public double Power1(double base, int n) {
double res = 1,curr = base;
int exponent;
if(n>0){
exponent = n;
}else if(n<0){
if(base==0)
throw new RuntimeException("分母不能為0");
exponent = -n;
}else{// n==0
return 1;// 0的0次方
}
while(exponent!=0){
if((exponent&1)==1)
res*=curr;//當(dāng)指數(shù)為1時(shí)前面的結(jié)果在乘以這個(gè)curr
curr*=curr;// 每一次循環(huán)底數(shù)自己相乘，翻倍 a,a^2,a^4,a^8,a^16.....
exponent>>=1;// 右移一位
}
return n>=0?res:(1/res);
}
思路：
- 1.全面考察指數(shù)的正負(fù)、底數(shù)是否為零等情況。
- 2.寫出指數(shù)的二進(jìn)制表達(dá)，例如13表達(dá)為二進(jìn)制1101。
- 3.舉例:10^1101 = (10^0001)* (10^0100) *(10^1000)。
-
4.通過&1和>>1來逐位讀取1101，為1時(shí)將該位代表的乘數(shù)累乘到最終結(jié)果。
圖片.png
補(bǔ)充：
int mid = (x+y)>>1；相當(dāng)于（x+y）/2
寫一個(gè)函數(shù)，求兩個(gè)整數(shù)之和。
要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運(yùn)算符號(hào)。
例：求a+b。
思路：異或^是無進(jìn)位加法，與&操作獲得進(jìn)位。
a^b是當(dāng)a+b計(jì)算時(shí)沒有進(jìn)位情況下的結(jié)果
我們先來觀察下位運(yùn)算中的兩數(shù)加法，其實(shí)來來回回就只有下面這四種：
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0（進(jìn)位 1）
就是相同位為 0，不同位為 1 的異或運(yùn)算結(jié)果
異或和與運(yùn)算操作
在位運(yùn)算操作中，異或的一個(gè)重要特性是無進(jìn)位加法。
a = 5 = 0101
b = 4 = 0100
a ^ b 如下：
0 1 0 1
0 1 0 0
----------
0 0 0 1
a ^ b 得到了一個(gè)無進(jìn)位加法結(jié)果，如果要得到 a + b 的最終值，我們還要找到進(jìn)位的數(shù)，把這二者相加。
在位運(yùn)算中，我們可以使用與操作獲得進(jìn)位：
a = 5 = 0101
b = 4 = 0100
a & b 如下：
0 1 0 1
0 1 0 0
-------
0 1 0 0
由計(jì)算結(jié)果可見，0100 并不是我們想要的進(jìn)位，1 + 1 所獲得的進(jìn)位應(yīng)該要放置在它的更高位，即左側(cè)位上，因此我們還要把 0100左移一位，才是我們所要的進(jìn)位結(jié)果。
public int Add(int num1,int num2) {
int a=num1^num2;
int b=num1&num2;
b=b<<1;
int count=0;
while(b!=0){
int temp=a;
a=a^b;
b=temp&b;
b=b<<1;
}
return a;
}
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。
int sum=0;
num1[0]=0;
num2[0]=0;
for(int i=0;i<array.length;i++){
sum^=array[i];
}
int index=findFirstIndexOf1(sum);
for(int i=0;i<array.length;i++){
int temp=array[i];
if((temp>>index&1)==1){
num1[0]^=array[i];
System.out.println("num1[0]="+num1[0]);
}
else{
num2[0]^=array[i];
System.out.println("num1[0]="+num2[0]);
}
}
}
public int findFirstIndexOf1(int t){
int index=0;//1000 3
while((t&1)==0&&t!=0){
t=t>>1;
index++;
}
return index;
}
解釋：
概念：位運(yùn)算中異或的性質(zhì)：兩個(gè)相同數(shù)字異或=0，一個(gè)數(shù)和0異或還是它本身。
鏈接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
當(dāng)只有一個(gè)數(shù)出現(xiàn)一次時(shí)，我們把數(shù)組中所有的數(shù)，依次異或運(yùn)算，最后剩下的就是落單的數(shù)，因?yàn)槌蓪?duì)兒出現(xiàn)的都抵消了。
依照這個(gè)思路，我們來看兩個(gè)數(shù)（我們假設(shè)是AB）出現(xiàn)一次的數(shù)組。我們首先還是先異或，剩下的數(shù)字肯定是A、B異或的結(jié)果，這個(gè)結(jié)果的二進(jìn)制中的1，表現(xiàn)的是A和B的不同的位。我們就取第一個(gè)1所在的位數(shù)，假設(shè)是第3位，接著把原數(shù)組分成兩組，分組標(biāo)準(zhǔn)是第3位是否為1。如此，相同的數(shù)肯定在一個(gè)組，因?yàn)橄嗤瑪?shù)字所有位都相同，而不同的數(shù)，肯定不在一組。然后把這兩個(gè)組按照最開始的思路，依次異或，剩余的兩個(gè)結(jié)果就是這兩個(gè)只出現(xiàn)一次的數(shù)字。
