复杂度分析

发表于 2025-03-18 更新于 2025-04-09 分类于数据结构与算法， leetcode真题分类
本文字数： 5.2k

什么是大O

n表示数据规模，则表示运行算法所需要执行的指令数，和成正比。

一个算法有多个步骤，每个步骤规模相同但时间复杂度不同，最终的时间复杂度以最高的那个为准。

对数据规模的概念

如果想要在1s之内解决问题：

的算法可以处理大约级别的数据；
的算法可以处理大约级别的数据；
的算法可以处理大约级别的数据；

这个结论只是执行简单的数据操作，实际还需要再低估一下。

空间复杂度

多开一个辅助数组：;
多开一个辅助的二维数组：
多开常数空间：;

需要注意：递归调用是有空间代价的，递归的深度就是空间复杂度。

//计算n以内数据的和

//空间复杂度O(1)
int sum1(int n)
{
    assert(n >= 0);
    int ret = 0;
    for(int i=0;i<=n;i++)
    {
        ret += i;
    }
    return ret;
}

//递归调用：空间复杂度O(n)
int sum2(int n)
{
    assert(n>=0);
    if(n == 0)
        return 0;

    return n + sum2(n-1);
}

简单的时间复杂度分析

O(1)

常数级的算法很简单，没有数据规模的变化

// O(1)
void swapTwoInts(int &a , int &b){
    int temp = a;
    a = b;
    b = temp;
    return;
}

O(n)

O(n)的算法典型的特征就是有个循环，并且循环的次数和n相关。

其实正常来说，应该是，其中C是个常数，且不一定大于1

