程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

数学专栏课外加餐(二) | 位操作的三个应用实例

黄申 2018-12-26
你好,我是黄申。欢迎来到第二次课外加餐时间。

位操作的应用实例

留言里很多同学对位操作比较感兴趣,我这里通过计算机中的位操作的几个应用,来帮你理解位操作。

1. 验证奇偶数

第 2 节里,我提到了,奇偶数其实也是余数的应用。编程中,我们也可以用位运算来判断奇偶数。
仔细观察,你会发现偶数的二进制最后一位总是 0,而奇数的二进制最后一位总是 1,因此对于给定的某个数字,我们可以把它的二进制和数字 1 的二进制进行按位“与”的操作,取得这个数字的二进制最后一位,然后再进行判断。
我这里写了一段代码,比较了使用位运算和模运算的效率,我统计了进行 1 亿次奇偶数判断,使用这两种方法各花了多少毫秒。如果在你的机器上两者花费的时间差不多,你可以尝试增加统计的次数。在我的机器上测试下来,同样次数的奇偶判断,使用位运算的方法耗时明显更低。
public class Lesson1_append1 {
public static void main(String[] args) {
int even_cnt = 0, odd_cnt = 0;
long start = 0, end = 0;
start = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
if((i & 1) == 0){
even_cnt ++;
}else{
odd_cnt ++;
}
}
end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println(even_cnt + " " + odd_cnt);
even_cnt = 0;
odd_cnt = 0;
start = 0;
end = 0;
start = System.currentTimeMillis();
for (int i = 0; i < 100000000; i++) {
if((i % 2) == 0){
even_cnt ++;
}else{
odd_cnt ++;
}
}
end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println(even_cnt + " " + odd_cnt);
}
}

2. 交换两个数字

