[TOC] ## SS, SP, BP 三个寄存器 SS - 存放栈的段地址 SP - 堆栈寄存器SP(stack pointer)存放栈的偏移地址 BP - 基数指针寄存器BP(base pointer)是一个寄存器，它的用途有点特殊，是和堆栈指针SP联合使用的，作为SP校准使用的，只有在寻找堆栈里的数据和使用个别的寻址方式时候才能用到 - 如:**堆栈中压入了很多数据或者地址，你肯定想通过SP来访问这些数据或者地址，但SP是要指向栈顶的，是不能随便乱改的，这时候你就需要使用BP，把SP的值传递给BP，通过BP来寻找堆栈里数据或者地址** Win32汇编示例 ``` bp为基址寄存器，一般在函数中用来保存进入函数时的sp的栈顶基址 每次子函数调用时，系统在开始时都会保存这个两个指针并在函数结束时恢复sp和bp的值。像下面这样： 在函数进入时： push bp // 保存bp指针 mov bp,sp // 将sp指针传给bp，此时bp指向sp的基地址。 // 这个时候，如果该函数有参数，则[bp + 2*4]则是该子函数的第一个参数，[bp+3*4]则是该子函数的 第二个参数，以此类推，有多少个参数则[bp+(n-1)*4]。 ..... 函数结束时： mov sp,bp // 将原sp指针传回给sp pop bp // 恢复原bp的值。 ret // 退出子函数 ```

[TOC] ## 控制流 ### if else系列 ``` b target # unconditional branch to program label target beq $t0,$t1,target # branch to target if $t0 = $t1 blt $t0,$t1,target # branch to target if $t0 < $t1 ble $t0,$t1,target # branch to target if $t0 <= $t1 bgt $t0,$t1,target # branch to target if $t0 > $t1 bge $t0,$t1,target # branch to target if $t0 >= $t1 bne $t0,$t1,target # branch to target if $t0 <> $t1 ``` ### 跳转（while, for, goto系列） ``` j target 　　　　 # 看到就跳， 不用考虑任何条件 jr $t3 # 类似相对寻址，跳到该寄存器给出的地址处 ``` ### 子程序调用 ``` jal sub_label #将当前的程序计数器保存到 $ra 中 ``` - 如果说调用的子程序中有调用了其他子程序，如此往复， 则返回地址的标记就用 栈（stack） 来存储, 毕竟 $ra 只有一个

[TOC] ## 算术指令集 * 最多3个操作数 * 再说一遍，在这里，操作数只能是寄存器，绝对不允许出现地址 * 所有指令统一是32位 = 4 \* 8 bit = 4bytes = 1 word ``` add $t0,$t1,$t2 # $t0 = $t1 + $t2; add as signed (2's complement) integers sub $t2,$t3,$t4 # $t2 = $t3 Ð $t4 addi $t2,$t3, 5 # $t2 = $t3 + 5; "add immediate" (no sub immediate) addu $t1,$t6,$t7 # $t1 = $t6 + $t7; add as unsigned integers subu $t1,$t6,$t7 # $t1 = $t6 + $t7; subtract as unsigned integers mult $t3,$t4 # multiply 32-bit quantities in $t3 and $t4, and store 64-bit # result in special registers Lo and Hi: (Hi,Lo) = $t3 * $t4 　　　　　　　　　　　　　　　　# 运算结果存储在hi,lo（hi高位数据， lo地位数据） div $t5,$t6 # Lo = $t5 / $t6 (integer quotient) # Hi = $t5 mod $t6 (remainder) 　　　　　　　　　　　　　　　　# 商数存放在 lo, 余数存放在 hi mfhi $t0 # move quantity in special register Hi to $t0: $t0 = Hi 　　　　　　　　　　　　　　　　# 不能直接获取 hi 或 lo中的值， 需要mfhi, mflo指令传值给寄存器 mflo $t1 # move quantity in special register Lo to $t1: $t1 = Lo # used to get at result of product or quotient move $t2,$t3 # $t2 = $t3 ```

