MENU

CS233 Lab1 Part2 Review

August 27, 2022 • Read: 557 • CS 233,Lab

前言

        这周和哥们们一起写了 CS233 的 lab,准确来说是我全程被 carry,屁都没干。这种坐牢的感觉真的非常折磨,所以就有了这篇文章。在文章的下面我会把哥们们的 blog 链接附上,又兴趣的可以去看看他们的网站(二次元浓度挺高的)。废话少说,开始复盘吧。
 


Question 1: KeyPad

extractMessage_1.png

要求:
 
        题目是让我们根据横纵坐标的输入判断甲方摁了哪个数字的键位,以及当前摁下的键位是不是有效的。此题无效的键位为左下和右下的空键位,其他键位均为有效。
 

Step1:重构
 
        首先,我们先以上帝视角重构一边对应的输入和输出
 

输入输出有效
ad0001 (1)Yes
bd0010 (2)Yes
cd0011 (3)Yes
ae0100 (4)Yes
be0101 (5)Yes
ce0110 (6)Yes
af0111 (7)Yes
bf1000 (8)Yes
cf1001 (9)Yes
ag0000 (null)No
bg0000 (0)Yes
cg0000 (null)No

 
        现在,把上面的表格转化为编程语言的“与“门。原理为:如果系统同时输入”a”和“b”,我们就可以与我们构建的表格进行比较然后得出用户按下了数字键“1”,etc。
 

Step2:valid 否
 
        判断完输出,但是摁的键位是否有效也是一个问题。这俩哥们就用了 1 行代码就解决了这个问题。首先让输入值跑一边上面的表格,得到结果后用一个大型 or 来判断是否 valid(这俩人往里面塞了 11 个 wire)。在这个 or 里面,所有的 wire 都是有效的数值(0-9),但凡有一个有效的 wire 被激活,整个 or 就会返还一个 true。如果输入的值不是有效的,判定为无效。
 

Step3:转化为 2 进制
 
        这也是我最佩服的地方,这俩哥们根据输入的数值来判断当前位的数值。
 

输入输出
00000
10001
20010
30011
40100
50101
60110
70111
81000
91001

 
        如果我输入的值是奇数,我的第一位怎么着都会是 1.如果是偶数第一位绝对是 0.确定完第一位后,来到了第二位。如果这个数字能到第二位,它肯定大于等于 2.所以他们给的条件就是只判断数值大于等于 2 的数字。如果为偶数,当前位为 1,如果是奇数或者小于 2,当前位就是 0,以此类推。我直接好家伙。
 


Question 2: extractMessage

extractMessage_1.png
extractMessage_2.png

 
要求:
 
        题目给了我们数据是如何被加密的。先把文字转化为二进制矩阵,然后如图中箭头所示,我们把原本横向的二进制表达式转为“垂直”的。其中加密后的矩阵的最上层 bit 为加密前矩阵的最后一位,加密后矩阵的第二层为加密前矩阵的倒数第二位,以此类推。题目现在要求我们反推这个过程,及给我们加密后的信息,要求我们解密这个信息。
 
Step1:“切开”矩阵
 
        通过题目给我们的信息,我们得知加密是以 8bit 为一组进行加密的。所以我们会有若干个 8X8 的矩阵。所以我们首先先把整个矩阵“切成”若干份,其中每一份的长度为 8(题目里面已经确保输入数据的长度为 8 的倍数)来还原此过程。
 
Step2:孤立单个 bit
 
        由于这个问题涉及到把数列转化为横行的问题,所以我们必须对加密后的矩阵的每一列进行循环(从上到下的循环)。但是这个二进制矩阵是理想的情景,现实很骨感,我们只能一串二进制一串的循环,binary mask 确实可能是一个解决的方法,但是要想找到一个对所有二进制通用的 mask 有点不切实际。但是!这周教的 binary shift 正好可以解决这个问题,只要是我不想要的 bit 全部挤走。管你什么 0,1 全部删掉,当然 shift 的操作是在一个复制品上完成的,毕竟我们一会还需要这些数值呢。拿第一行的二进制(11010010)举例子,假设我想要从左往右数第三个 1(第 5 位)。

        1. 先把左边的“110”部分全部去掉:11010010 << 3 = 10010000 目前我们想要的那个“1”在整个二进制的第一位
        2. 然后我把 1 后面的值也全部去掉:10010000 >> 7 = 00000001 现在我们想要的那个“1”在整个二进制的最后一位,其余 bit 均为 0。
        3. 别忘了,我们希望在保留这个 bit 的同时也希望它的位置也能保持不变。所以我们还需要再把它 shift 到他原来的位置第五位上面:00000001 << 5 = 00010000
 
Step3:拼成结果
 
        在创建完一个全新的空 array 后,我们可以把每次循环的结果放进 array 里面。由于上个步骤我们已经把不要的 bit 前部清空了,所以我们现在可以直接用 bitwise or 来达到只更新 1bit。举个例子,假设我们目前的二进制数值为“11011111”,我想把里面唯一的那个“0”替换为“1”来缓解我的强迫症。
         11011111
        | 00100000
        ------------
         11111111
 
注意我并没有改变其他位的值,我可以用这个方法来一位一位的更新结果。每一次循环我们都能解密一个字符,以此类推。听到这个方法时,我的内心是拒绝的,但是它确实很妙,完美结合了这周的 bit shift 和 bit wise operator。

 


总结

        CS 233 这课真的阴间,和以往的课,比如 CS 128,完全不一样,这可能就是底层的魅力吧。这俩哥们的博客就在文章上方的友链里,欢迎前去观摩一下!
 


哥们们的 blog

  1. 红头发老哥:https://www.captoz.me/
  2. 黄老哥:https://erdao.me/ (网站二次元浓度高的那个人)
Last Modified: October 4, 2023
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. FXF

    👍 👍 👍 👍 👍