你应该知道,要想在计算机中交换两个变量的值,通常都需要一个中间变量,来临时存放被交换的值。不过,利用异或的特性,我们就可以避免这个中间变量。具体的代码如下:
x = (x ^ y);
y = x ^ y;
x = x ^ y;
把第一步代入第二步中, 可以得到:
y = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x
把第一步和第二步的结果代入第三步中,可以得到:
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(56)

  • Jerry银银
    我的天,昨天才为老师的加餐点过赞,今天又来一篇干货。谢谢老师,看了这两篇加餐,心里的很多疑惑被解除了。买老师的专栏,值了。

    ——
    思考题:

    需要考虑不同的数量级,分两种情况:
    1. 内存能容纳这n个数

    方法1:暴力查找,两层循环遍历,时间复杂度为O(n^2),空间复杂度为O(1)

    方法2:用快排先进行排序,然后遍历一次,比较前一个数和后一个数,若相等,则查找完成,时间复杂度O(nlogn),空间复杂度为O(1)

    方法3:利用hash表(或set),进行一次遍历,同时将遍历到的数放入hash表,放入之前判断hash表是否存在,若存在,则找到了重复的数,时间复杂度为O(n),空间复杂度为O(n)

    方法4:使用位向量,遍历给到的n个数,对于出现的数,将对应位标记为1,如果已经是1则查找成功,时间复杂度为O(n),空间复杂度为(n),这种方法类似方法3,虽然渐进的空间复杂度和方法3相同,但是其实小很多很多,毕竟只要用1bit就能表示有或无


    2. 内存无法容纳给到的n个数

    依然可以用上述方法4来解决,其它的方法有的不能用,有的效率不高。

    作者回复: 感谢支持,思考题分析的很透彻,各种情况都考虑到了

    2018-12-26
    43
  • 科哥
    根据异或的两个特点,任何两个相同的数异或的结果都为0,任何数与0异或都为这个数,因此将所有的数依次异或得到的结果就是除了两个重复数的所有数的异或结果,假设为T。而将1到n依次异或的结果为T^重复数。因此,重复数=T^T^重复数。即:所有数异或的结果再异或1到n所有数异或的结果

    作者回复: 很好的思路👍

    2018-12-26
    27
  • 胡鹏
    看到 Brian Wang 的回答, 您说了正解, 我才想明白:
      推到应该是:
      原始数据: 1,2...m,m,...n (是否有序对此题不重要)
      所有数字: 1,2,...m,...n
    因为 x^x = 0
    令a = 1^2...^m...^n
       b = 1^2...^m^m...^n
    则有: a^b = (1^2...^m...^n)^(1^2...^m...^n)^m = 0^m = m

    作者回复: 是的 👍

    2018-12-30
    18
  • 李嘉鹏
    看了大家留言,1-n必须是连续以1递增才有简化解的吧。从原题并未审出这一点。
    2018-12-28
    9
  • Brian Wang
    思考题:对于有的全部数字进行异或再和 1-n 这 n 个数字进行异或,最终得出的结果就是 m

    作者回复: 正解

    2018-12-26
    8
  • mickey
    /**
     在1到n的数字中,有且只有唯一的一个数字m重复出现了,其它的数字都只出现一次。
    请把这个数字找出来。
    提示:可以充分利用异或的两个特性。
      */
    public class LessonE02_2 {
    public static void main(String[] args) {
    int[] arr = { 6, 3, 9, 5, 4, 8, 2, 5, 7, 1 };

    int temp = arr[0];
    int max = 0;
    for (int i = 1; i < arr.length; i++) {
    temp ^= arr[i];
    max = max < arr[i] ? arr[i] : max;
    }
    int t = 1;
    for (int i = 2; i <= max; i++) {
    t ^= i;
    }
    System.out.println(t ^ temp);
    }
    }

    题目不够严谨,m 重复偶数次才能用位运算吧。
    2018-12-26
    7
  • 樊少皇
    思考题:
    public static int getSpecialNum(int[] oArr, int n){
    int result = 0;
    for(int i = 0; i < oArr.length; i++){
    result = (result^oArr[i]);
    }
    for(int j = 1; j <= n; j++){
    result = result^j;
    }
    return result;
    }

    最开始不太理解。后来明白题意应该是说总共有n+1或者更多个数字,这些数字都在1--n内,并且除数字m外,其余的数字有且只有一个。举例:{1,2,3,4,5,5,6,7}满足条件;{1,2,3,5,5,5,6,7}不满足条件。
    2018-12-26
    5
  • 指间砂的宿命
    将所有结果异或再和1到n的不重复结果异或,最后剩余的值就是重复值,真的好神奇,这种异或用法

    作者回复: 嗯 异或的妙用

    2018-12-26
    5
  • 蜉蝣
    如果给出的数字不连续,Python中不妨这样使用:
    ```python
    from itertools import chain

    nums_list = [1, 2, 10, 8, 2, 3]
    nums_set = set(nums_list)

    start = 0 # 任何数与 0 异或得到自己,所以作为初始值使用
    for num in chain(nums_list, nums_set):
        start = start ^ num
        
    print(start)
    ```

    作者回复: 正确

    2019-01-08
    3
  • 夏飞
    假设我们有两个集合{1, 3, 8}和{4, 8}。我们先把这两个集合转为两个 8 位的二进制数,从右往左以 1 到 8 依次来编号。

    如果某个数字在集合中,相应的位置 1,否则置 0。那么第一个集合就可以转换为 10000101,第二个集合可以转换为 10001000。


    怎么转的?没看懂

    作者回复: 10000101最高位(第8位)的1表示集合中的8,第3位的1表示集合中的3,最低位的1表示集合中的1,以此类推。然后两个集合的交集就专为两个二进制数的按位与

    2018-12-26
    3
  • anil
    请教老师,用异或交换两个变量值感觉不太懂:
    第一步代入第二步时,y已经=x了,
    再把第二步代入第三步,此时y的值已经是x,怎么还能利用它把原y值传给x呢?
    感觉还是要临时变量做过渡啊?

    作者回复: 因为此时新的x值还是x^y,而新y已经是原来的x,两种异或,就是y了

    2018-12-26
    2
  • 风轨
    不等关系是“最没用”的关系,没有传递性,更没有序性。
    如果没有额外空间,直接暴力比较,时间复杂度O(n平方); 如果这n个数字本身是有序的,需要时间复杂度O(n),排序时间复杂度O(nlog(n))。
    如果额外空间充足,在数据聚集度较高甚至连续时,可以使用桶,时间复杂度O(n);如果数据很分散,数据范围远远大于数据量,可以考虑用桶加hash,时间复杂度O(n),但需要考虑hash碰撞问题。

    作者回复: 很好的总结!

    2018-12-26
    2
  • I keep my ideals💤
    不太明白,1到n不就是所有数吗,所有数异或所有数不就是0了吗😔😔😔

    作者回复: 原题可能没有说清楚,非重复的数字只异或一次,所以为0,而重复的数字会异或两次,成为最后的结果。

    2019-06-28
    1
  • bnhjk76
    集合{1,3,8}最大的数是8所以用8位数?那如果最大的数是999999999...那这个2进制的位数会很大,这个时候也用这个方法进行运算吗?

    作者回复: 可以把大的数切分为不同的组,例如第一个32位二进制表示前32个元素,第二个二进制表示第33到第64的元素

    2019-01-04
    1
  • 梦开始的地方
    对于有的全部数字进行异或再和 1-n 这 n 个数字进行异或,最终得出的结果就是 m
    老师,我对于两全部数字异或,在和1-n异或,就能得出m不太懂
    2018-12-27
    1
  • 拉欧
    集合中的数字和1到n的数字组成的2n+1个数,只有m出现了3次,其他的数是2次,全部亦或一遍之后就剩下了m

    作者回复: 正解

    2018-12-26
    1
    1
  • Brian Wang
    思考题:把所有的数字进行异或,结果就是要的答案
    2018-12-26
    1
  • Eleven
    老师,判断奇偶数这步操作不是看的很懂,思路不是按位与之后取最后一位么if((i & 1) == 0),这个操作不对吧?

    作者回复: 因为只要看最后一位,所以&1是获取最后一位,然后根据这位来判断奇偶,由于二进制,所以0表示偶数,1表示奇数

    2019-11-12
    1
  • Paul Shan
    异或交换律和结合律成立
    2019-08-20
  • Paul Shan
    思考题
    取n位二进制数,初始为0,和每个数对应位为1的二进制数异或,最后的结果有一位为0,其他位为1,取出补码对应的二进制数就是对应的位数。
    2019-08-20
收起评论
56
返回
顶部