基础算法知识点小结

bit

指1个0或者1

二进制

[begin{array}{c}{Large 117=(1110101)_2}hspace{1cm}{tinytext{最低位(0)}}hspace{0.6cm}{tinytext{最高位(6)}}end{array}]

十六进制

表示

以(0x)开头后面接十六进制数，如(0x75)表示十六进制数75，即((75)_6=117)

表

0	1	2	3	4	5	6	7
0	1	10	11	100	101	110	111
8	9	a(10)	b(1)	c(12)	d(13)	e(14)	f(15)
1000	1001	1010	1011	1100	1101	1110	1111

注：

最好能够记得，然后随便给你一个十六进制数，你能一秒内写出它的二进制位,十六进制的好处在于，十进制无法凸显二进制中的每一位，而十六进制的一位可以表现二进制中的8位，虽然考试不考，但是肯定对你有帮助，而且也可以锻炼你的记忆能力，尽管我现在都还记不得。

补码和反码

采取补码的类型满足(-x=sim x+1)

采取反码的类型满足(-x=sim x)

注：c++通常采用补码

无符号整型和有符号整型

以下对第n位而言

类型	范围	溢出	最低位	最高位
无符号整型	(0sim 2^n-1)	对(2^n)取模	0	n
有符号整型	(-2^nsim 2^n-1{tinyboxed{1}})	对(2^{n-1})取模	0	n-1

注释

({tinyboxed{1}}:)

(-2^n)等价于0，因为0的取反+1为0,而(-2^n)取反+1也为0，而这也解释为什么溢出了是对(2^{n-1})取模。

memset

表达式

[memset(a,b,sizeof(a))]

解释

1. a表示要进行操作的数组，(sizeof(a))取得是a的空间大小，好像把数组传到函数下或报错，因为不知道空间大小。
2. b表示你要给数组每个元素赋值的数，应该是一个8进制数，然后会将你的数组的每一个元素的每8位赋值为b的二进制位，推荐几个常用赋值的数，(0x3f)好处在于每三位(0011 1111),并且乘以2不过intmax（即(0x7fffffff)），还有就是(0x7f)也就是赋值为前面的intmax，还有就是(-1),全部赋值为-1

位运算

（讲解顺序按算术优先级排序）

(sim)（非）

表达式:(sim a)

解释

对a的二进制位下每一位进行取反操作，即0变为1,1变为0,如3为二进制数(~(101)_2=(010)_2)

解释

对a的二进制位下每一位取反，即

(<<,>>)（左移，右移）

表达式

(a<<b,a>>b)

解释

1. 其中a表示要进行操作的数，b表示右移左移的位数
2. 右移1位等价与/2向0取整（对负数也成立，如(3>>1=1,-3>>1=-1)），二进制下的理解即所有的数字向右移动，最高位补0,低位舍去，如((101111)_2>>3=(000101)_2)
3. 左移一位等价与乘2,（同样对负数也成立，如(3<<2=12,-3<<2=-12)），二进制理解下即所有数字向向左移动，最高位溢出舍去，最低位补0.如(00101111<<2=(10111100)_2)。

(&;)（与）

表达式(:a&;b)

解释

a，b二进制位下，每一位对应二进制位同为1才为1,否则为0,如((10011)_2&;(10000)_2=(10000)_2)

$$（异或）

表达式：(awedge b)

解释

1. 对a，b的二进制位下的每一位运算，相异为1,相同为1,即((10011)_2wedge(10000)_2=(00011)_2)
2. 只有二进制位上的1才造成改变，有类似奇偶的性质
3. 任何数异或0为其本身
4. 异或满足交换律和结合律，于是多次异或同一个数无效(awedge bwedge b=a)
5. 结合2，3条，对于类异或问题，即操作后1变为0,0变成1,那么多次进行重复操作无效，并且操作顺序不存在先后，这是重要的性质
6. 在图论中的异或和路径，即路径长边权为所有边权的异或值，原路返回等于没走，于是类似瞬间转移，真正产生结果的为环，而环可以作为线性基处理。

(|)(或)

表达式：(a|b)

解释

