YuanLi's Notes

About the Internet

0%

Posted on In

剑指 Offer II 052. 展平二叉搜索树

今天在做这道题的时候，被困扰了很久，经过排错才发现是错误使用局部变量引发的错误

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public TreeNode increasingBST(TreeNode root) {
    TreeNode head=new TreeNode();
    TreeNode oldHead=head;
    middle(root,head);
    return oldHead.right;
}
public void middle(TreeNode node,TreeNode head){
    if(node==null){
        return;
    }
    middle(node.left,head);
    head.right=node;
    node.left=null;
    head=node;
    middle(node.right,head);
}

官方代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private TreeNode resNode;

public TreeNode increasingBST(TreeNode root) {
    TreeNode dummyNode = new TreeNode(-1);
    resNode = dummyNode;
    inorder(root);
    return dummyNode.right;
}

public void inorder(TreeNode node) {
    if (node == null) {
        return;
    }
    inorder(node.left);
    // 在中序遍历的过程中修改节点指向
    resNode.right = node;
    node.left = null;
    resNode = node;
    inorder(node.right);
}

可以看出我的代码和官方代码基本一致，唯一的区别就是官方的resNode变量是全局的，而我的head变量是局部的。

为什么用局部变量会出错？

middle函数首先传入root，head；在对root.left进行递归的时候，head会不断变化，但由于是局部变量，函数执行之后就被销毁了，也就是说head只是局部的变化；middle(node.left,head)执行完毕，使用的head还是第一次传入的head，所以会引发错误。

Posted on Edited on In

一、单体(monolithic)

单体架构的优点：

易于部署 – 一个可执行文件或目录使部署更容易.

开发 – 使用一个代码库构建应用程序时，开发更容易.

性能 – 在集中式代码库和仓库中, 一个API能够执行在多个微服务中多个API执行的相同功能(即微服务架构功能存在冗余，比如每个微服务都有登录模块)。

简化测试 – 由于单体应用程序是一个单一的集中式单元，因此可以比分布式应用程序更快地执行端到端测试.

易于调试 – 所有代码都位于一个位置，更容易跟踪请求并找到问题.

单体架构的缺点：

较慢的开发速度 – 大型的单体应用程序使开发更加复杂和缓慢.

可扩展性 – 您无法扩展单个组件.

可靠性 – 如果任何模块出现错误，都可能影响整个应用程序的可用性.

技术采用的障碍 – 框架或语言的任何更改都会影响整个应用程序，使更改通常昂贵且耗时.

缺乏灵活性 – 单体应用受到单体应用中已经使用的技术的限制.

部署 – 对单体应用程序的小改动需要重新部署整个单体应用程序.

二、微服务(microservices)

微服务的优点：

敏捷性 – 促进与经常部署的小型团队合作的敏捷方式.

灵活扩展 – 如果微服务达到其负载能力，该服务的新实例可以快速部署到随附的集群以帮助缓解压力.

持续部署 – 更频繁和更快的发布周期，以前每周发布一次更新，现在每天发布大约两到三次.

高度可维护性和可测试性 – 团队可以试验新功能并在出现问题时回滚。这样可以更轻松地更新代码并加快新功能的上市时间。此外，很容易隔离和修复单个服务中的故障和错误.

可独立部署 – 由于微服务是单独的单元，它们允许快速轻松地独立部署各个功能.

技术灵活性 – 微服务架构允许团队自由选择他们想要的工具.

高可靠性 – 可以为特定服务部署更改，而不会威胁到整个应用程序的崩溃.

微服务的缺点：

开发蔓延 – 与单体架构相比，微服务增加了更多复杂性，因为多个团队在更多地方创建了更多服务。如果开发蔓延没有得到妥善管理，则会导致开发速度变慢和运营性能下降.

基础设施成本 – 每个新的微服务都可以有自己的测试套件、部署手册、托管基础设施、监控工具等成本.

缺乏标准化 – 如果没有通用平台，语言、日志标准和监控可能会激增.