[TOC] ## 加载/保存(读取/写入) * 如果要访问内存，不好意思，你只能用**load**或者**store**指令 * 其他的只能都一律是寄存器操作 ``` //从内存中 复制 RAM_source 的内容到 对应的寄存器中（lw中的'w'意为'word',即该数据大小为4个字节） lw register_destination, RAM_source //同上， lb 意为 load byte lb register_destination, RAM_source //将指定寄存器中的数据 写入 到指定的内存中 sw register_source, RAM_destination // 同上, b 为 byte sb register_source, RAM_destination //这里的 li 意为 load immediate li register_destination, value ``` ## 立即与间接寻址 直接给地址 ``` // 将var1的内存地址复制到寄存器$t0中 la $t0, var1 ``` 地址是寄存器的内容（可以理解为指针） ``` // 将包含在$t0中的内存地址的字加载到$t2中 lw $t2, ($t0) // 将寄存器$t2中的字存储到内存中$t0中包含的地址 sw $t2, ($t0) ``` 偏移量 ``` // 将内存地址($t0+4)的字加载到寄存器$t2中 lw $t2, 4($t0) // 将寄存器$t2中的字存储到内存中的地址($t0 - 12) sw $t2, -12($t0) ``` * 要用到偏移量的寻址，基本上使用最多的场景无非两种：数组，栈 实例 ``` .data array1: .space 12 # declare 12 bytes of storage to hold array of 3 integers 　　　　　　　　　　　　　　　　　　 # 定义一个 12字节 长度的数组 array1, 容纳 3个整型 .text __start: la $t0, array1 # load base address of array into register $t0 　　　　　　　　　　　　　　　　　　# 让 $t0 = 数组首地址 li $t1, 5 # $t1 = 5 ("load immediate") sw $t1, ($t0) # first array element set to 5; indirect addressing 　　　　　　　　　　　　　　　　　　# 对于 数组第一个元素赋值 array[0] = $1 = 5 li $t1, 13 # $t1 = 13 sw $t1, 4($t0) # second array element set to 13 　　　　　　　　　　　　　　　　　　 # 对于 数组第二个元素赋值 array[1] = $1 = 13 　　　　　　　　　　　　　　　　　　 # (该数组中每个元素地址相距长度就是自身数据类型长度，即4字节， 所以对于array+4就是array[1]) li $t1, -7 # $t1 = -7 sw $t1, 8($t0) # third array element set to -7 　　　　　　　　　　　　　　　　　　# 同上， array+8 = （address[array[0])+4）+ 4 = address(array[1]) + 4 = address(array[2]) done ```

[加载/保存 指令集](%E6%8C%87%E4%BB%A4%E9%9B%86/%E5%8A%A0%E8%BD%BD-%E4%BF%9D%E5%AD%98%E6%8C%87%E4%BB%A4%E9%9B%86.md) [算术指令集](%E6%8C%87%E4%BB%A4%E9%9B%86/%E7%AE%97%E6%9C%AF%E6%8C%87%E4%BB%A4%E9%9B%86.md) [控制流 指令集](%E6%8C%87%E4%BB%A4%E9%9B%86/%E6%8E%A7%E5%88%B6%E6%B5%81.md)

