强推我左神好吧！B站搜左程云！！！

算法讲解002【入门】从社会实验到入门提醒

实验：

• 一开始有100个人，每个人都有100元

• 在每一轮都做如下的事情：

• 每个人可以拿1元给出自己外随机的另一个人

• 如果他是0元，可以不给

• 如果很多论之后，大家的财富平均吗？

如何定义平均？ —— 基尼系数

• 差值总和（每个人和其他人的差值，然后所有人的差值加起来） / （ 2 * 人数n * 财富总和 ）

• 当基尼系数达到 0.5 时，认为社会贫富差距非常大，分布非常不均匀

实验过程

• 先默认每个人没钱，然后走一个循环判断有没有钱，然后转换

• (int) (Math.random()*n); 0到 n-1 的随机一个

学习算法入门提醒

1. 善于，乐于折腾。勤写代码找到乐趣，只看课没有用。看懂了一定要确保自己手写正确，再继续下个内容。

2. 算法的学习节奏，不像大学，像高中。区别是一个为了应试，一个在磨练手艺，代码人就是手艺人。

3. 关于复习，尽量冲击到一定的题量再整体复习，不要频繁复习，会拉长周期，而且很多是无效的复习。
1. 到了多少题600 700 的时候再去复习

算法讲解003【入门】二进制和位运算

大纲

1. 二进制和位的概念

2. 正数怎么用二进制表达

3. 负数怎么用二进制表达

4. 打印二进制：直接定义二进制、十六进制的变量

5. 常见的位运算（!&, ^, ~, <<, >>, >>>）

6. 解释打印二进制的函数

7. 逻辑 |、&是位运算或，位运算与；||、&&是逻辑或、逻辑与，两者是有区别的

8. 相反数

9. 整数最小值的特殊性（取绝对值还是自己）

10. 为什么这么设计二进制（为了加法的实现是一样，没有条件转移），那么为啥加法逻辑如此重要呢？

11. 关于进位（自己确保自己的调用所得到的结果不会溢出，一定是自己确保的，计算机会给你做检查）

12. 位运算玩出很多很多，特别是异或运算（后面的课会详细讲述），如何用位运算实现加减乘除（后面的课会详细讲述）

具体

1. 二进制和位的概念
1. 二进制 Binary
2. 直接形式：如 0b10010 前面加上 0b 表示二进制形式 后面的10010表示数值 转换成10进制就是18
3. 当某个位置的数字满2进1 —— 左边一位+1(逢二进一)
4. 每一位对应 进制 n 的 x 次方，x为从右开始数的第几位但要 -1 ，因为最右边其实是 n的0次方 （几位数，你可以简单的认为你看到几个数字就是几位数）
5. 所以默认最右边为 n 的 0 次方，即为1，如果这位是0，则表示0，如果为1 即为1，再往左就是 n 的 1 2 3 .... x 次方
6. 无符号数： 每一位数字都拿来作 数值 位，并且没有负数
7. 有 x 位数，则可以表示 2 的 x 次方 个数字，从 0 — 2的x次方-1共有 2^x -1 个数字

2. 正数怎么用二进制表达
1. 最高位为符号位，0为 正数， 1为负数
2. 最左边以外的数字作为数值

3. 负数怎么用二进制表达
1. 两种方法
1. 第一种直接写
1. 先写出无符号整数的数值
2. 最左边加上一个符号位 1
3. 接着右边位当作数值
4. 这样最终加上符号位的就是 负数了
2. 第二种 知道负数，怎么拿到它的二进制表达（它的状态）呢？ （左神 ）
1. 先写出它的正数
2. 接着 -1
3. 按位取反 （0变1 1变 0 ）
4. 这个是二进制表达 （也就是这个数的状态）
2. 拿到负数的二进制状态（形式）（不是直接的二进制表示，这个是计算机看的，要转换成） 怎么看是 负几呢？
1. 先看最高位正负，这个就是符号了
2. 接着全部按位取反
3. 再 +1 得到的数字（包括最左边的符号位，其实就是当作无符号位） 作为 数值
4. 最后别忘了符号位的 -1
3. 负数和非负数（0到 2的x次方 -1 ）个数 相同

4. 打印二进制：直接定义二进制、十六进制的变量
1. 16进制 0x 开头
1. 二进制中的每4位合为十六进制的1位
2. 大于9的数字从 a -> 10 b -> 11 c -> 12 d -> 13 e -> 14 f -> 15 开始 分别对应表示 16就得进1了

5. 常见的位运算（!&, ^, ~, <<, >>, >>>）
1. 或运算 | 只要某一位有 1 则有 1 有1则1
2. 与运算 & 两位都得为 1 才为 1 11为1
3. 异或 ^ 两位不同 才为 1 相反为1
4. << 左移 整体数字往左移 n 位 空出来的位置拿0补补
5. >> 右移 往右移，左边拿符号位补
6. >>> 往右移，左边一律拿 0 补
7. 非负数 << i 等同于乘以2的 i 次方
8. 非负数 >> i 等同于 除以2的 i 次方

6. 解释打印二进制的函数
1. 想要看一个数字二进制表达的第 i 位是 0 还是 1呢？
1. 让这个数字 a & (1 << i)，a为这个数字，i为第几位数字，
2. 假设 有个数 num ，打印它， 就让它的每一位（从最高位开始） & (1<<i) ，第几位数字，i 就是多少，(有多少位，i 的初始值就是多少)，然后判断等于0吗？(每输出完一位，i 就得 -- )
1. 如果是 0 该位置就是 0
2. 但是不能拿来和 1 比 ，因为 & 出来的结果只有 0 和 非0 ，而不是只有 0 和 1，不要搞错了
3. 要注意 1 的 & ，如果num是 long类型，那么 得 num & (1L << 48) ，不能越位，否则溢出

7. 注意 | 、& 是 位运算或，位运算与；||、&&是逻辑或、逻辑与，两者是有区别的
1. 位运算 一定是 每个数字 都会执行的 确定它们每个的状态才执行
2. 而逻辑运算 则不一定，有穿透性（如果一个数
3. || bool t=A || B || C || D 当遇到 True 就会停止，只要是False 就会一直穿透下去
4. && bool t =A && B && C && D 当遇到 False就会停止，只要是True 就会一直穿透下去

8. 相反数
1. 任何数字 取反 ~ + 1 即得到 这个数了
2. 0的相反数是它本身
3. 但是取反是 取反不了 有符号的最小负数的

9. 整数最小值的特殊性（取绝对值还是自己）
1. int long 的最小值取相反数，绝对值 还是自己
2. 比如 4位的 -8， 32位，64位也一样的

10. 为什么这么设计二进制（为了加法的实现逻辑是一样的，没有条件转移），那么为啥加法逻辑如此重要呢？
1. 拿到负数做加法，先把负数通过它的正数转化出来
2. 然后做加法，如果有溢出位，溢出位不要了
3. 得到的结果就是正确的二进制表示的数

11. 关于进位（自己确保自己的调用所得到的结果不会溢出，一定是自己确保的，计算机会给你做检查）

12. 位运算玩出很多很多，特别是异或运算（后面的课会详细讲述），如何用位运算实现加减乘除（后面的课会详细讲述）