缺乏明确的所有权 – 随着更多服务的推出，运行这些服务的团队数量也在增加。随着时间的推移，很难知道团队可以利用的可用服务以及与谁联系以获得支持.

Posted on Edited on In
一、节点的度、深度

参见 https://github.com/Snailclimb/JavaGuide/blob/main/docs/cs-basics/data-structure/tree.md

二、二叉树

二叉树(Binary Tree)是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

​ 二叉树的性质：

​ 性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。

​ 性质2：深度为k的二叉树至多有2k-1个结点，(k≥1)。

​ 性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1。

三、满二叉树和完全二叉树

四、二叉搜索树

二叉搜索树（又：二叉查找树，二叉排序树，Binary Search Tree，BST）

满足以下几个条件：

1.若它的左子树不为空，左子树上所有节点的值都小于它的根节点。

2.若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。

3.任意结点的左、右子树也分别为二叉搜索树。

五、二叉平衡树

平衡二叉树又称AVL树

平衡二叉树是一棵二叉搜索树，且具有以下性质：

1.可以是一棵空树

2.如果不是空树，它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

Posted on Edited on In
Phase1
1
2
3
4
5
input = read_line();             /* Get input                   */
phase_1(input);                  /* Run the phase               */
phase_defused();                 /* Drat!  They figured it out!
      * Let me know how they did it. */
printf("Phase 1 defused. How about the next one?\n");

首先根据代码，先输入一个字符串，然后传入phase_1()这个函数，所以要分析在phase_1()这个函数里都做了什么。

1
2
3
4
5
6
7
8
9
0000000000400ee0 <phase_1>:
  400ee0:	48 83 ec 08          	sub    $0x8,%rsp         ;入栈，栈指针减8
  400ee4:	be 00 24 40 00       	mov    $0x402400,%esi	 ;%esi=402400
  400ee9:	e8 4a 04 00 00       	callq  401338 <strings_not_equal> ;调用
  400eee:	85 c0                	test   %eax,%eax  ;
  400ef0:	74 05                	je     400ef7 <phase_1+0x17> ;如果%eax为0，跳转
  400ef2:	e8 43 05 00 00       	callq  40143a <explode_bomb>
  400ef7:	48 83 c4 08          	add    $0x8,%rsp
  400efb:	c3                   	retq   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
