ARTS是
由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS），至少坚持一年。
ARTS 009
这是第9篇
Algorihm 算法题
leetcode算法第338题.Counting Bits: 难度：中等
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
Follow up:
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
解题过程：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 2 | 3 |
如果 i 刚好是2的n次方，那么i的二进制只有一个1。 如果 i 不正好是2的n次方，该怎么算呢？可以把拆成 2^n + m， 2^n < i 且2^n+1 > i，比如13拆为 2^3 + 5,13的二进制数据包含1的个数等于1加 5的二进制数据包含1的个数。 可以看到我们可以利用已知的数据求出未知的数据，这里实现的关键是怎么求出n，也就是以2为底的对数运算。实现如下,运行时间是20ms:
int* countBits(int num, int* returnSize) {
int* nums = (int*)malloc(sizeof(int) * (num + 1));
nums[0] = 0;
if (num >0) {
nums[1] = 1;
for (int i = 2; i <=num; i++) {
double log2Dou = log2((double)i);
int log2int = log2Dou;
int remainder = i - pow(2, log2int);
nums[i] = nums[remainder] + 1;
}
}
*returnSize = num+1;
return nums;
}
看到一个是简短的实现,如下，运行时间是16ms
int* countBits(int num, int* returnSize)
{
int* dp = (int*)malloc(sizeof(int) * (num + 1));
for (dp[0] = 0, *returnSize = 1; *returnSize <= num; ++*returnSize)
dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1);
return dp;
}
分析一下这个实现：
这个算法的关键是要理解 dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1);
把*returnSize写成二进制就容易理解了，假设 *returnSiz等于13，
13的二进制表示是：0000 1101，0000 1101 » 1之后是，0000 0110，最后一位去掉了，高位补0；
如果最后一位是0，比如12，那么0000 1100包含的1的个数，和右移之后的数0000 0110包含1的个数是一样的。
如果最后一位是1，比如13，那么0000 1101包含的1的个数，比右移之后的数0000 0110包含1的个数 多 1个。
而右移之后数字的二进制包含1的的个数前面已经求出了。
比右移之后是相等还是多1，可以通过按位与来得出 (*returnSize & 1)，或者 *returnSize % 2也可以。
再看另外一个算法:
int* countBits(int num, int* returnSize) {
int *dp, i, nearest;
dp = (int *)malloc(sizeof(int) * (num + 1));
*returnSize = num + 1;
if (dp == NULL)
return NULL;
dp[0] = 0;
if (num >= 1)
dp[1] = 1;
i = nearest = 2;
while (i <= num)
{
nearest = (i & (i - 1)) == 0 ? i : nearest;
dp[i] = 1 + dp[i - nearest];
i++;
}
return dp;
}
这个算法的关键是
while (i <= num)
{
nearest = (i & (i - 1)) == 0 ? i : nearest;
dp[i] = 1 + dp[i - nearest];
i++;
}
理解了 ` nearest = (i & (i - 1)) == 0 ? i : nearest;`，也就理解了这个算法了， i是什么值得情况下 (i & (i - 1)) == 0 会成立，只有i 正好等2^n的时候才会成立，所以这个算法的思想和我的实现是一样的，但是他在找n的时候比较巧妙，值得学习。
还有下面这个算法，也是找n的时候比较巧妙，sign就是2^n：
int* countBits(int num, int* returnSize) { 20
int* nums=(int *)calloc(num+1,sizeof(int));
for(int i=1,sign=1;i<=num;i++){
if(i>1&&i%sign==0){
sign*=2;
}
int n=i%sign;
nums[i]=nums[n]+1;
}
*returnSize=num+1;
return nums;
}
再来分析一个算法：
int* countBits(int num, int* returnSize) { //28
int bit = 1;
*returnSize = num+1;
int *table = (int *) malloc((*returnSize)*sizeof(int));
memset(table, 0, (*returnSize)*sizeof(int));
for (int i = 1; i <= num; i++)
{
if ((1 << (bit-1)) == i)
{
table[i] = 1;
bit++;
}
else
table[i] = 1 + table[i & ~(1 << (bit-2))];
}
return table;
}
这个算法的实现思路也是拆成 2^n + m，if里面相当于在找n,else 里面再找m，
` table[i] = 1 + table[i & ~(1 « (bit-2))]; ，加号左边的 1 是最高的1，也就是 2^n ， table[i & ~(1 << (bit-2))]; 中的i & ~(1 « (bit-2)) `就是m，相当与 i - 2^n.
上面分析了很多别人的实现，可以看到基本上都是对二进制数据的操作技巧。
Review
这篇文章来自：https://blog.google/technology/developers/pushing-limits-streaming-technology/ Pushing the limits of streaming technology 挑战流媒体技术的极限
Streaming media has transformed the way we consume music and video, making it easy to instantly access your favorite content. It’s a technically complex process that has come a long way in a few short years, but the next technical frontier for streaming will be much more demanding than video. 流媒体已经改变了我们消费音乐和视频的方式，让我们可以很容易地立即获取你喜欢的内容。这是一个技术上复杂的过程，在短短几年的时间里已经取得了长足的进步，但流媒体的下一个技术前沿将比视频要求更高。
We’ve been working on Project Stream, a technical test to solve some of the biggest challenges of streaming. For this test, we’re going to push the limits with one of the most demanding applications for streaming—a blockbuster video game. 我们一直在做Project Stream，这是一个解决流媒体最大挑战的技术测试。对于这个测试，我们将通过一个最苛刻的流媒体应用程序 - 一个重磅炸弹视频游戏来突破极限。
We’ve partnered with one of the most innovative and successful video game publishers, Ubisoft, to stream their soon-to-be released Assassin’s Creed Odyssey® to your Chrome browser on a laptop or desktop. Starting on October 5, a limited number of participants will get to play the latest in this best-selling franchise at no charge for the duration of the Project Stream test. 我们与一个最创新和成功的视频游戏发行商,育碧,流他们即将发布的刺客信条奥德赛®Chrome浏览器在笔记本或桌面。从10月5日开始，有限数量的参与者将可以在项目测试期间免费玩这个最畅销系列的最新游戏。 我们与最具创新性和成功的视频游戏发行商之一Ubisoft合作，将即将发布的刺客信条Odyssey®发布到笔记本电脑或台式机上的Chrome浏览器中。 从10月5日开始，有限数量的参与者将在项目流测试期间免费玩这个最畅销的特许经营权。
The idea of streaming such graphically-rich content that requires near-instant interaction between the game controller and the graphics on the screen poses a number of challenges. When streaming TV or movies, consumers are comfortable with a few seconds of buffering at the start, but streaming high-quality games requires latency measured in milliseconds, with no graphic degradation. 流式播放如此丰富的图形内容，需要游戏控制器和屏幕上的图形进行近乎即时的交互，这种想法带来了许多挑战。当流媒体电视或电影开始时，消费者对几秒钟的缓冲还能接受，但是流式传输高质量游戏需要以毫秒为单位测量延迟，而不会出现图像质量下降。
The technology and creativity behind these AAA video games is extraordinary—from incredible detail and life-like movement of the characters’ skin, clothing, and hair, to the massive scale of the world in which the game unfolds, down to every last blade of grass. Every pixel is powered by an array of real-time rendering technology, artistry, visual effects, animation, simulation, physics and dynamics. We’re inspired by the game creators who spend years crafting these amazing worlds, adventures and experiences, and we’re building technology that we hope will support and empower that creativity. 这些AAA级电子游戏背后的技术和创造力是非凡的——从令人难以置信的细节和角色皮肤、衣服和头发的栩栩如生的运动，到游戏展开的巨大规模的世界，到每一片草叶。每个像素都由一系列实时渲染技术、艺术性、视觉效果、动画、模拟、物理和动力学支持。我们受到了游戏开发者的启发，他们花了数年时间来创造这些令人惊叹的世界、冒险和体验，我们正在开发一种技术，我们希望它能支持并赋予这种创造力。
There are limited spaces available for Project Stream, but if you’re interested in participating, you can apply on our website. Project Stream is geared toward home internet connections capable of 25 megabits per second, and you must be 17 years or older and live in the U.S. to participate (other requirements can be found on the help center).
Project Stream的可用空间有限，但如果您有兴趣参与，可以在我们的网站上申请。 Project Stream适用于每秒25兆比特的家庭互联网连接，你必须年满17岁并居住在美国才能参与(其他要求可以在帮助中心找到)。
We’re looking forward to what the future of streaming holds, and feedback from those participating in Project Stream. Thank you for helping us bring streaming to the next level. 我们期待着流媒体的未来，以及那些参与Project Stream的人的反馈。 感谢您帮助我们将流媒体提升到新的水平。
Ubisoft and Assassin’s Creed Odyssey are trademarks of Ubisoft Entertainment in the U.S. and/or other countries.
POSTED IN: DEVELOPERS
TIPS:
怎么实现如下这样的线性动画
可以用CAShapeLayer + UIBezierPath实现，这里的难点在于怎么确定CGPath，简单的可以自己慢慢调，对于复杂的动画可以自动生成代码，
大致思路如下 1 让设计师将Sketch绘制的图形以SVG格式导出 2 将SVG文件拖到PaintCode，PaintCode这个软件就会自动生成OC的路径代码 3 有了这个路径代码我们就可以绘制出这个图形 4 然后用CABasicAnimation加上动画即可
Share:
最近在看深入理解计算机系统 第三版，刚看到了第一章，第一章讲了很多C语言的知识，能看看出书的作者真的很用心，每个知识点都会有相应的习题帮助你理解对应的知识点，但是知识密度确实大，只能慢慢啃。
作为一个iOS开发者为什么要读深入理解计算机系统呢？其实很多iOS开发的工作都是画UI，写业务。常用的方法都是苹果封装好的，但是你想深入优化你的APP的时候就会发现，计算机基础的知识是必须要掌握的，比如怎么获取崩溃信息，怎么加快APP启动速度，怎么实现日志系统，这么这些都需要有扎实的计算机基础才能去做。