对于a，b每一位二进制位对应运算，只要有1就为1,如((10011)_2wedge(10000)_2=(10011)_2)

与或非通性

运算中可以拆开每一位独自运算，这样对于二进制运算的题目，我们可以对于每一位独自运算，这样会更加好做。

快速幂

[注：以下的ll均表示long long]

二分快速幂

原理：(x^y=(x^{y/2})^2times begin{cases}x(yintext{奇数})1(yintext{偶数})end{cases})

代码实现：

int pow(int x,int y,int yyb){
    if(!y)return 1;
    int ans(pow(x,y>>1,yyb));
    return ans*ans%yyb*((y&1)?x:1)%yyb;
}

二进制（拆分）幂

原理：({Large x^y=x^{c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_02^0}})

代码实现：

int pow(int x,int yyb){
    int ans(1%yyb);while(y){
        if(y&1)ans=(ll)ans*x%yyb;
        x=x*x%yyb,y>>=1;
    }return ans;

练习

64位乘法

问题

求(atimes b %yyb),其中，(a,yybleq 10^{18})

根号乘

原理

[atimes b% yyb=(atimessqrt{b}% yybtimes sqrt{b}% yyb+atimes (b-sqrt{b}times sqrt{b})%yyb)%yyb]

代码实现

此法已萎，有兴趣者自我娱乐

龟速乘

原理

[atimes b% yyb=atimes (c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_02^0)%yyb=ac_{k-1}2^{k-1}% yyb+ac_{k-2}2^{k-2}% yyb+...+ac_02^0%yyb]

参考代码

ll mult(ll a,ll b,ll p){
    ll ans(0);while(b){
        if(b&1)(ans+=a)%=p;
        (a<<=1)%=p,b>>=1;
    }return ans;
}

快速乘

原理

[atimes b%yyb=atimes b-([atimes b/yyb]times yyb]

代码实现

ll mult(ll a,ll p){
    ll ans(a*b-(ll)((lb)a*b/p)*p);
    if(ans<0)ans+=p;return ans;
}

---

证明：

设(x=atimes b,y=[atimes b/yyb]times yyb,xequiv x'(mod 2^{63}),yequiv y'(mod 2^{63}))

显然有(x-yequiv x'-y'(mod 2^{63})equiv atimes b%yyb)，而(yyb<2^{63})，于是有

((x-y)% 2^{63}=atimes b%yyb)，得证

---

练习

二进制压缩

标志

数据范围小

做法

用一个数字的二进制位表示bool变量的0or1，如开了个(bool a[31])，用b存储,其中b二进制第0位等价与(a[0])，第一位等价与(a[1]),...以此类推

常用操作

代码	解释
(n>>k&;1or1<<k$n)	取第k位上的数字
(n&;(1<<k+1))	取后k位
(nwedge 1<<k)	第k位上数字取反
(n|1<<k)	第k位数字赋值为1
(n&;1<<K)	第k位数字赋值为0

练习：

最短Hamilton路径

成对变换

定义

(nwedge1=begin{cases}n+1(nintext{偶数})n-1(nintext{奇数})end{cases})

于是称一对相邻的奇数偶数(a,b(b-a=1))为成对变换，而且具有性质(awedge 1=b,bwedge1=a)

lowbit

定义

[lowbit(x)=x&;-x=text{x最后的一位1以及后面的0组成的数（如$lowbit((1100100)_2)=100$）}]

应用

快速查找一个二进制数x的每一个1所在的位置

做法：

• 预处理(to[37])，预处理(to[2^i%37]=i(i=0,1,...,36))

求证：

(2^0%37,2^1%37,2^{36}% 37)互不相同

证明：

注意到37是一个质数，且与2互质，故满足费马小定理，有(2^{36}equiv 1(mod 37))

于是易知余数循环节为36,故36以内的数互不相同

• 输出(to[lowbit(x)%37]),令(x-=lowbit(x)),当x为0时，停止程序

参考代码

void prepare(){
    for(int i(0);i<37;++i)
        to[(1<<i)%37]=i;
}
void work(int n){
    while(n){
        printf("%d ",to[lowbit(n)%37]);
        n-=lowbit(n);
    }
}