0000000000401338 <strings_not_equal>:
  401338:	41 54                	push   %r12        ;原始值压入栈中
  40133a:	55                   	push   %rbp		   ;原始值压入栈中
  40133b:	53                   	push   %rbx		   ;原始值压入栈中
  40133c:	48 89 fb             	mov    %rdi,%rbx   ;%rbx=%rdi
  40133f:	48 89 f5             	mov    %rsi,%rbp   ;%rbp=%rsi
  401342:	e8 d4 ff ff ff       	callq  40131b <string_length> ;获得字符串长度
  401347:	41 89 c4             	mov    %eax,%r12d  ;%r12d=%eax
  40134a:	48 89 ef             	mov    %rbp,%rdi   ;%rdi=%rbp
  40134d:	e8 c9 ff ff ff       	callq  40131b <string_length> ;获得字符串长度
  401352:	ba 01 00 00 00       	mov    $0x1,%edx   ;%edx=1
  401357:	41 39 c4             	cmp    %eax,%r12d  
  40135a:	75 3f                	jne    40139b <strings_not_equal+0x63> ;比较两字符串长度，如果不同则跳转到40139b
  40135c:	0f b6 03             	movzbl (%rbx),%eax ;往上看，%rbx其实就是%rdi，也就是第一个字符串，因此%eax=(%rbx)即为第一个字符串的第一个字符
  40135f:	84 c0                	test   %al,%al  
  401361:	74 25                	je     401388 <strings_not_equal+0x50> ;如果%eax=0，则跳转到401388
  401363:	3a 45 00             	cmp    0x0(%rbp),%al  ;往上看，%rbp其实就是%rsi，也就是第二个字符串，因此这里是判断s1的第一个字符和s2的第一个字符是否相等，如果相等跳转到401372，否则跳转到40138f
  401366:	74 0a                	je     401372 <strings_not_equal+0x3a>
  401368:	eb 25                	jmp    40138f <strings_not_equal+0x57>
  40136a:	3a 45 00             	cmp    0x0(%rbp),%al
  40136d:	0f 1f 00             	nopl   (%rax)
  401370:	75 24                	jne    401396 <strings_not_equal+0x5e>
  401372:	48 83 c3 01          	add    $0x1,%rbx  ;%rbx=%rbx+1
  401376:	48 83 c5 01          	add    $0x1,%rbp  ;%rbp=%rbp+1
  40137a:	0f b6 03             	movzbl (%rbx),%eax 
  40137d:	84 c0                	test   %al,%al  ;如果字符串1的当前字符不为0，则跳转到40136a
  40137f:	75 e9                	jne    40136a <strings_not_equal+0x32>
  401381:	ba 00 00 00 00       	mov    $0x0,%edx
  401386:	eb 13                	jmp    40139b <strings_not_equal+0x63>
  401388:	ba 00 00 00 00       	mov    $0x0,%edx
  40138d:	eb 0c                	jmp    40139b <strings_not_equal+0x63>
  40138f:	ba 01 00 00 00       	mov    $0x1,%edx
  401394:	eb 05                	jmp    40139b <strings_not_equal+0x63>
  401396:	ba 01 00 00 00       	mov    $0x1,%edx   ;这几行的%edx其实都是标志位，当%edx为1时，两个字符串不相等，当%edx为0时，两个字符串相等
  40139b:	89 d0                	mov    %edx,%eax 
  40139d:	5b                   	pop    %rbx
  40139e:	5d                   	pop    %rbp
  40139f:	41 5c                	pop    %r12
  4013a1:	c3                   	retq   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
000000000040131b <string_length>:
  40131b:	80 3f 00             	cmpb   $0x0,(%rdi)   ;判断(%rdi)是否为0
  40131e:	74 12                	je     401332 <string_length+0x17>  ;如果是0，则跳到401332
  401320:	48 89 fa             	mov    %rdi,%rdx   ;%rdx=%rdi
  401323:	48 83 c2 01          	add    $0x1,%rdx   ;%rdx=%rdx+1
  401327:	89 d0                	mov    %edx,%eax   ;%eax=%edx
  401329:	29 f8                	sub    %edi,%eax   ;%eax=%eax-%edi 
  ;这里的上下两步其实可以简写为%eax=%edx-%edi 其实按理来说应该是%eax=%rdx-%rdi 但他这里用的低位四个字节，我在这认为是编译器的优化
  40132b:	80 3a 00             	cmpb   $0x0,(%rdx)  ;判断(%rdx)是否为0
  40132e:	75 f3                	jne    401323 <string_length+0x8>  ;如果不相等，跳到401323
  401330:	f3 c3                	repz retq 
  401332:	b8 00 00 00 00       	mov    $0x0,%eax  ;%eax=0
  401337:	c3                   	retq 
  
  由此看来<string_length>这个函数，首先是判断一下传入的字符串是否为空，为空直接返回0；否则计算一下字符串长度然后返回。

根据C语言代码和phase_1的反汇编代码，可以看出当的返回值为0，也就是传入的两个字符串相等时，炸弹才能拆除。这两个字符串，第一个是我们从命令行输入的，第二个则是以0x402400地址开始的字符串。因此，只需要找到这个字符串是什么，然后输入即可。

1
2
(gdb) print (char*) 0x402400
$1 = 0x402400 "Border relations with Canada have never been better."
Phase2

Posted on In

一个x86-64的中央处理单元(CPU)包含一组16个存储64位值的通用目的寄存器。这些寄存器用来存储整数数据和指针。

除了整数寄存器, CPU还维护着一组单个位的条件码(condition code)寄存器,它们描述了最近的算术或逻辑操作的属性。可以检测这些寄存器来执行条件分支指令。最常用的条件码有:

