算法基础课听的不是很牢固,故听算法提高的时候边整合算法基础的内容,之后边学习边复习完善,同时补全语法基础的细节,并把相关的题目(leetcode和acwing)整理成题单,方便复习和强化思路,之后整理出一系列的总结

位运算

位运算的核心就是二进制的转化

位运算符的优先级

从高到低：~、&、^、|【其中~（取反）的结合方向自右至左，且优先级高于算术运算符，其余运算符的结合方向都是自左至右，且优先级低于关系运算符】

详细介绍

&:表示按位与我们通常使用0x0f来与一个整数进行&运算，来获取该整数的最低4个bit位，例如，0x31 & 0x0f的结果为0x01。二进制与运算规则:1&1=1 1&0=0 0&0=0

• 最重要的技巧就是(b>>n)&1(tips:),

  • 语法基础课中提到的细节:处理负数不能直接向右移
  • 解决办法:解决办法是把 nn 强制转化成无符号整型，这样 nn的二进制表示不会发生改变，但在右移时系统会自动在最高位补0。
  • 具体见: https://www.acwing.com/solution/content/732/
  • 作用:可以分别得到b的二进制的每一位具体是什么
  • 如 b = 5 则二进制就是0101,再循环和&操作下即可提取每一位的1

• 划重点:b&1也可以用来判断奇数和偶数,b&1=true时为奇数,反之b&1=false时为偶数

• 补充(基本用不上):语法基础课的lowbit运算 lowbit(x) = x&-x,返回x的最后一位1

^:按位异或运算**,参与运算的两个值，如果两个相应位相同，则结果为0，否则为1。即：0^0=0， 1^0=1， 0^1=1， 1^1=0。例如：10100001^00010001=10110000

• 该操作有一个常见方法:可以求出一个数组中只出现一次的数,把数组中所有的数异或起来(acwing 73.数组中只出现一次的数 )

• 还可用于实现不进位加法acwing 85.不用加减乘除做加法
  相关题目:acwing 26 二进制1的个数
  leetcode 数组中数字出现的次数

  ---

• 快速幂(算法基础课 acwing 875 快速幂 )
  算法原理:再a^b的时候,暴力求解(即循环b次分别模p),时间复杂度:o(n*b),会TLE,故借助二进制将其复杂度降为O(n∗logb).二进制yyds
  二进制的强大之处在于能表示所有数(当然本句话有点问题,具体想了解可以看看计算机组成原理,看误差的产生),即k可以用2^x1+2^x2…等表示,经过这个操作相当于把原先的循环,变成了log级别
  相同思路的龟速乘见下方
  具体参见高赞题解 [https://www.acwing.com/solution/content/15293/]
  一些细节:需要开到long long 的时候注意每次基本都要模p
  相关题目:acwing 876.快速幂求逆元
  acwing 886.求组和数II
  accwing 887.求组和数III
  acwing 89.a^b
  模板代码:

 LL res = 1;
        while(b)
        {
            if(b&1) res = (res*a)%p;
            a = (a*a)%p;
            b>>=1;
        }

• 龟速乘(算法提高课 acwing 90 64位整数乘法 )
  类比与快速幂将乘方变成乘法,该算法是将乘法变成加法
  核心原理:位数过大,相乘空间不够(上面的快速幂是时间超时),故将乘法这种一次运算位数变大很多的变成加法这种变化很小的.
  具体参见高赞答案 https://www.acwing.com/solution/content/844/
  相关题目:
  模板代码(比较快速幂,乘变加)

while(b) 
    {
        if(b&1) res= (res+a)%p;
        a = (a+a)%p;
        b>>=1;
    }