关于二进制数
求二进制数1的个数：
知识点：在计算机中所有数据都是二进制类型的，所以不用特意的去转换。
n & (n - 1)，会把该整数n最右边一个1变成0。
/*
一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，
而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。
这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。
如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.
那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
*/
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的话)。其余所有位将不会受到影响。
关于数值的幂次运算
有符号左移（<<）向左移动n位，就相当于乘以2^n。
带符号右移（>>）如果该数为正，则高位补0，若为负数，则高位补1。右移一位相当于除2，右移n位相当于除以2的n次方。
不带符号右移>>>表示不带符号向右移动二进制数，移动后前面统统补0。
如 -12 的二进制为：1111 1111 1111 1111 1111 1111 1111 0100；
-12 >> 3 即带符号右移3位，结果是：1111 1111 1111 1111 1111 1111 1111 1110，十进制为： -2；
-12 >>> 3 就是右移三位，前面补零，为：0001 1111 1111 1111 1111 1111 1111 1110，十进制为：536870910。
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
(快速幂运算)
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;//当指数为1时前面的结果在乘以这个curr
curr*=curr;// 每一次循环底数自己相乘，翻倍 a,a^2,a^4,a^8,a^16.....
exponent>>=1;// 右移一位
}
return n>=0?res:(1/res);
}
思路：
- 1.全面考察指数的正负、底数是否为零等情况。
- 2.写出指数的二进制表达，例如13表达为二进制1101。
- 3.举例:10^1101 = (10^0001)* (10^0100) *(10^1000)。
-
4.通过&1和>>1来逐位读取1101，为1时将该位代表的乘数累乘到最终结果。
图片.png
补充：
int mid = (x+y)>>1；相当于（x+y）/2
写一个函数，求两个整数之和。
要求在函数体内不得使用+、-、*、/四则运算符号。
例：求a+b。
思路：异或^是无进位加法，与&操作获得进位。
a^b是当a+b计算时没有进位情况下的结果
我们先来观察下位运算中的两数加法，其实来来回回就只有下面这四种：
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0（进位 1）
就是相同位为 0，不同位为 1 的异或运算结果
异或和与运算操作
在位运算操作中，异或的一个重要特性是无进位加法。
a = 5 = 0101
b = 4 = 0100
a ^ b 如下：
0 1 0 1
0 1 0 0
----------
0 0 0 1
a ^ b 得到了一个无进位加法结果，如果要得到 a + b 的最终值，我们还要找到进位的数，把这二者相加。
在位运算中，我们可以使用与操作获得进位：
a = 5 = 0101
b = 4 = 0100
a & b 如下：
0 1 0 1
0 1 0 0
-------
0 1 0 0
由计算结果可见，0100 并不是我们想要的进位，1 + 1 所获得的进位应该要放置在它的更高位，即左侧位上，因此我们还要把 0100左移一位，才是我们所要的进位结果。
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;
}
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
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;
}
解释：
概念：位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。
链接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。
依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。