[TOC] ## 数据类型 * 所有MIPS指令都是32位长的 * 各单位：1字节=8位，半字长=2个字节，1字长=4个字节 * 一个字符空间=1个字节 * 一个整型=一个字长=4个字节 * 单个字符用单引号，例如：'b' * 字符串用双引号，例如："A string" ## 寄存器 |寄存器编号 |寄存器名| 寄存器用途| |---|---|---| |0| zero| 永远返回零| |1|$at|汇编保留寄存器（不可做其他用途）| |2-3|$v0 - $v1|（Value简写）存储表达式或者是函数的返回值| |4-7|$a0 - $a3|（Argument简写）存储子程序的前4个参数，在子程序调用过程中释放| |8-15|$t0 - $t7|（Temp简写）临时变量，同上调用时不保存| |16-23|$s0 - $s7|（Saved or Static简写？）静态变量？调用时保存| |24-25|$t8 - $t9|（Temp简写）算是前面$0~$7的一个继续，属性同$t0~$t7| |26-27|$k0 - $k1|（breaK off简写？）中断函数返回值，不可做其他用途| | 28|$gp |（Global Pointer简写）指向64k(2^16)大小的静态数据块的中间地址（字面上好像就是这个意思，块的中间）| | 29|$sp |(Stack Pointer简写）栈指针，指向的是栈顶| | 30| $s8/$fp |(Saved/Frame Pointer简写)帧指针| | 31|$ra| 返回地址，目测也是不可做其他用途| ## 程序结构 * 本质其实就只是数据声明+普通文本+程序编码（文件后缀为.s，或者.asm也行） * 数据声明在代码段之后（其实在其之前也没啥问题，也更符合高级程序设计的习惯） ### 数据声明 - 数据段以 .data为开始标志 - 声明变量后，即在主存中分配空间。 ### 代码 * 代码段以 **.text**为开始标志 * 其实就是各项指令操作 * 程序入口为**main：**标志（这个都一样啦） * 程序结束标志（详见下文） ### 注释 ``` # Comment giving name of program and description of function # Template.s #Bare-bones outline of MIPS assembly language program .data # variable declarations follow this line 　　　　 # 数据变量声明 # ... .text # instructions follow this line # 代码段部分 main: # indicates start of code (first instruction to execute) # 主程序 # ... # End of program, leave a blank line afterwards to make SPIM happy # 程序结束,留下一个空行之后 ``` ### 数据声明 ``` name: storage_type value(s) 变量名：（冒号别少了） 数据类型 变量值 ``` * 通常给变量赋一个初始值；对于**.space**,需要指明需要多少大小空间（bytes) ### 实例 ``` example: .data var1: .word 23 # declare storage for var1; initial value is 23 　　　　　　　　　　　　　　　　　　 # 先声明一个 word 型的变量 var1 = 3; .text __start: lw $t0, var1 # load contents of RAM location into register $t0: $t0 = var1 　　　　　　　　　　　　　　　　　　 # 令寄存器 $t0 = var1 = 3; li $t1, 5 # $t1 = 5 ("load immediate") 　　　　　　　　　　　　　　　　　　 # 令寄存器 $t1 = 5; sw $t1, var1 # store contents of register $t1 into RAM: var1 = $t1 　　　　　　　　　　　　　　　　　　 # 将var1的值修改为$t1中的值： var1 = $t1 = 5; done ```

[MIPS](%E6%B1%87%E7%BC%96/MIPS.md)

[TOC] ## 问题 1美元换 50美分,24美分,10美分,5美分,1美分,有几种方式 ## 思考 将总数为a的现金换成n种硬币的不同方式的数目等于 1. 将现金数a换成除第一种硬币之外的所有其他硬币的不同方式数目,加上 2. 将现金数a-d换成所有种类的硬币的不同方式数目,其中的d是第一种硬币的币值 将某个给定现金数的换零钱方式的问题,递归地归**约为**对更少现金数或者更少种类硬币的同一个问题。 - 如果a就是0,应该算作是有1种换零钱的方式。 - 如果a小于0,应该算作是有0种换零钱的方式 - 如果n是0,应该算作是有0种换零钱的方式。 ``` (define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50))) ;; -> 292 (count-change 100) ```

[TOC] ## 最大子序和 示例 1： ``` 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 ``` 示例 2： ``` 输入：nums = [1] 输出：1 ``` ## 实现 一种简单理解实现 ``` func maxSubArray(nums []int) int { if len(nums) < 2 { return nums[0] } max := nums[0] lastMax := nums[0] for i := 1; i < len(nums); i++ { n := nums[i] if tmp := n + max; tmp > n { max = tmp } else { max = n } } return lastMax } ``` 利用 nums[i] 保存 lastMax 的值 ``` func maxSubArray(nums []int) int { if len(nums) < 2 { return nums[0] } max := nums[0] for i := 1; i < len(nums); i++ { if nums[i] < nums[i]+nums[i-1] { nums[i] = nums[i] + nums[i-1] } if nums[i] > max { max = nums[i] } } return max } ```

[TOC] ## 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ >找到关系式 dp[i] = dp[i-1] + dp[i-2] n层台阶有 dp[n] ``` func climbStairs(n int) int { if n<=3{ return n } dp:=make([]int,n+1) dp[1]=1 dp[2]=2 for i:=3;i<=n;i++ { dp[i]=dp[i-1]+dp[i-2] } return dp[n] } ```