CF:进位标志。最近的操作使最高位产生了进位。可用来检查无符号操作的溢出.

ZF:零标志。最近的操作得出的结果为0

SF:符号标志。最近的操作得到的结果为负数

OF:溢出标志。最近的操作导致一个补码溢出一正溢出或负溢出

比如说,假设我们用一条ADD指令完成等价于C表达式t=a+ b的功能,这里变量a、 b和t都是整型的。然后,根据下面的C表达式来设置条件码:

条件码 表达式 描述
CF (unsigned) t < (unsigned) a 无符号溢出
ZF (t ==0) 零
SF (t<0) 负数
OF (a<0==b<0) && (t<0 !=a<0) 有符号溢出

CMP subtracts the operands and sets the flags. Namely, it sets the zero flag(ZF) if the difference is zero (operands are equal).

TEST sets the zero flag, ZF, when the result of the AND operation is zero. If two operands are equal, their bitwise AND is zero when both are zero. TEST also sets the sign flag, SF, when the most significant bit is set in the result, and the parity flag, PF, when the number of set bits is even.

JE [Jump if Equals] tests the zero flag and jumps if the flag is set. JE is an alias of JZ

So,

1
2
TEST %eax, %eax
JE   400e77 <phase_1+0x23>

jumps if the %eax is zero.

Posted on In

实现LRU缓存机制，需要用到一个哈希表和一个双向链表。

两者的作用：

  • 哈希表：记录此数据结构(即上面提到的LRU缓存机制数据结构)中存在的键值对
  • 双向链表：双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

当时看到这里有一个疑问，那就是为什么要用双向链表，不能用单向链表？

首先要知道一点：我们要始终保存head节点和tail节点的值，这样每次操作只需要吧tail移到head的前面即可。这个时候问题就出来了。如果使用单向链表，当我们把tail节点移动到head前时，我们当然可以令tail的next为head值，令head值为tail；但是此时新的tail(也就是旧的tail的前一个节点)值我们不能得到，想要得到就只能从头遍历一遍，因此要用双向链表。

Posted on In

前言

Java 泛型（generics）是 JDK 5 中引入的一个新特性, 泛型提供了编译时类型安全检测机制，该机制允许开发者在编译时检测到非法的类型。

泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。

泛型带来的好处

在没有泛型的情况的下，通过对类型 Object 的引用来实现参数的“任意化”，“任意化”带来的缺点是要做显式的强制类型转换，而这种转换是要求开发者对实际参数类型可以预知的情况下进行的。对于强制类型转换错误的情况，编译器可能不提示错误，在运行的时候才出现异常，这是本身就是一个安全隐患。

那么泛型的好处就是在编译的时候能够检查类型安全，并且所有的强制转换都是自动和隐式的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class GlmapperGeneric<T> {
		private T t;
    public void set(T t) { this.t = t; }
    public T get() { return t; }
  
    public static void main(String[] args) {
        // do nothing
    }

  /**
    * 不指定类型
    */
  public void noSpecifyType(){
    GlmapperGeneric glmapperGeneric = new GlmapperGeneric();
    glmapperGeneric.set("test");
    // 需要强制类型转换
    String test = (String) glmapperGeneric.get();
    System.out.println(test);
  }

  /**
    * 指定类型
    */
  public void specifyType(){
    GlmapperGeneric<String> glmapperGeneric = new GlmapperGeneric();
    glmapperGeneric.set("test");
    // 不需要强制类型转换
    String test = glmapperGeneric.get();
    System.out.println(test);
  }
}

上面这段代码中的 specifyType 方法中 省去了强制转换，可以在编译时候检查类型安全，可以用在类，方法，接口上。

泛型中通配符

我们在定义泛型类，泛型方法，泛型接口的时候经常会碰见很多不同的通配符，比如 T，E，K，V 等等，这些通配符又都是什么意思呢？

常用的 T，E，K，V，？

