-
选择排序和冒泡排序
选择排序是O(n2)，每次选取最大的，放在最前面，然后下次从第二个开始找到最后一个。
冒泡也是O(n2)，一直交换到最后。 -
插入排序
插入排序最坏是O(n2)，最好是O(n)，但是算法一般都是按照最坏的来。插入是先排序0-1，然后0-2，然后0-3，eq.:排序0-5时，0-4已经排序好了，只需要将第五个数字插入即可，依次与4 3 2 1 判断并交换到对应位置上。
二进制加减乘除
通过位运算计算int的加减乘除:
加法原理:a+b
位的异或运算跟求'和'的结果一致：
异或 1^1=0 1^0=1 0^0=0
求和 1+1=0 1+0=1 0+0=0
位的与运算跟求'进位‘的结果一致：
位与 1&1=1 1&0=0 0&0=0
进位 1+1=1 1+0=0 0+0=0
所以a+b = (a^b)+((a&b)<<1)
减法原理:a-b
减去一个正数等于加上这个负数的补码.一个正数的补码是它的原码.一个负数的补码等于它的反码+1.即 -b = ~b+1.所以a-b = a+(-b) = a+ ~b+1.
补码的规定如下：
对正数来说，最高位为0，其余各位代表数值本身(以二进制表示)，如+42的补码为00101010。
对负数而言，把该数绝对值的补码按位取反，然后对整个数加1，即得该数的补码。如-42的补码为11010110(00101010按位取反11010101+1即11010110)
【例1】对 5 进行取反。
假设为16位。
5转换为二进制数为： 0000 0000 0000 0101得到二进制数
每一位取反： 1111 1111 1111 1010得到最终结果的补码
取补码： 1000 0000 0000 0110得到最终结果的原码
转换为十进制数：-6
则 5 取反为 -6 .
【例2】对 -5 进行取反。
假设为16位。
-5 转换为二进制数为： 1000 0000 0000 0101得到二进制数
取补码： 1111 1111 1111 1011得到二进制数的补码
每一位取反： 0000 0000 0000 0100 得到最终结果的补码
取补码： 0000 0000 0000 0100得到最终结果的原码
转换为十进制数：4
则 -5 取反为 4 .
如果用适合人类运算的计算方法：
如对 a 按位取反，则得到的结果为 -(a+1) .
此条运算方式对正数负数和零都适用。
所以（b-1）=-b可得a-b=a+（-b）=a+((b-1))。把减法转化为加法即可。
乘法原理:a*b
-
用循环加法替代乘法。a*b，就是把a累加b次。时间复杂度为O(N)。
-
在二进制数上做乘法.就是根据乘数的每一位为0或1时，将被乘数错位的加在积上。时间复杂度为O(logN)
除法原理:a/b
-
从被除数上减去除数，看能减多少次之后变得不够减。时间复杂度为O(N)。
-
采用类似二分法的思路，从除数*最大倍数开始测试，如果比被除数小，则要减去。下一回让除数的倍数减少为上一次倍数的一半，这样的直到倍数为1时，就能把被除数中所有的除数减去，并得到商。时间复杂度降低到O(logN)。
/**
* 2023年07月28日 10:57:57
* 加法
* @param a
* @param b
* @return
*/
public static int add(int a,int b) {
int res=a;
int xor=a^b;//得到原位和
int forward=(a&b)<<1;//得到进位和
if(forward!=0){//若进位和不为0，则递归求原位和+进位和
res=add(xor, forward);
}else{
res=xor;//若进位和为0，则此时原位和为所求和
}
return res;
}
/**
* 减法
* @param a
* @param b
* @return
*/
public static int minus(int a,int b) {
int B=~(b-1);
return add(a, B);
}
/**
* 乘法
* @param a
* @param b
* @return
*/
public static int multi(int a,int b){
int i=0;
int res=0;
while(b!=0){//乘数为0则结束
//处理乘数当前位
if((b&1)==1){
res+=(a<<i);
b=b>>1;
++i;//i记录当前位是第几位
}else{
b=b>>1;
++i;
}
}
return res;
}
/**
* 除法
* @param a
* @param b
* @return
*/
public static int sub(int a,int b) {
int res=-1;
if(a<b){
return 0;
}else{
res=sub(minus(a, b), b)+1;
}
return res;
}
public static void main(String[] args) {
//加法运算
int result1 = add(90,323);
System.out.println(result1);
//减法运算
int result2 = minus(413,323);
System.out.println(result2);
int result3 = multi(90,2);
System.out.println(result3);
int result4 = sub(90,2);
System.out.println(result4);
}
异或的知识点
两个数字相异为1，相同为0，引申到int对比时，是32位的数字相异，也是相异为1，相同为0。
public static void sway(int[] arr,int i,int j){
if(i!=j){
//不能两个值指向同一地址
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];//就是arr[i]^arr[j]^arr[j]就表示a
arr[i]=arr[i]^arr[j];//表示arr[i]^arr[j]^arr[i]^arr[j]^arr[j]就是b
}
}
可以理解为二进制上的不进位相加。
题目1：一组数只有一个数出现奇数次，其他出现偶数次，找出这个出现奇数次的数
public class Main {
private static int process(int[] arr) {
int res = 0;
for (int i : arr) {
res ^= i;
}
return res;
}
}
取出最右边为1的二进制位所代表的数字
int mostRightOne = pos & (~pos + 1);
// mostRightOne值在二进制位上的位次就是pos得最右第一个1的位置
题目2：有两种数出现了奇数次，另一种出现了偶数次，求出奇数次的a,b
思路：先一路异或找到a^b，然后因为a!=b，因此一定有不相同的位，那取出两者从右边数第一个不相同的位置，即先取反+1再异或 （ab）。然后将与这个结果&运算==0的数字全部异或，也就获得了其中一个奇数次的数字，a或者b。在将其与ab异或得到另一个数字。
public class Main {
private static void process(int[] arr) {
int med = 0;
for (int a : arr) {
med ^= a;// 两个不同的单数^最后得到med
}
int rightOne = med & (~med + 1);// 取出med中二进制为1的位值（必存在，因为不同值）
int med1 = 0;
for (int a : arr) {
// 对应位为1的值取出进行^最后的到两个单数对应位为1的
// (a&rightOne)== 0得到对应位为0
if ((a & rightOne) == rightOne) {
med1 ^= a;
}
}
System.out.println(med1);// 两个单数其中一个值
System.out.println(med ^ med1);// 两个单数令一个值
}
}
二分法的另类应用
当数况和方法同时满足条件时，可以用二分法做。
例如数组中相邻元素都不相等，而且要找到一个"局部最小点"，即即比左边小也比右边小的一个点。
思路：根据数学定理，中间必有导数为0的点，取M为中点，如果不是"局部最小点"，则它左侧必有，一直向左边二分即可。
标签：arr,0000,int,复杂度,补码,取反,二进制,算法,排序 From： https://www.cnblogs.com/benfang/p/17642530.html