// O(n)
int sum(int n){

    assert(n >= 0);

    int ret = 0;
    for( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

//字符串反转，只需要进行1/2次的swap操作即可
void reverse(string &s){

    int n = s.size();
    for(int i = 0 ; i < n/2 ; i ++)
        swap( s[i] , s[n-1-i] );
    return;
}

O(n^2)

见到算法内部有双重循环，每层循环都是n相关基本就八九不离十了。

//选择排序算法
void selectionSort(int arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

千万要注意两层循环都要和n相关，不要看到双重循环就认为是


//第二重循环哪怕循环300w次，这个也是O(n)
void printInformation(int n){

    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= 30 ; j ++ )
            cout << "Class " << i << " - " << "No. " << j << endl;
    return;
}

O(logn)

经典的二分查找法：

//二分查找法
int binarySearch(int arr[], int n, int target){

    int l = 0, r = n-1;
    while( l <= r ){
        int mid = l + (r-l)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

将数字整形转化为字符串：

string intToString(int num){

    string s = "";
    string sign = "+";
    if(num < 0){
        num = -num;
        sign = "-";
    }

    while(num){
        s += '0' + num % 10;
        num /= 10;
    }

    if(s == "")
        s = "0";

    reverse(s);
    if(sign == "-")
        return sign + s;
    else
        return s;
}

分析算法思想，核心在" num /= 10"步中，就是n经过几次“除以10”操作后等于0，那么就是;

虽然上面两个例子，一个是以2为底，一个是以10为底，但都是，这个可以通过对数函数的换底公式来理解：有换底公式，可见和之间只相差一个常数，在时间复杂度下可以直接理解为

还需要注意，双重循环也可能出现logN的复杂度，需要注意量增长的规模：

//复杂度:O(nlogn)
void hello(int n){

    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout << "Hello, Algorithm!" << endl;
}

//外层循环每次增长可以理解为sz*2
//其实就可以理解为n经过几次“除以2”的操作后等于1，外层循环复杂度O(logn)
//内层循环复杂度是O(n)
//合起来是O(nlogn)



//判断是否为素数
// O(sqrt(n))
bool isPrime(int num){

    if( num <= 1 ) return false;
    if( num == 2 ) return true;
    if( num % 2 == 0 ) return false;

    for(int x = 3 ; x * x <= num ; x += 2)
        if( num%x == 0 )
            return false;

    return true;
}

//

递归算法的复杂度分析

面对递归算法需要具体问题具体分析。

递归中只会进行一次递归调用

如果递归函数中只进行一次递归调用，递归深度为depth，在每个递归函数中的时间复杂度为T，则总体的时间复杂度为，既只需关注递归的深度

//递归调用的二分查找法
int binarySearch(int arr[], int l, int r, int target){

    if(l > r)
        return -1;

    int mid = l + (r - l) / 2;
    if(arr[mid] == target)
        return mid;
    else if(arr[mid] > target)
        return binarySearch(arr, l, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, r, target);

}

二分查找法很容易用递归实现，上述代码每次调用时，内部要么直接返回，要么数组左半边调用递归，要么数组右半边调用递归，只会调用一次，所以分析时间复杂度只有看递归的深度即可。

每次调用数组减少一半，是典型的logn情况，所以复杂度为

// sum,O(n)
int sum(int n){

    assert(n >= 0);

    if(n == 0)
        return 0;
    return n + sum(n - 1);
}

// 求x的n次方：O(logn)
double pow(double x, int n){

    assert(n >= 0);

    if(n == 0)
        return 1.0;

    double t = pow(x, n / 2); //每次减半，logn
    if(n % 2)
        return x * t * t;

    return t * t;
}

递归中进行多次递归调用

当递归中有多次递归调用时，就需要关注递归调用的次数了。如果递归中只调用一次，深度就是次数，但如果调用了多次，那么深度和次数就是两个概念了。

//O(2^n)
//这个是指数级的算法，是个非常慢的算法
int f(int n)
{
    assert(n >= 0);

    if(n == 0)
        return 1;

    return f(n-1) + f(n-1);
}

均摊复杂度分析

有时候会遇到这种情况：解决某个问题时运用了一系列算法，某个算法的复杂度很高，但这个算法可以降低其他算法的复杂度，这时候就需要计算分摊复杂度。

均摊复杂度的经典问题就是动态数组vector。

template <typename T>
class MyVector{

private:
    T* data;
    int size;       // 存储数组中的元素个数
    int capacity;   // 存储数组中可以容纳的最大的元素个数

    // 复杂度为 O(n)
    void resize(int newCapacity){

        assert(newCapacity >= size);
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector(){

        data = new T[100];
        size = 0;
        capacity = 100;
    }

    ~MyVector(){

        delete[] data;
    }

    // 平均复杂度为 O(1)
    void push_back(T e){
        //当元素到达容量上限时，需要调用resize扩大空间
        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)
    T pop_back(){

        assert(size > 0);
        size --;

        return data[size];
    }

};

上面的代码只在push操作时resize了空间，但是没有在pop操作时resize空间。我们当然可以参考push操作，在pop到capacity一半时resize容量，但这里涉及一个问题，就是要防止复杂度震荡。

考虑这个问题：当push到临界点时resize一倍空间，然后立即pop，此时又resize为一半，然后立即push，这种极端场景下时间复杂度无法均摊，会退化为。

如果想避免这种场景，可以不再临界点处resize，当pop操作到达capacity的1/4处时，resize为1/2

// 平均复杂度为 O(1)
T pop_back(){

    assert(size > 0);
    T ret = data[size-1]; //这里一定要提前拿出来，resize操作会修改data
    size --;

    // 在size达到静态数组最大容量的1/4时才进行resize
    // resize的容量是当前最大容量的1/2
    // 防止复杂度的震荡
    if(size == capacity / 4)
        resize(capacity / 2);

    return ret;
}

C到C++的改进

发表于 2025-04-02 更新于 2025-04-18 分类于 C++
本文字数： 9.7k

C语言字符的语法陷阱

先看C语言中常见的词法、语法问题：

char c1 = 'yes';
/*
* 不符合常理，但这样定义没有错误
* 编译器会截断
* 至于是保留第一个还是最后一个，这个和编译器有关
* 虽然没报错，但编译器会有warning
*/

	
char c2 = "yes";
/*
* 编译器报错
* "yes"是一个字符串，c2只是一个字符变量，不能存储字符串
*/

const char* slash = "/";
/*
字符串的正确定义方法
slash中存放两个字符：'/'、'\0'
这样其实就是把字符串的首地址给了指针变量
*/

const char* slash2 = '/';
/*
编译器报错
字符的类型不能给指针，两个变量类型不匹配
*/

const char* slash3 = &c1;
/*
正确
slash3指针变量存放c1单个字符的地址
*/

从上面的例子可以看到，C语言是高级语言中的低级语言，优点是小巧、高效、接近底层，比如上面的例子就把字符和字符串区分的很细，但缺点就是细节和陷阱比较多。为了更好的解决这个问题，C++在兼容C语言的同时，推出了既高效又易于大规模开发的机制：string类的使用:

#include <string>

string s1(1,'yes');  //s
string s2(3,'yes');  //sss
string s3(1,'y');    //y
string s4("/");      // /
string s5(1,'/');    // /
string s6("yes");    //yes

C语言指针和数组的关系问题

c预言数组在作为参数时的退化行为，退化为一个指针。

给定一个数组，计算数组中的数据的平均数，有以下代码：

//计算平均数
double average1(int arr[10])
{
	double result = 0.0;
	int len = sizeof(arr) / sizeof(arr[0]);
	std::cout << "In average1 : " << len << std::endl;
	for (int i = 0; i < len; i++)
	{
		result += arr[i];
	}

	return result / len;
}

int main()
{
	int array1[] = { 10,20,30,40,50,60,70,80,90,100 };

	//数组长度最好是用变量这样来求，不要写成常量
	//这样方便扩展
	int len = sizeof(array1) / sizeof(array1[0]);
	std::cout << "len : " << len << std::endl;

	std::cout << average1(array1) << std::endl;

	return 0;
}

可以看到输出的值并不是平均数，通过输出中间数据可以知道，main函数中的长度是10，而average1中的数组长度是1；

出现这个的原因就是C预言数组在作为函数参数传递时会退化为一个指针，average1中的入参实际上只是函数的首地址，sizeof(arr)输出的只是单个元素的长度。

可以进行如下优化，通过外部把数组长度先行计算出来然后传递给函数。需要注意，如果传递的是字符数组的话就不需要这么麻烦了，因为字符数组往往是通过'\0'结尾的，函数内部有办法知道数组的长度。

//直接把数组长度传递进来
double average2(int arr[10], int len)
{
	double result = 0.0;

	for (int i = 0; i < len; i++)
	{
		result += arr[i];
	}

	return result / len;
}

int main()
{
	int array1[] = { 10,20,30,40,50,60,70,80,90,100 };

	int len = sizeof(array1) / sizeof(array1[0]);

	std::cout << average2(array1,len) << std::endl;

	return 0;
}

其实知道数组当作函数参数传递时会发生退化时，就可以不传递数组，而是只传递指针：

double average2(int* arr, int len)
{
	double result = 0.0;

	for (int i = 0; i < len; i++)
	{
		result += arr[i];
	}

	return result / len;
}

C语言之所以要这么做，是和c语言发展分不开的。c语言早期是伴随着unix操作系统，是非常底层的，对空间要求非常高的语言。如果函数传参时传递了一个非常大的数据容器，空间转移的效率是非常低的。所以C语言设计者就通过传递指针和容器尺寸这样一种传递方式从而达到节省空间的目的。

C++的解决方案就是引入STL容器，实现底层包装，保证效率的同时也保证简单安全。

#include <vector>

//这里传递的是引用
//如果传递的是vector本身，c++这里会产生一个副本，如果容器很大会得不偿失
double average3(std::vector<int>& v)
{
	double result = 0.0;
	std::vector<int>::iterator it = v.begin();
	for (;it!=v.end();++it)
	{
		result += *it;
	}

	return result / v.size();
}

int main()
{
    std::vector<int> vt = { 10,20,30,40,50,60,70,80,90,100 };
	std::cout << average3(vt) << std::endl;

    return 0;
}

使用stl容器后，哪怕是二维数组，处理起来也很方便了：

double average2DV(vector<vector<int> >& vv)
{
	double result = 0.0;
	unsigned int size = 0;

	for (unsigned int i = 0; i < vv.size(); ++i)
	{
		for (unsigned int j = 0; j < vv[i].size(); ++j)
		{
			result += vv[i][j];
			size += 1;
			cout << vv[i][j] << " ";
		}
		cout << endl;
	}

	return result / size;
}

int main()
{
    vector<vector<int> > vv2D{8, vector<int>(12,3) }; //8个vector，每个包含12个3
    cout << average2DV(vv2D);
    return 0;
}

C语言的移位问题

问题一：右移操作：无法区分是逻辑右移还是算术右移。

#include<cstdio>

#include <bitset>
#include <iostream>
using namespace std;

int main()
{
	
	char a1 = 0x63;       // 0110 0011
	a1 = (a1 << 4);        // 0011 0000
	printf("0x%x\n", a1);  //左移操作，末位补0

	a1 = 0x63;                // 0110 0011
	a1 = (a1 >> 4);        //  0000 0110 逻辑右移
	printf("0x%x\n", a1);  // 逻辑右移自动补0


	char a2 = 0x95;       // 1001 0101
	a2 = (a2 << 4);        // 0101 0000
	printf("0x%x\n", a2);  //左移操作，末位补0

	a2 = 0x95;                // 1001 0101
	a2 = (a2 >> 4);        //  1111 1001 算术右移
	printf("0x%x\n", a2);   //这里执行的是算数右移操作，补1了

	return 0;
}

上面可以看到，C语言在执行右移操作时表现不同，而不同的编译器输出的结果可能都不一样，C语言并没有做统一标准。C语言官方的做法是在做右移操作时，把操作数都变为无符号的数，这样可以保证执行的是逻辑右移操作（补0）。原因是无符号数首位都是0，可以保证补位的数也是0。

int main()
{
	
	unsigned char a3 = 0x63;       // 0110 0011
	a3 = (a3 << 4);        // 0011 0000
	printf("0x%x\n", a3);

	a3 = 0x63;                // 0110 0011
	a3 = (a3 >> 4);        //  0000 0110 逻辑右移
	printf("0x%x\n", a3);


	unsigned char a4 = 0x95;       // 1001 0101
	a4 = (a4 << 4);        // 0101 0000
	printf("0x%x\n", a4);

	a4 = 0x95;                // 1001 0101
	a4 = (a4 >> 4);        //  0000 1001 逻辑右移
	printf("0x%x\n", a4);

	return 0;
}

问题二：移位操作位数的限制。

int main()
{
    //示例常见与权限控制，每一位代表不同的权限
	//0000 0000
	const unsigned char priv = 0xFF;  //初始化权限
	const unsigned char P_BAKCUP = (1<<7);  //备份权限
	const unsigned char P_ADMIN = (1<<8);   //最高权限

	printf("0x%x\n", P_BAKCUP);
	printf("0x%x\n", P_ADMIN);
	if (priv & P_BAKCUP)
	{
		cout << "BAKUP" << endl;
	}
	if (priv & P_ADMIN)
	{
		cout << "ADMIN" << endl;
	}
	return 0;
}

由运行结果可以看到，char本身就只有8位，P_ADMIN的移位操作已经超过了8位，这时候所有的8位都被清零了。这是C语言编码常见错误，移位操作一定要注意操作位数上限，移位数大于0，小于位数；

出现上面两个问题的原因就是，C语言设计移位操作时需要考虑操作数表示的上下文环境。C++为了对这个问题做改进，引入了bitset：

#include <bitset>

int main()
{
    // bitset
	bitset<10> priv = 0xFF;  //手动控制，这里就只有10位
	bitset<10> P_BAKCUP = (1 << 6);
	bitset<10> P_ADMIN = (1 << 7);

    //这里可以直接输出
	cout << priv << endl;
	cout << P_BAKCUP << endl;
	cout << P_ADMIN << endl;

	if ((priv & P_BAKCUP) == P_BAKCUP)
	{
		cout << "BAKUP" << endl;
	}
	if ((priv & P_ADMIN) == P_ADMIN)
	{
		cout << "ADMIN" << endl;
	}

	return 0;
}

C语言强制类型转换问题

C语言中强制类型转换隐藏了很多bug和陷阱：

#include <iostream>
using  namespace std;

int main()
{
	int array[] = { 1,2,3 };
	cout << sizeof(array) / sizeof(array[0]) << endl;
	int threshold = -1;
	
	if (sizeof(array) / sizeof(array[0]) > threshold)
	{
		cout << "positive number array" << endl;
	}
	else
	{
		cout << "negative number array" << endl;
	}

	return 0;
}

上面的代码当数组长度大于0时，需要输出“positive number array”，否则输出“negative number array”。可以通过编译运行后，长度输出为3是正确的，但判断逻辑里却输出了“negative number array”。

发生这个问题的原因是sizeof的返回值是unsigned int,是无符号数，但threshold却是一个有符号数，在执行比较判断语句时，C语言的机制把threshold转换为了一个无符号数，然后才进行的比较。这里发生的是隐式类型转换。-1转换为unsigned int时会变为4294967295，是个很大的正整数（这里涉及到了补码转换）。

C语言在编写时，可以先用一个有符号的数把数据先取出来。今后编码时也需要注意，尽量避免用无符号的数据来进行数据比较：

#include <iostream>
using  namespace std;

int main()
{
	int array[] = { 1,2,3 };
	cout << sizeof(array) / sizeof(array[0]) << endl;
	int threshold = -1;
	int len = sizeof(array) / sizeof(array[0]);  //用一个有符号的变量先把数据拿出来
	
	if (len > threshold)
	{
		cout << "positive number array" << endl;
	}
	else
	{
		cout << "negative number array" << endl;
	}

	return 0;
}

类型转换还可能会发生在以下情况：假设要计算1+1/2+1/3+……+1/n，如果代码是这么写的：

// 1+1/2+1/3+1/4+... +1/n
double getSum(int n)
{
	double result = 0.0;
	for (int i = 1; i < n + 1; i++)
	{
		result += 1 / i;
	}
	return result;
}

int main()
{
	int n = 0;
	cin >> n;
	cout << getSum(n) << endl;

	return 0;
}

可以看到，计算出的结果是1。这里的问题出在“result += 1/n”这句中，被除数是整形，除数也是整形，那么计算结果也是整型值。result虽然会转换为浮点数，但整形计算中已经丢失了精度。

c语言中的一个解决方法是把被除数先转换为浮点数：

// 1+1/2+1/3+1/4+... +1/n
double getSum(int n)
{
	double result = 0.0;
	for (int i = 1; i < n + 1; i++)
	{
		result += 1.0 / i;  //把被除数换成浮点数，那么结果会被转换为浮点数
	}
	return result;
}

int main()
{
	int n = 0;
	cin >> n;
	cout << getSum(n) << endl;

	return 0;
}

上面两个例子可以看到，有时候我们会忽略C语言的隐式类型转换，导致出现程序bug；但有时候我们又需要这种隐式类型转换来得到我们想要的结果。c语言中滥用类型转换可能导致灾难性的后果，且很难排查。C语言之所以这么设计，是因为类型转换在底层语言中的运用非常广泛，且灵活方便。C++为了方便排查隐藏bug减少复杂性，提供了四种类型转换的方式：static_cast、const_cast、dynamic_cast、reinterpret_cast。

static_cast：其实就是类似于C语言中的类型转换，C++提供了这么一种标准格式用于显示类型转换，可以方便程序员精准定位程序哪里使用了强制类型转换；
const_cast：只针对去除const属性；
dynamic_cast：用于类的继承关系转换，比如把子类转换为父类、或者父类转换为子类；
reinterpret_cast：用于指针的转换；

// 1+1/2+1/3+1/4+... +1/n
double getSum(int n)
{
	double result = 0.0;
	for (int i = 1; i < n + 1; i++)
	{
		result += static_cast<double>(1) / i;
	}
	return result;
}

int main()
{
	int n = 0;
	cin >> n;
	cout << getSum(n) << endl;

	return 0;
}

C语言的整数溢出问题

32位系统中，一个整数占用4个字节，共32位。其中第一位是符号位，所以一共有31位可以表示整数范围。如果计算的时候，如果我们算出的数值超出了数据表示范围，那么会数据溢出变为负数。要注意C语言中的整数不能和数学上的整数划等号。

int main()
{
	int i = 2147483640;
	for (; i > 0; i++)
	{
		cout << "adding " << i << endl;
	}
	cout << "exit " << i << endl;

	return 0;
}

出现这个问题的原因和系统的设计是有关的。数据存储空间是有限的，不能无限增长。C语言的一个解决方案是通过字符串的方式来表达大数的运算，字符串理论上是可以无限长的，C语言是有这个类库的，但并没有直接的解决方案。 C++本身也没有提供好的解决方案，但boost库中提供了cpp_int方法：boost官网

C语言字符串的典型缺陷

C标准字符和字符串的区别是：字符是单引号括起来的，字符串是双引号括起来的，由'\0'结尾。而'\0'作为结束符这个方式，表达能力有天生的缺陷：一旦字符串中间具有'\0'字符，那么c语言的字符串函数就会认为这个字符已经结束了。如果用c语言的方式存储一些图片或者其他二进制的内容，很容易出问题。

C语言的字符串操作还有另一个问题就是效率低下。C语言的字符处理函数都是通过遍历'\0'来寻找字符串结尾的，这个遍历操作会消耗性能。

C语言设计这种字符串处理方式主要是为了节省空间，有针对性的设计问题。C++语言为了解决这个问题有以下几种思路：

C++的string类
开源库Redis解决方案，redis官网

int main()
{
	cout << "Testing C++ String: " << endl;
	string sstr1 = "string";
	cout << sstr1.length() << endl;  //字符串内容的长度
	cout << sstr1.capacity() << endl; //string的容量长度
	cout << sizeof(sstr1) << endl;  //实际内存分配长度，不同平台的值可能不一致，但实际大小肯定会大于内容长度

	cout << endl;

	cout << "sstr2: " << endl;
	string sstr2 = "stri\0ng";
	cout << sstr2.length() << endl;
	cout << sstr2.capacity() << endl;
	cout << sizeof(sstr2) << endl;

	cout << endl;

	cout << "sstr1: " << endl;
	sstr1 += sstr2;   //字符串直接拼接
	cout << sstr1.length() << endl;
	cout << sstr1.capacity() << endl;
	cout << sizeof(sstr1) << endl;

	return 0;
}

可以看到，string类的实现方案中，内部不仅记录了字符串的内容，还有几个变量记录了字符串内容的长度、容量等，在执行字符串操作时不需要遍历寻找'\0'，提高了效率；但是依旧保留了c风格字符串以'\0'结尾的传统，还具有一些缺陷。

补码

发表于 2025-03-31 更新于 2025-04-02 分类于 C++
本文字数： 2.2k

机器数和真值

机器数：一个数在计算机中的二进制表示形式，叫做这个数的机器数。

机器数是带符号的，在计算机中用一个数的最高位存放符号，正数为0，负数为1；

比如：十进制数+3，就是00000000000000000000000000000011；十进制数-3，就是10000000000000000000000000000011；（int值占4字节）；这个例子只是整型数，浮点数有其他表达方式。

真值：真正的数学意义上的数值。因为机器数第一位是符号位，所以机器数的形式就不等于真正的数值。

补码

按照上面的机器数的表示方法有一个问题，第一位用作符号位的话，这个数的表示范围会变小。所以计算机中存储用的并不是机器数，而是补码。

无符号数的编码

用一个函数（Binary to Unsigned的缩写，长度为w）来表示：

eg:

有符号数的补码

用一个函数（Binary to Two`s-complement的缩写，长度为w）来表示：

eg:

补码数值范围

数	8位字长	16位字长	32位字长	64位字长
UMax	0xFF 255	0xFFFF 65535	0xFFFFFFFF 4294967295	0xFFFFFFFFFFFFFFFF 18446744073709551615
TMin	0x80 -128	0x8000 -32768	0x80000000 -2147483648	0x8000000000000000 -9223372036854775808
TMax	0x7F 127	0x7FFF 32767	0x7FFFFFFF 2147483647	0x7FFFFFFFFFFFFFFF 9223372036854775807
-1 0	0xFF 0x00	0xFFFF 0x0000	0xFFFFFFFF 0X00000000	0xFFFFFFFFFFFFFFFF 0X0000000000000000

需要注意，无符号数中0xFFFFFFFF是最大值，但有符号数中这个值代表-1；还要注意有符号数中的最小值是0x80000000;

字节序（Byte Ordering）

以32位机器为例，一个字有32bits字长，占用4bytes，在内存中有以下两个存放方式：

大端法（Big Endian）:大多数IBM机器、Internet传输；

小端法（Little Endian）:Inter兼容机

个人机器基本上都是小端表示法。

补码的意义

我们在设计软件系统时总是希望软件系统尽可能的简单通用。于是人们希望在只有加法运算器的情况下设计一种方法能实现减法运算。

以时间为例：表盘一圈12个小时，现在是8点，那么3小时前是5点，9小时以后还是5点(8+9-12)，这里进行的是模12的操作。所以8-3和8+9的结果是一样的；我们就可以用9来表示-3，如果想计算8-3，那么就用加法器计算8+9；

当然单纯的这么想是有问题的，以时间为例我们可以得到一个对照表，遇见12就清零：

0	-1	-2	-3	-4	-5	-6	-7	-8	-9	-10	-11
0	11	10	9	8	7	6	5	4	3	2	1

5-3 ==> (5+9)%12=2
3-5 ==> (3+7)%12 = 10 ==>-2

我们计算3-5的时候，得到的值是10，我们可以在对照表中得到10对应的值是-2，但我们计算5-3的时候，得到的值是2，我们却不需要找对应的值。计算机如何区分什么时候要找对应的值，什么时候不需要呢？

可以对表进行一些修改：

0	-1	-2	-3	-4	-5	-6	5	4	3	2	1
0	11	10	9	8	7	6	5	4	3	2	1

5-3 ==> (5+9)%12=2 ==>2
3-5 ==> (3+7)%12 = 10 ==>-2

表格修改后，每次计算完都在表格中进行对照，这样操作统一，得到的值也是正确的了。其实在计算机内部，补码的用处就是构造这张映射表的。

git基础

发表于 2025-03-27 更新于 2025-03-28 分类于 git
本文字数： 1.8k

git安装

git手册提供了完整的安装步骤。

安装成功后，命令行输入git命令可以检查是否安装成功：

1 2	#查看git版本 git --version

最小配置

使用git之前需要配置user.name和user.email，可以方便绑定每次操作的用户信息。

1 2	$ git config --global user.name 'your_name' $ git config --global user.email 'your_email@domain.com'

上面的'--global'是git的作用域，git一共有三个作用域：

--local :只对某个仓库有效
--global ：对当前用户的所有仓库有效
--system ：对系统的所有登录用户有效

显示config的配置，可以加--list：

1
2
3

$ git config --list --local
$ git config --list --global
$ git config --list --system

创建仓库并配置local用户信息

建立git仓库有两种使用场景：

第一种场景：把已经有的项目代码列入git管理

1 2	$ cd 项目代码目录 $ git init

第二种场景：新建的项目直接用git管理：

1
2
3

$ cd 某个目录
$ git init your_project  #会在当前路径下创建和项目名称同名的文件夹
$ cd your_project

以第二种方式为例，执行完命令后，会在目录下生成一个'.git'的隐藏目录。

如果此时在这个目录下配置local的用户名和邮箱，且和global配置的不同，那么在这个仓库中执行的操作会以local配置为准生效。

工作区和暂存区

1
2
3

$ git add files  #把工作目录中的内容添加暂存区

$ git commit     #把暂存区中的内容添加到正式版本历史

git标准的操作是每次在工作目录中修改的文件，都先添加入暂存区。为了某个功能而做的修改都添加入暂存区后，可以统一把这批文件commit到git版本库中。

$ git reset --hard
#这个命令可以重置暂存区，轻易不要使用

$ git status #查看工作目录修改状态

如果想要在git中修改某个文件的文件名，可以有两种方式：

# 方式1：工作目录中修改文件名，然后重新add、commit
$ mv old new   #修改文件名
$ git add new
$ git commit

# 方式2：直接调用git命令
$ git mv old new
$ git commit

查看版本历史和分支

# 查看每次提交的细节
$ git log

# 只查看提交备注
$ git log --oneline

# 只查看最近的某几次提交
$ git log -n2 --oneline  #只查看2次

# 查看本地有多少分支
$ git branch -v

# 查看所有分支的提交记录
$ git log --all

# 图形化查看所有分支的提交记录
$ git log --all --graph

对于Windows用户来说，可能更习惯图形化操作，可以使用git自带的图形化工具：

1	$ gitk # 打开图形化界面

".git"目录

新建仓库后，工作目录下会生成一个隐藏的".git"目录，这里面就是git最核心的内容。

常用的文件如下：

HEAD文件：记录当前工作在哪个分支上；
config文件：当前工作目录的一些配置，比如user.name和user.email；
refs/heads目录：各个分支指向的提交hash；
refs/tags目录：各个tag指向的提交hash；
objects目录：存放文件和更改，内部的对象可以分为commit、tree和blob三种类型；这个是git版本管理的底层目录；

git文件类型（commit、tree和blob）

数据存储是git的核心技术点；git的目标是项目管理，而项目管理中的文件变更很频繁，如果没有一个好的数据管理技术，git的存储信息会越来越大，性能会越来越差。所以设计一个良好的数据存储机制是很关键的。

.git的object中就是git存储的核心目录，下面的文件共有三种类型：commit、tree和blob。

上图是git官网文档的实例，每次执行commit操作都会创建一个commit对象出来；一个commit对应唯一一棵树，是这个commit的快照，存放所有的文件夹和文件；blob就是其中具体的文件；要注意每个blob和文件名毫无关系，在git中只要这个文件的内容相同，那对应的就是一个blob，这样可以大大减少存储代价。