本质上这些个都是通配符，没啥区别，只不过是编码时的一种约定俗成的东西。比如上述代码中的 T ，我们可以换成 A-Z 之间的任何一个 字母都可以，并不会影响程序的正常运行，但是如果换成其他的字母代替 T ，在可读性上可能会弱一些。通常情况下，T，E，K，V，？ 是这样约定的：

  • ？ 表示不确定的 java 类型
  • T (type) 表示具体的一个java类型
  • K V (key value) 分别代表java键值中的Key Value
  • E (element) 代表Element

？ 无界通配符

先从一个小例子看起，原文在 这里 。

我有一个父类 Animal 和几个子类，如狗、猫等，现在我需要一个动物的列表，我的第一个想法是像这样的：

1
List<Animal> listAnimals

但是老板的想法确实这样的：

1
List<? extends Animal> listAnimals

为什么要使用通配符而不是简单的泛型呢？通配符其实在声明局部变量时是没有什么意义的，但是当你为一个方法声明一个参数时，它是非常重要的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static int countLegs (List<? extends Animal > animals ) {
    int retVal = 0;
    for ( Animal animal : animals )
    {
        retVal += animal.countLegs();
    }
    return retVal;
}

static int countLegs1 (List< Animal > animals ){
    int retVal = 0;
    for ( Animal animal : animals )
    {
        retVal += animal.countLegs();
    }
    return retVal;
}

public static void main(String[] args) {
    List<Dog> dogs = new ArrayList<>();
 	// 不会报错
    countLegs( dogs );
	// 报错
    countLegs1(dogs);
}

当调用 countLegs1 时，就会飘红，提示的错误信息如下：

所以，对于不确定或者不关心实际要操作的类型，可以使用无限制通配符（尖括号里一个问号，即 <?> ），表示可以持有任何类型。像 countLegs 方法中，限定了上届，但是不关心具体类型是什么，所以对于传入的 Animal 的所有子类都可以支持，并且不会报错。而 countLegs1 就不行。

上界通配符 < ? extends E>

上界：用 extends 关键字声明，表示参数化的类型可能是所指定的类型，或者是此类型的子类。

在类型参数中使用 extends 表示这个泛型中的参数必须是 E 或者 E 的子类，这样有两个好处：

  • 如果传入的类型不是 E 或者 E 的子类，编译不成功
  • 泛型中可以使用 E 的方法，要不然还得强转成 E 才能使用
1
2
3
4
5
6
private <K extends A, E extends B> E test(K arg1, E arg2){
    E result = arg2;
    arg2.compareTo(arg1);
    //.....
    return result;
}

类型参数列表中如果有多个类型参数上限，用逗号分开

下界通配符 < ? super E>

下界: 用 super 进行声明，表示参数化的类型可能是所指定的类型，或者是此类型的父类型，直至 Object

在类型参数中使用 super 表示这个泛型中的参数必须是 E 或者 E 的父类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private <T> void test(List<? super T> dst, List<T> src){
    for (T t : src) {
        dst.add(t);
    }
}

public static void main(String[] args) {
    List<Dog> dogs = new ArrayList<>();
    List<Animal> animals = new ArrayList<>();
    new Test3().test(animals,dogs);
}
// Dog 是 Animal 的子类
class Dog extends Animal {

}

dst 类型 “大于等于” src 的类型，这里的“大于等于”是指 dst 表示的范围比 src 要大，因此装得下 dst 的容器也就能装 src 。

？ 和 T 的区别

？和 T 都表示不确定的类型，区别在于我们可以对 T 进行操作，但是对 ？ 不行，比如如下这种 ：

1
2
3
4
5
// 可以
T t = operate();

// 不可以
？ car = operate();

简单总结下：

T 是一个 确定的 类型，通常用于泛型类和泛型方法的定义，？是一个 不确定 的类型，通常用于泛型方法的调用代码和形参，不能用于定义类和泛型方法。

区别1：通过 T 来 确保 泛型参数的一致性

