变强日记13

主要内容

CAS原理
算法：寻找数组中只出现一次的数字

CAS的原理

什么是CAS？
CAS即（commpare and swap），是用于实现多线程同步到原子指令，它将内存中的内容与给定值进行比较，只有在相同的情况下，才将内存位置的内容修改为型的给定值，这是作为单个原子操作完成的。原子性保证新值基于最新信息计算，如果该值在同一时间被另一个线程更新，则写入将失败。Java1.5之后引入了CAS.在java.util.concurrent.atomic包下有大量的运用。
对于CAS的理解
假如现在两个线程都要去修改一个变量A值为1.那么这两个线程对于该变量的预期值都为1，假如第一个线程修改变量A的值为2，并从工作内存将变量A更新为2。对于线程线程二。此时变量A的值为2了，不再是预期值1了，那么第二个线程就会更新失败。
通俗的讲，CPU去更新一个值，但如果想更改的值不是预期的值，那么就更新失败，因为之前肯定有其它操作更改了这个值。

CAS的伪代码如下：

do{
备份旧数据
基于旧数据构造新数据
}while(!CAS(内存地址,预期的旧数据（即备份的旧数据 ）,新数据))

CAS的开销
CAS是CPU指令级的操作，是一个原子操作，所以速度是非常快的，但不代表CAS就没有开销。CAS的开销主要是cache同步带来的开销。CAS操作其实也是在自己的工作内存中进行的，这就需要确保缓存的一致性，但相比使用锁，CAS的开销是非常小的。
CAS存在的问题？
之前提到：CPU去更新一个值，但如果想更改的值不是预期的值，那么就更新失败，因为之前肯定有其它操作更改了这个值。那如果现在内存中值是预期的值，那么之前就一定没有其它操作更新过这个值吗？显然是不能保证之前没有其它操作更新过这个值，因为假如预期值为A，该内存中的值可能经历了A-B-A的变化。这也就是CAS的ABA问题。解决ABA问题，可以引入“版本号”。

除了ABA问题之外，CAS还不适合高并发的场景，如果更新失败，那么线程会不断重试更新，在线程竞争激烈的情况下，重试的过程会持续很久。线程不断尝试而导致等待被称为自旋。因此在高并发的情况下，使用锁更好。

算法：寻找数组中只出现一次的数字

首先看一道简化的：
题目：
leetcode[136]:只出现一次的数字. 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素
分析：
这种题型我们可以使用位运算来解决，使用位运算中的异或来解决，异或有个特性即偶数个相同的数字异或后为0.利用这个特性就可以很快解决该问题了。

class Solution {
    public int singleNumber(int[] nums) {
        int result=0;
        for(int num:nums){
            result^=num;
        }
        return result;
    }
}

更加难一点的题
题目：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
分析：上一道题，我们直到了如何在成对的数字中找出唯一的一个单个的数字，但是这道题，需要我们找出两个只出现一次的数字，所以，我们需要将这些数组分为两个部分，每个部分各含一个只出现一次的数字。
我们还是将所有的数字依次异或，最后得到一个结果，成对的数字异或后为0，那么结果中某一位存在1，则必然是这两个单个出现的数在这一位不同，根据这一位，将数组分为两个部分，然后，按照上一道题的方法，就可以找出，每个部分中，只出现一次的数字了。

解答：

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
 public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int xor=0;
        for (int item : array) {
            xor^=item;
        }
        int index=1;
        while ((index&xor)==0) {
            index = index << 1;
        }
        
        int resultA=0;
        int resultB=0;
        for(int i=0;i<array.length;i++) {
            if((array[i]&index)==0) {
                resultA^=array[i];
            }else {
                resultB^=array[i];
            }
        }
        num1[0]=resultA;
        num2[0]=resultB;
    }}