[爬楼梯](%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/%E7%88%AC%E6%A5%BC%E6%A2%AF.md) [最大子序和](%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.md)

[TOC] ## 字符串匹配——Sunday算法

[TOC] ## 概述 - 跳表(SkipList，全称跳跃表)是用于有序元素序列快速搜索查找的一个数据结构 - 实质就是一种可以进行二分查找的有序链表

[TOC] ## 场景 在一个字符串中是否包含另一个字符串 ## 概述 - 一句话概括,KMP算法的核心是已经匹配的字符不会重复匹配 - KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组 ### 图示   ## 解析 假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置 * 如果 j = -1，或者当前字符匹配成功（即 S\[i\] == P\[j\]），都令 i++，j++，继续匹配下一个字符； * 如果 j != -1，且当前字符匹配失败（即 S\[i\] != P\[j\]），则令 i 不变，j = next\[j\]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next \[j\] 位。 * 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的 next 值，即**移动的实际位数为：j - next\[j\]** * 如果 next [j] 等于 0 或 -1，则跳到模式串的开头字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某个字符 思路 1.构造next数组（初始化->处理前后缀不相同的情况->处理前后缀相同的情况） 2.使用next数组来做匹配 golang 实现 ``` func strStr(haystack string, needle string) int { n:=len(haystack) m:=len(needle) if (m==0){ return 0 } if (n0 && haystack[i]!=needle[q]{ q=next[q-1] } if ( haystack[i]==needle[q]){ q++ } if (q==m){ return i+1-m; } } return -1 } func compute_next( pattern string) []int { n:=len(pattern) next:=make([]int,n) k:=0 for q:=1;q0 && ( pattern[k]!=pattern[q]){ k=next[k-1]; } if ( pattern[k]==pattern[q]){ k++; } next[q]=k; } return next } ```

[KMP 算法](%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95/KMP%E7%AE%97%E6%B3%95.md) [跳表](../%E8%B7%B3%E8%A1%A8.md) [Sunday算法](%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95/Sunday%E7%AE%97%E6%B3%95.md)

[查找算法](%E7%AE%97%E6%B3%95/%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95.md) [动态规划](%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92.md) [零钱问题](%E7%AE%97%E6%B3%95/%E9%9B%B6%E9%92%B1%E9%97%AE%E9%A2%98.md)

[TOC] ## 将有序数组转换为二叉搜索树 给你一个整数数组`nums`，其中元素已经按**升序**排列，请你将其转换为一棵**高度平衡**二叉搜索树。  解答 ``` /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sortedArrayToBST(nums []int) *TreeNode { return helper(nums,0,len(nums)-1) } func helper(nums []int,left,right int)*TreeNode { if left>right { return nil } mid:=(left+right)/2 root:=&TreeNode{Val:nums[mid]} root.Left=helper(nums,left,mid-1) root.Right=helper(nums,mid+1,right) return root } ```

[TOC] ## 对称二叉树 给定一个二叉树，检查它是否是镜像对称的。 ``` 1 / \ 2 2 / \ / \ 3 4 4 3 ``` 解答 ``` /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func isSymmetric(root *TreeNode) bool { if root==nil{ return true } return helper(root.Left,root.Right) } func helper(left *TreeNode,right *TreeNode)bool{ if left==nil && right==nil{ return true } else if left==nil || right==nil || left.Val!=right.Val { return false } return helper(left.Left,right.Right) && helper(left.Right,right.Left) } ```

[TOC] ## 二叉树的最大深度 ``` /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func maxDepth(root *TreeNode) int { if root ==nil{ return 0 } left:=maxDepth(root.Left) right:=maxDepth(root.Right) return max(left,right)+1 } func max(a,b int)int{ if a>b{ return a } return b } ```

[二叉树的最大深度](%E7%A4%BA%E4%BE%8B/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.md) [对称二叉树](%E7%A4%BA%E4%BE%8B/%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.md) [将有序数组转换为二叉搜索树](%E7%A4%BA%E4%BE%8B/%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.md)