记录一些零零碎碎的方法

记录一些不好分类的，偶然看到的知识吧

两数交换的方法

有三种

一种是用tmp存储作为过渡，然后进行交换

golang
a := 0
b := 1
tmp := a
a = b
b = tmp

优点：适合各自数据类型

缺点：需要开辟新的空间

利用 b = a+b-b a = a+b-(a+b-b)

golang
a := 0;b:= 1
a = a + b
b = a - b
a = a - b

优点：节省空间

缺点：两数和可能会越界，这个也是用到两数和可能出现的问题，而且只适用数值类型

异或操作,两个数相同异或为0

golang
a = a^b
b = a^b
a = a^b

优点：

节省空间
不会超出范围
效率高

缺点：

只适用于数值类型

理解这个方法要懂异或操作：
二进制两数运算为


0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

假设a = 10，b=12
二进制分别为 1010 1100
在二进制看来，就是交换不同的01，在这里即是中间两位
第一次 a = a ^ b = 0110,相当于找到不同的位，将不同的位置为1,存到a
第二次 b = a ^ b = 0110 ^ 1100 = 1010,就是对两个不同的数进行取反，那不同的位置已经为1，所以如果是为1的话异或就为0，如果是0的话异或就为1，相当于取反了
第三次 a ^ b = 0110 ^ 1010 = 1100 ,这一次的b就是相当于交换前的a，所以是对a中间两位数取反

位运算

按位取反

~ 0 - 1, 1- 0
按位与

& 同为1为1，其余为0
按位或

| 存在1为1，否则为0
按位异或

^ 相同为0，不同为1

主要是异或的性质，如果两个相同的数异或得0，而且异或是有交换律和结合律的,与0异或都是他本身，简单来说，异或后得到的结果中，1即为两数不同的位置，可以注意这个性质，就可以得到上面两数交换的第三种方法


eg.找出没有重复的数
存在一列数据，其中大部分数据两两配对，只有一个数据落单，请找出这个落单的数据
解释：这时候就可以利用异或的性质

public static int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i<arr.length;i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

两两相异或，最后重复的异或后得到0，0与落单的进行异或得到落单的数

还有一种时间复杂度一样，但空间复杂度为O(n)的算法，就是用哈希再存储

题目

找出不大于N的最大的2的幂指数

思路不难，如果转为二进制来看，比如000100100，那最大的就是000100000，就是把最左边的1后面的数字转为0

java
public static int findN(int n) {
    n | n >> 1;
    n | n >> 2;
    n | n >> 4;
    n | n >> 8;
    return (n + 1) >> 1;
}


假设最左边的1处于二进制中的第k位，那么把n右移一位之后，得到的结果中第k+1位也必定为1，然后
把n与右移后的结果做或运算，即有1为1，那么k和k+1位都为1，然后再位移两位，k+2和k+3必定为1，
然后再或运算，以此类推，最多将k以及k以后的都变为1
之后再将得到的最后值+1，即获得最大值的前一位为1，其余为0，那么就右移一位就得到结果

求平均值

防止爆int

(a&b) +((a^b)>>1)
(b-a)/2+a;
((b-a)>>1)+a;

讲一下第一个的原理，a = 10 = 1010,b = 12 = 1100

那么a&b = 1000 = 8,a^b = 0110 = 6,a^b >> 1 = 0011 = 3

a^b前面也说了，就是可以获得两数不同的位置，那右移一位，就是除以2求平均值

a&b是求同一个bite位上相同的平均值，即为其自身

所以就是求相同位置的平均值加上不同位置的平均值

快速幂

可以用O(log n)的时间复杂度计算乘方

递归

正常计算一个数的2的n次幂，一般是要经过n次乘法，但其实好像也可以用2^n/2 * 2^n/2来得出结
果，而2^n/2也可以推为另外两个计算
那就可以使用递归来获得结果

golang
 int qpow(int a,int n) {
    if(n == 0) return 1;
    else if(n%2==1) return qpow(a,n-1) * a;
    else {
        int tmp = qpow(a,n/2);
        return tmp * tmp;
    }
}

非递归

将幂转换为二进制的形式，即7^10,看为7^(1010),可以看成若干个7(100...)相乘，即7^1,7^2,7^4,所以将底数平方就可以计算它们.

golang
int qpow(int a,int n){
    int ans = 1;
    while(n){
        if(n&1) ans *= a;
        a *= a;
        n >> = 1;
    }
    return ans;
}

如何写出CPU跑得更快的代码

即如果能在CPU Cache命中的话，会带来较大的性能提升
L1 Cache一般分为[数据缓存]和[指令缓存]

提升数据缓存的命中率

golang
array[N][N] = 0;
// Demo1
for(int i = 0;i<N;i++){
    for(int j = 0;j<N;j++){
        array[i][j] = 0;
    }
}

// Demo2
for(int i = 0;i<N;i++){
    for(int j = 0;j<N;j++){
        array[j][i] - 0;
    }
}

两个Demo里面，数据缓存命中率高的是1，因为数组是连续线性存储在内存里的，当array[0][0]没在cacha里查到，则CPU会将array[0][0]和之后的一段一起放入Cache里面，这个就是缓存的空间局部性原理，还有一个时间局部性是这次被使用，则在之后一段时间也可能再次被使用,所以如果下次访问的刚好在前一段刚好带来Cache里面的部分，则可以直接命中，而Cache一次性加载的元素大小与Linux里的coherency_lone_size有关，通常是64个字节

提升指令缓存的命中率

golang
int array[N]
for(int i = 0;i<N;i++){
    array[i] = rand() % 100;
}

// 操作一：数组遍历
for(int i =0;i<N;i++){
    if(array[i] < 50){
        array[i] = 0;
    }
}

// 操作二：排序
sort(array,array+N);

那么先遍历再排序快还是先排序再遍历快

那先了解CPU的分支预测器,对于if语句，意味着至少可以选择跳转到两段不同的指令执行，即if还是else
，如果可以预测到接下来执行的是if还是else的话，就可以把对应的指令提前放到指令缓存里，这样CPU可以直接从Cache读取到指令。

当数组种元素随机，则分支预测就无法有效工作，当数组元素都是顺序，分支预测器会动态地根据历史名字数据对未来进行预测，这样命中率就会很高

所以先排序再遍历会快

提升多核CPU的缓存命中率

现代CPU是多核心的，线程在不同CPU核心来回切换执行，这对CPU Cache不是有利的，虽然L3 Cache是多核心之间共享，但L1，L2都是每个核心独有的.如果一个线程在不同核心之间来回切换的话，命中率就会受影响，所以当有多个同时执行[计算密集型]的线程，为了防止因为切换到不同核心，可以把线程绑定在某一个CPU核心上

LCM && gcd

java
    public static int gcd(int a,int b){
        return b != 0 ? gcd(b,a%b):a;
    }
    
    public static int lcm(int a,int b){
        return a * b / gcd(a,b);
    }

DNS查询

DNS查询其实会先经过三步，浏览器会先去查询浏览器的缓存，然后由操作系统查询一遍缓存，最后查询一遍本地hosts文件，如果没有才会请求本地DNS服务器

目录