1
2
3
4
5
6
7
// 通过 T 来 确保 泛型参数的一致性
public <T extends Number> void
test(List<T> dest, List<T> src)

//通配符是 不确定的，所以这个方法不能保证两个 List 具有相同的元素类型
public void
test(List<? extends Number> dest, List<? extends Number> src)

像下面的代码中，约定的 T 是 Number 的子类才可以，但是申明时是用的 String ，所以就会飘红报错。

不能保证两个 List 具有相同的元素类型的情况

1
2
3
4
GlmapperGeneric<String> glmapperGeneric = new GlmapperGeneric<>();
List<String> dest = new ArrayList<>();
List<Number> src = new ArrayList<>();
glmapperGeneric.testNon(dest,src);

上面的代码在编译器并不会报错，但是当进入到 testNon 方法内部操作时（比如赋值），对于 dest 和 src 而言，就还是需要进行类型转换。

区别2：类型参数可以多重限定而通配符不行

使用 & 符号设定多重边界（Multi Bounds)，指定泛型类型 T 必须是 MultiLimitInterfaceA 和 MultiLimitInterfaceB 的共有子类型，此时变量 t 就具有了所有限定的方法和属性。对于通配符来说，因为它不是一个确定的类型，所以不能进行多重限定。

区别3：通配符可以使用超类限定而类型参数不行

类型参数 T 只具有 一种 类型限定方式：

1
T extends A

但是通配符 ? 可以进行 两种限定：

1
2
? extends A
? super A

Class<T> 和 Class<?> 区别

前面介绍了 ？ 和 T 的区别，那么对于，Class<T> 和 <Class<?> 又有什么区别呢？
Class<T> 和 Class<?>

最常见的是在反射场景下的使用，这里以用一段发射的代码来说明下。

1
2
3
4
// 通过反射的方式生成  multiLimit 
// 对象，这里比较明显的是，我们需要使用强制类型转换
MultiLimit multiLimit = (MultiLimit)
Class.forName("com.glmapper.bridge.boot.generic.MultiLimit").newInstance();

对于上述代码，在运行期，如果反射的类型不是 MultiLimit 类，那么一定会报 java.lang.ClassCastException 错误。

对于这种情况，则可以使用下面的代码来代替，使得在在编译期就能直接 检查到类型的问题：

Class<T> 在实例化的时候，T 要替换成具体类。Class<?> 它是个通配泛型，? 可以代表任何类型，所以主要用于声明时的限制情况。比如，我们可以这样做申明：

1
2
3
4
// 可以
public Class<?> clazz;
// 不可以，因为 T 需要指定类型
public Class<T> clazzT;

所以当不知道定声明什么类型的 Class 的时候可以定义一 个Class<?>。

那如果也想 public Class<T> clazzT; 这样的话，就必须让当前的类也指定 T ，

