Daily C/C++ 位运算的妙用 这个文章的思路来自于今天的每日一题 题目链接 虽然是有点脑筋急转弯的题目，不过看到这样巧妙的利用位运算我还是想来分享一下这个做法 题目大意就是数组中只有两个元素的个数是1，其他元素的个数都是2。也就是只有两个元素没有重复，叫我们找出这两个元素 这个是之前题的进阶版，如果只有一个元素没有重复，那我们可以把整个数组异或一遍，重复的元素就会相互抵消，最终就剩下了答案 对于这个题来说，我们都异或一遍以后，得到的是 x = x1 \oplus x2 那我们如何充分利用这里的信息呢 对于这…
Daily C/C++ 更简单的加法模拟 本题来自leetcode链接 原始的思路就是一位一位的模拟加法器的运算 这样我们从最低位开始，每次维护进位的信息。循环32次即可 这里有一个更巧妙的实现方法，有点并行的那个感觉 先贴代码 unsigned int res = a; unsigned int nxt = b; while (nxt) { unsigned int tmp = (res & nxt) << 1; res ^= nxt; nxt = tmp; } 首先是对于这种位运算我们先转化…
Daily C/C++ 利用值域节省空间 这个文章内容会比较少，是我在做leetcode题中遇到的 但是无论如何也是新学习到的东西，所以这里简单记录一下 题目链接 就是一个数组，叫我们找出其中任意一个重复的数 如果值域较大的话，我们可以用哈希表来解决 这道题有个特殊的点就是他的值域是小于给出数组大小的，这也启发了我们可以进行原地修改来帮我们记录信息 这里的技巧就是，对于当前扫描到的数x，我们去找数组中对应下标的位置nums[x]，如果nums[x]是正数，那么我们将它变成负数，否则我们就找到了一个重复的数 这里重点…
Daily C/C++ 利用mutex实现简单的读写锁 之前我们有说过条件变量相关的东西，他可以帮助我们控制线程的执行 今天这里，我们就说一种简单的利用mutex和条件变量实现读写锁的方法 这里的实现其实就是CMU15445的bustub中的实现，如果有兴趣的同学可以自己去看相关的代码 首先我们要明确，我们希望实现的读写锁的性质。比如他是按照队列一个一个分配的吗？他是读者优先还是写者优先？ 这里，我们要实现的读写锁是写者优先，即如果当前有写者在等待，那么新到来的读者也会被阻塞。 如果当前有写者的时候，我们又来一个写…
Daily C/C++ condition_variable 之前有说要出一个条件变量的讲解 说到头我还是感觉cppreference讲的好，这里就总结一下 参考文章 条件变量也是一种用于同步的对象，他能够阻塞多个线程，直到另一个线程修改了共享变量并通知条件变量 这是啥意思呢，我们先来一个例子 #include <iostream> #include <string> #include <thread> #include <mutex> #include <co…
Daily C/C++ 弹性数组 参考文章 之前在写CMU15445的lab的时候遇到的，弹性数组指的是结构体中，长度为0的数组 举个例子 struct foo { int a; char b[0]; //或者写成 char b[]; } 当我们分配了一块内存给这个结构体的时候，b的长度就会随着我们分配内存大小的改变而改变 比如我们分配了一个128字节的内存给这个结构体，那么前四个字节就会映射到a中，而后面的124个字节就会映射到b中，此时b就是一个长度为124的数组 这样我们就可以通过灵活改变分配给foo的内存来…
Daily C/C++ 并发编程基础 今天这篇文章是简要的介绍一下并发编程中的用于控制同步的对象 参考文章是CMU15445的project4中andy推荐的一篇文章 锁 锁是一个抽象的概念，用来保护资源的，当你持有锁的时候，你就可以去访问受保护的资源。当你没有持有锁的时候，你就不能去访问对应的资源 锁本身的含义也隐喻了独占的意味。当你尝试去获取一个锁，却失败的时候，要么你会阻塞住，一直等到你可以获得这个锁为止。要么你会返回一些错误码等东西来表示获取失败 最常见的一种就是简单的计数，一个锁可以有一个上限的值。当我们…
Daily C/C++ 变参列表### Daily C/C++ 变参列表 昨天我发了一篇文章，里面有些许的涉及到了变参列表这个东西，今天就在这里好好说一下 参考文章 我们首先看printf，这个应该是我们平常用到的最多的函数之一了 /* Write formatted output to stdout from the format string FORMAT. */ /* VARARGS1 */ int __printf (const char *format, ...) { va_list arg; int d…
printf中的一个小问题 今天的问题由这样一段小的代码引入 int main() { short x = -1; printf("%u", x); return 0; } 直觉上来说，这段代码的输出应该是65535，因为65535是双字节无符号数所能表达的最大的值。 正常来说，我们输出负数使用的是%d，这里虽然我们使用了%u，但是他的输出结果并不是我们想象的65535，而是4294967295。这是四字节的数所能表示的最大值。 但是为什么是这样的呢？按照我曾经的理解，printf不过是用一个指针逐步解析我们的参数…
ARTS打卡 第十九周 这周算法题目是这个 树上的前缀和，是十分不错的题目，推荐一下想练习前缀和的同学做 本周的文章推荐这个 讲的是有关并发编程的一些知识点 上周的打卡我给鸽掉了，这周的内容也比较少。因为最近在做CMU的15445。不过好消息是现在已经做完了。所以下周将开始恢复文章的更新 下周见