2020年4月

先看以下C语言代码执行,猜一下运算结果

#include <stdio.h>

void inplace_swap(int *x, int *y) {
    *y = *x ^ *y; /* Step 1 */
    *x = *x ^ *y; /* Step 2 */
    *y = *x ^ *y; /* Step 3 */
}
// 注: ^符号为异或运算,异或运算符合数学运算的可交换定律,符合加法逆运算a^a=0

void reverse_array(int a[], int cnt){
    int first, last;
    for (first = 0, last = cnt-1; first <= last; first++,last--) {
        inplace_swap(&a[first], &a[last]);
    }
}

int main(int argc, const char * argv[]) {
    int nums1[4] = {1,2,3,4};
    int cnt1 = sizeof(nums1) / sizeof(nums1[0]);
    reverse_array(nums1,cnt1);
    for(int i=0; i<cnt1; i++){
        printf("%d ", nums1[i]);
    }
    printf("\n");
    
    int nums2[5] = {1,2,3,4,5};
    int cnt2 = sizeof(nums2) / sizeof(nums2[0]);
    reverse_array(nums2,cnt2);
    for(int i=0; i<cnt2; i++){
        printf("%d ", nums2[i]);
    }
    printf("\n");
    
    return 0;
}

结果:

  • 遍历nums1数组,结果为4 3 2 1
  • 遍历nums2数组,结果为5 4 0 2 1
  • 多测试几遍,发现当数字元素为偶数时,结果是数组倒序的结果;当数字元素为奇数时,它就会把中间元素置成0

问题:

  1. 对于一个长度为奇数的数组,长度cnt=2k+1,函数reverse_array最后一次循环中,变量first和last的值分别是什么?
  2. 为什么这时调用函数inplace_swap会将数组元素设置为0?
  3. 对reverse_array的代码做哪些简单改动就能消除这个问题?

思路:

先来分析inplace_swap里每一步的结果,假使指针x和y指向的位置存储值分别是a和b作为开始,则有下表1:

步骤*x*y
初始ab
第1步aa^b
第2步a^(a^b)=(a^a)^b=ba^b
第3步bb^(a^b)=(b^b)^a=a

再来看nums2的reverse_array里循环:
第一次循环:a[0]值为1,a[4]值为5,套入上面公式,inplace_swap(&a[0], &a[4]),a[0]值为5,a[4]值为1;
第二次循环:a[1]值为2,a[3]值为4,套入上面公式,inplace_swap(&a[1], &a[3]),a[1]值为4,a[2]值为2;
第三次循环:a[2]值为3,a[2]值为3,套入上面公式,inplace_swap(&a[2], &a[2]),a[2]值为0,a[3]值为0;
注意第三次循环:inplace_swap里,第1步,这时x和y都指向的是同一个位置,所以当我们计算x^y时,我们得到的是0!

答案:

  1. 长度cnt=2k+1,所以first和last的值都为k,也就是2。
  2. 因为x和y都指向的是同一个位置,所以当我们计算x^y时,我们得到的是0。
  3. 使x和y指向不同位置,也就是说,reverse_array里first <= last 改为:first < last

总结:

异或运算符合交换律:a^(a^b)=(a^a)^b
异或运算符合加法逆运算:a^a=0

  • 删除上一个字符使用抄ctrl-h
  • 删除光标到行首使用ctrl-u
  • 删除光标到行尾使用ctrl-k
  • 删除一个单词ctrl-w
  • 跳转到上一个单词使知用alt-b
  • 跳转到下一个单词使用alt-f
  • 跳转到行首使用ctrl-a
  • 跳转到行尾使用ctrl-e
  • 搜索历史命令使用ctrl-r

阻塞与非阻塞

  • 线程访问资源,该资源是否准备就绪的一种处理方式

同步与异步

  • 同步和异步是指访问数据的一种机制

BIO

  • 同步阻塞IO,Block IO
  • 举例子,去上厕所,坑全满,此时我一直光等着,主动观察哪个坑位好了,只要坑位释放了,我就立马去占坑

NIO

  • 同步非阻塞IO,New IO (Non-Block IO)
  • 厕所坑全满,此时我去厕所外面玩手机干其他事情,然后时不时得再主动去厕所看看有没有坑被释放,如果有坑了去占坑

AIO

  • 异步非阻塞IO(AIO),A上厕所排队,做别的事情的同时等待别人告诉自己哪个坑没人
  • 异步阻塞IO,上厕所排队,在厕所里等待别人告诉自己哪个坑没人