1
2
3
4
public class Test3<T> {
    public Class<?> clazz;
    // 不会报错
    public Class<T> clazzT;

转自：https://juejin.cn/post/6844903917835419661#heading-1

Posted on In

一、位运算概览

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
| 或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

二、实例

1.~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int main()
{
    int x = 9;
    printf("x=%d \n", x);
    printf("~x=%d \n", ~x);
    return 0;
}

//结果
x=9
~x=-10

//原理
 9 (base 10) = 00000000000000000000000000001001 (base 2)
               --------------------------------
~9 (base 10) = 11111111111111111111111111110110 (base 2) = -10 (base 10)

-------------------------------------------------------------------------------
如果把x的值换成-10,那么结果正好相反

上面9和-10都是用他们的补码表示的，因为在计算机中用补码来表示数字

Bitwise NOTing any number x yields -(x + 1). For example, ~-5 yields 4.

参考：

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_NOT

https://www.runoob.com/w3cnote/bit-operation.html

Posted on Edited on In

一、前置知识

1.补码

Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big-endian numbers, rightmost bit in little-endian numbers) to indicate whether the binary number is positive or negative (the sign). It is used in computer science as the most common method of representing signed (positive, negative, and zero) integers on computers,[1] and more generally, fixed point binary values. When the most significant bit is a one, the number is signed as negative. (see Converting from two's complement representation, below).

Two's complement is executed by 1) inverting (i.e. flipping) all bits, then 2) adding a place value of 1 to the inverted number. For example, say the number +6 is of interest. +6 in binary is 0110 (the leftmost MSB is needed for the sign; positive 6 is not 110 because it would be interpreted as -2). Step one is to flip all bits, yielding 1001. Step two is to add the place value one to the flipped number, which yields 1010. To verify that 1010 indeed has a value of -6, remember that two's complement makes the most significant bit represent a negative place value, then add the place values: 1010 = 1(-23)+0(22)+1(21)+0(20) = 1(-8) + 0 + 1(2) + 0 = -6.

二进制补码是一种数学运算，可将正二进制数可逆地转换为具有等效（但为负）值的负二进制数，使用具有最大位值的二进制数（大端数中的最左边位，小端数中的最右边位- endian numbers）来指示二进制数是正数还是负数（符号）。它在计算机科学中用作在计算机上表示有符号（正、负和零）整数的最常用方法，[1] 以及更普遍的定点二进制值。当最高有效位为 1 时，该数字被标记为负数。 （请参阅下面的从二进制补码表示转换）。

二进制补码的执行方式是 1) 反转（即翻转）所有位，然后 2) 将位值 1 添加到反转后的数字。例如，假设数字 +6 是有趣的。二进制中的 +6 是 0110（符号需要最左边的 MSB；正 6 不是 110，因为它会被解释为 -2）。第一步是翻转所有位，得到 1001。第二步是将位值 1 与翻转后的数字相加，得到 1010。要验证 1010 确实具有值 -6，请记住二进制补码是最高有效位表示负位值，然后添加位值：1010 = 1*(-23)+0*(22)+1*(21)+0*(20) = 1(-8) + 0 + 1(2 ) + 0 = -6。

二、计算机数字编码方式

大多数机器对整数使用补码编码,而对浮点数使用IEEE标准754编码 ----csapp-2.5

Posted on In

代码变成可执行文件，叫做编译（compile）；先编译这个，还是先编译那个（即编译的安排），叫做构建（build）。

Make是最常用的构建工具，诞生于1977年，主要用于C语言的项目。但是实际上 ，任何只要某个文件有变化，就要重新构建的项目，都可以用Make构建。

一、Make的概念

Make这个词，英语的意思是"制作"。Make命令直接用了这个意思，就是要做出某个文件。比如，要做出文件a.txt，就可以执行下面的命令。

1
$ make a.txt

但是，如果你真的输入这条命令，它并不会起作用。因为Make命令本身并不知道，如何做出a.txt，需要有人告诉它，如何调用其他命令完成这个目标。

比如，假设文件 a.txt 依赖于 b.txt 和 c.txt ，是后面两个文件连接（cat命令）的产物。那么，make 需要知道下面的规则。

1
2
a.txt: b.txt c.txt
    cat b.txt c.txt > a.txt

也就是说，make a.txt 这条命令的背后，实际上分成两步：第一步，确认 b.txt 和 c.txt 必须已经存在，第二步使用 cat 命令 将这个两个文件合并，输出为新文件。

像这样的规则，都写在一个叫做Makefile的文件中，Make命令依赖这个文件进行构建。Makefile文件也可以写为makefile， 或者用命令行参数指定为其他文件名。

1
2
3
$ make -f rules.txt
# 或者
$ make --file=rules.txt

上面代码指定make命令依据rules.txt文件中的规则，进行构建。

总之，make只是一个根据指定的Shell命令进行构建的工具。它的规则很简单，你规定要构建哪个文件、它依赖哪些源文件，当那些文件有变动时，如何重新构建它。

二、Makefile

构建规则都写在Makefile文件里面，要学会如何Make命令，就必须学会如何编写Makefile文件。

参考：https://www.ruanyifeng.com/blog/2015/02/make.html