例会笔记(5) 位运算&STL

ゝ一世哀愁。 2022-04-24 12:20 123阅读 0赞

> 位操作是程序设计中对位模式或二进制数的一元和二元操作。在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。在现代架构中，情况并非如此：位运算的运算速度通常与加法运算相同（仍然快于乘法运算）。 （Wikipedia）

**分类**

&
    按位与
    如果两个相应的二进制位都为1，则该位的结果值为1，否则为0
    |
    按位或
    两个相应的二进制位中只要有一个为1，该位的结果值为1
    ^
    按位异或
    若参加运算的两个二进制位值相同则为0，否则为1
    ~
    取反
    ~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1
    <<
    左移
    用来将一个数的各二进制位全部左移N位，右补0
    >>
    右移
    将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数， 高位补0

**性质**

0^x = x;
    ^ 满足交换和结合律
    x^x = 0;

**举栗**

*  验证一个数的奇偶
 *  统计二进制中1的个数
 *  汉明距离（统计两个二进制数中相同为不同值的位数）
 *  看一个数是否是2的幂（4的幂）
 *  出现次数是奇数次的数的异或
 *  快速求幂（数值快速幂 矩阵快速幂）
 *  状压dp

**例题**

**没有交集的单词**  
**[https://leetcode-cn.com/problems/maximum-product-of-word-lengths/][https_leetcode-cn.com_problems_maximum-product-of-word-lengths]**

**快速幂**  
[https://blog.csdn.net/L1558198727/article/details/80944597][https_blog.csdn.net_L1558198727_article_details_80944597]  
解释：例如  
 x 10 = x ( 1010 ) 2 1010 = 1000 + 000 + 10 + 0 x 1010 = x 1000 ∗ x 10 x^\{10\} = x^\{(1010)\_\{2\}\} \\\\ 1010 = 1000 + 000+ 10 + 0\\\\ x^\{1010\} = x^\{1000\} \* x^\{10\}\\\\ x10=x(1010)21010=1000\+000\+10\+0x1010=x1000∗x10

**dp介绍**  
**基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解**  
**爬楼梯**  
**[https://leetcode-cn.com/problems/climbing-stairs/][https_leetcode-cn.com_problems_climbing-stairs]**  
**状压dp**  
**[http://www.bnuoj.com/problem\_show.php?pid=12976][http_www.bnuoj.com_problem_show.php_pid_12976]**  
**[https://blog.csdn.net/L1558198727/article/details/88887104][https_blog.csdn.net_L1558198727_article_details_88887104]**

**STL**  
**C++ STL（标准模板库）是一套功能强大的 C++ 模板类**  
**东西太多了，只能介绍一小部分，大家有时间进一步学习吧**

**容器**

*  vector 变长数组
 *  set 集合 可以用来去重
 *  map 映射
 *  string 字符串类 丰富的字符串操作函数
 *  list 链表

**库函数**

sort 可以自定义排序依据，用来排结构体
     next_permutation 返回下一个排列
     prev_permutation 返回上一个排列
     make_heap 建立堆 最大最小堆看传入的函数

**[https://leetcode-cn.com/problems/two-sum/][https_leetcode-cn.com_problems_two-sum]**  
**枚举  
双指针  
哈希**

**强大的map**  
**[https://leetcode-cn.com/problems/group-anagrams/][https_leetcode-cn.com_problems_group-anagrams]**

**map是怎么实现的？**

**哈希：[https://blog.csdn.net/qq\_37954088/article/details/79692032][https_blog.csdn.net_qq_37954088_article_details_79692032]**

[https_leetcode-cn.com_problems_maximum-product-of-word-lengths]: https://leetcode-cn.com/problems/maximum-product-of-word-lengths/
[https_blog.csdn.net_L1558198727_article_details_80944597]: https://blog.csdn.net/L1558198727/article/details/80944597
[https_leetcode-cn.com_problems_climbing-stairs]: https://leetcode-cn.com/problems/climbing-stairs/
[http_www.bnuoj.com_problem_show.php_pid_12976]: http://www.bnuoj.com/problem_show.php?pid=12976
[https_blog.csdn.net_L1558198727_article_details_88887104]: https://blog.csdn.net/L1558198727/article/details/88887104
[https_leetcode-cn.com_problems_two-sum]: https://leetcode-cn.com/problems/two-sum/
[https_leetcode-cn.com_problems_group-anagrams]: https://leetcode-cn.com/problems/group-anagrams/
[https_blog.csdn.net_qq_37954088_article_details_79692032]: https://blog.csdn.net/qq_37954088/article/details/79692032