QeuroIzoのBlog

hello world

0%

发表于 更新于

  • 不蒜子

    1. 在_includes/head.html添加以下代码：

    1
    2
    <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js">
    </script>

    2. 在_layouts/post.html添加以下代码：

    功能：

    1). 本文总阅读量

    1
    2
    3
    <span id="busuanzi_container_page_pv">
        本文总阅读量<span id="busuanzi_value_page_pv"></span>次&nbsp&nbsp&nbsp&nbsp
    </span>

    2). 本站总访问量

    1
    2
    3
    <span id="busuanzi_container_site_pv">
        本站总访问量<span id="busuanzi_value_site_pv"></span>次&nbsp&nbsp&nbsp&nbsp
    </span>

    3). 本站访客数

    1
    2
    3
    <span id="busuanzi_container_site_uv">
        本站访客数<span id="busuanzi_value_site_uv"></span>人次
    </span>

发表于 更新于

位运算：

  • & （与）

    eg:

    1 0 1

    0 0 1

    0 0 1

  • | （或）

    eg:

    1 0 1

    0 0 1

    1 0 1

  • ^ （异或）

1. 运算规则：（不进位加法）

0         0 ——> 0
1         0 ——> 1
0         1 ——> 1
1         1 ——> 0

2. 不进位的加法：

1 ^ 1 ==> 0 正常的话：1 + 1 = 20,但是只看个位，因此，取0

3. 运算法则：

  1. 交换律
  2. 结合律

    即$(a^b)^c == a^{b^c}$

  3. 对于任何数x，都有

    $x^x=0，x^0=x$

  4. 自反性：

    A XOR B XOR B = A xor 0 = A

  • ~ （取反）

    把 0 变成 1

    把 1 变成 0

  • << （左移）

eg:

  1. 1101 << 1 ===> 11010
  2. 1 << n == $2^n$ （向上取整）

  • >> （右移）

    eg:

    1. 1101 >> 1 ===> 110
    2. n >> x == $n \over 2^x$(向下取整)

技巧：

  1. x + (-x)

经验：

  • 将数组无穷大：memset(nums, 0x3f, sizeof(nums))
  • 竞赛中少使用#include <bits/stdc++.h> // 原因：编译的时间过长,时间会超时
  • 转化成 long long的形式：乘以 1ll,例子见——>快速幂算法模板—求$ a^b%p$
  • 将大数组放到全局变量中

快速幂算法模板

1：求 $ a^b $

1
2
3
4
5
6
7
8
9
10
11
long long quickPower(int a, int b)
{
    long long res = 1;
    while(b) {
        if(b & 1)
            res *= 1ll * a;
        a *= a;
        b >>= 1;
    }
    return res;
}

2：求 $a^b%p$

1
2
3
4
5
6
7
8
9
10
11
12
int quickPowerMod(int a, int b, int p)
{
    int res = 1 % p;
    while(b) {
        if(b & 1)
            res = res * 1ll * a % p;
        a = a * 1ll * a % p;
        b >>= 1;
    }
    return res;
}

模运算法则

  • (a + b) % p = (a % p + b % p) % p
  • (a - b) % p = (a % p - b % p) % p
  • (a * b) % p = (a % p * b % p) % p
  • (a^b) % p = ((a % p)^b) % p

位运算常用技巧

  • 用异或来实现配偶

    1
    2
    3
    4
    5
    0，1
    2，3
    4, 5
    6, 7
    ……

    即(把每个整数异或一个1，就可以得到他的配偶)

    1
    2
    3
    4
    0 ^ 1 = 1,            1 ^ 1 = 0
    2 ^ 1 = 3,            3 ^ 1 = 2
    ……
    2k ^ 1 = 2k + 1,    (2k + 1) ^ 1 = 2k

    使用

    1
    一般在图论里面，写最小费用流时，我们会存一个编的正向编和反向编，会需要快速求出来一个数的反向编是什么

  • lowbit运算(树状数组的基础)

    定义：

    快速的求出来整数n，在二进制表示里面，最低的一位1是哪个(或者说：n的二进制表示中最右边一个1)

    效果：

    lowbit(1110011000) ——> 1000

    实现：

    1
    2
    3
    4
    5
    首先，假设n的二进制是1110011000
    然后，对n取反，得到：~n = 0001100111
    接着，~n+1  ===>  0001101000
    紧接着，(~n + 1) & n ===> 0000001000 ===> 1000
    最后，由于-n = ~n + 1,所以lowbit就是：(-n) & n

    代码实现：

    1
    2
    3
    4
    int lowbit(int n)
    {
        return (-n) & n;
    }

    拓展

    1. 复杂度和1的个数有关和
    2. 可以快速求出来一个整数里面有多少个1
    3. 求n是2的整次方幂
      【释】：
      $2^n$      <==> 1 << n  
            **⬇**
      n & -n   <==>   n；

    反之， n & -n < n

原码、反码、补码

正数

原码，反码，补码均相等。

负数

  • 反码求法：
  1. 符号位不变。
  2. 其他位取反。
  • 补码求法：

1.符号位不变。
2.其他位取反。
3.最后一位加1。

例子

以123和-123为例：

  • [123] 原码：01111011。 反码：01111011。 补码：01111011。
  • [-123]原码：11111011。 反码：10000100。 补码：10000101。

二进制转换成10进制

  1. 如果为正数，则直接求即可
  2. 如果为负数，取反+1，然后求出数值前面加个负号。