【ZJOI2014 Day1 课件】位运算及其应用

1、位运算及其应用1Q&AQ：你是谁，我怎么没听说过？A：即将退役的酱油选手一枚，你们不认识也很正常Q：既然你这么弱，为什么还要来讲课？A：我受买老师的命令来基础知识。显然买老师不屑于来讲NOIp难度的东西。2Q&AQ：位运算什么的我十年前就会了！A：鉴于本节课内容十分简单，您可以选择在这里睡觉或者回宾馆睡觉，要是因为这样一节水课影响了您的休息就不好了。祝您进队。3结构基本运算二进制位的修改和查询将整数用作集合其他应用例题4约定约定二进制最高位为最左边，最低位为最右边，最低位标号为第0位程序均以C+语言描述，所涉及的语言细节、内建函数等均以GNU C+（GCC编译器）为标准汇编指x86汇编5基本运

2、算6与、或、非和异或逻辑运算0000001011100111111001107与、或、非和异或位运算逻辑运算在整数上的扩展结果的每个二进制位等于运算数的对应二进制位进行相应逻辑运算的结果带符号整数符号位？一视同仁交换律、结合律（与、或、异或）8移位运算逻辑移位算数移位循环移位带进位循环移位四种9逻辑移位逻辑左移shl x y把x的每个二进制位向左移动y位，移动造成的最右边的空位由0补足，最左边的数溢出。逻辑右移shr x y把x的每个二进制位向右移动y位，移动造成的最左边的空位由0补足，最右边的数溢出。10算术移位算术左移sal x y与逻辑左移完全相同算术右移sar x y与逻辑右移大体相同

3、，唯一的区别在于移动造成的最左边的空位由符号位（最高位）补足而不是由0补足。11循环移位循环左移rol x y把x的每个二进制位向左移动y位，移动造成的最右边的空位由最左边溢出的位补足。循环右移ror x y把x 的每个二进制位向右移动y位，移动造成的最左边的空位由最右边溢出的位补足。12带进位循环移位不搞汇编就别管这个了_13注意事项14数学意义15C/C+中的移位运算无符号整数的移位使用逻辑移位，有符号整数的移位使用算术移位。无论是无符号整数还是带符号整数，我们都可以放心的使用左移和右移来代替乘以二的幂或除以二的幂的操作。没有专门的对带符号整数进行逻辑右移的运算符我们可以通过强制类型转换将

4、它转换成无符号整数后再进行运算。16C/C+中的移位运算没有提供循环移位操作符通过其他运算的组合来实现应用于32位整数的两个例子：(x (32 - y)(x y) | (x 1) + (x & 0 x55555555u);x-= (x & 0 xAAAAAAAAu) 1);31求1的个数 x = (x & 0 xAAAAAAAAu) + (x & 0 x55555555u)ans = (x & 0 xAAAAAAAAu) 1) + (x & 0 x55555555u)两者作差x - ans = (x & 0 xAAAAAAAAu) 1)ans = x - (x & 0 xAAAAAAAAu)

5、1)32求1的个数第二个区别作用：将4对4 bit整数相加每个整数最大只可能是4，两个数相加的结果也能在4 bit的空间存下(x 4) + x可以正确地依次求出第0个数加第1个数，第1个数加第2 个数，第2个数加第3个数从中取出我们需要的结果。x = (x & 0 xF0F0F0F0u) 4) + (x & 0 x0F0F0F0Fu);x = (x 4) + x) & 0 x0F0F0F0Fu;33求1的个数Keep going！34求1的个数发生了什么？令x = (a24)+(b16)+(c8)+(d 24;35求1的个数 x * 0 x01010101=(x24)+(x16)+(x8)+(

6、x0)=(a48)+(b40)+(c32)+(d24)+ (a40)+(b32)+(c24)+(d16)+ (a32)+(b24)+(c16)+(d 8)+ (a24)+(b16)+(c 8)+(d 0)=(a) 48) + (a+b) 40) + (a+b+c) 32) + (a+b+c+d) 24) + (b+c+d) 16) + (c+d) 8 ) + (d) 0 )36求1的个数前三项：溢出后三项：考虑a,b,c,d的实际意义，后三项之和小于1 24，不影响前8位前八位即为a+b+c+d37求1的个数38求1的个数分段预处理所有16位整数的答案，询问时将被询问的整数拆成高16位和低16

7、位分别计算答案39求1的个数GCC内建函数int _builtin_popcount (unsigned int x);对于支持SSE4.2的机器，如果在编译时开启相应开关，则该函数会被翻译成汇编指令popcnt，否则使用查表法计算40翻转位序41翻转位序分治将整个数分割成两个部分，分别翻转这两个部分，再将这两个部分对调借由位运算，每一层的工作并行完成42翻转位序43翻转位序44翻转位序45求前缀/后缀0的个数以求前缀0为例二分查找46求前缀/后缀0的个数第一步，判断高16位是否为空若是，则高16位必然均为前缀0，我们给答案加上16，并在第0至15位上继续二分若不是，则前缀0只出现在则高16位

8、上，我们将它们右移到低16位上以便对它继续二分第二步，判断此时的高8位是否均为前缀0，并选择一边继续二分下去。47求前缀/后缀0的个数同样的思路求解后缀0个数48求前缀/后缀0的个数49求前缀/后缀0的个数50求前缀/后缀0的个数内建函数int _builtin_clz (unsigned int x);求解前缀0bsr (Bit Scan Reverse) + xorint _builtin_ctz (unsigned int x);求解后缀0bsf (Bit Scan Forward)若参数x为0，返回值是未定义51效率REVERSE暴力2247分治328查表86LEADINGZEROS暴

9、力699二分278查表61系统函数119POPCOUNT暴力1042分治319优化1270优化2211查表89SSE4.286非SSE4.287852求第k个1的位置53求第k个1的位置54求第k个1的位置不利用cnt_tbl二分时查询的区间正好是分治时求过的区间利用分治的中间值55求第k个1的位置56提取末尾连续的157提取lowbit58遍历所有1不断求lowbit并将它从原数中删去（异或）若需要用到这个1所在的位置转化为求后缀0个数59将整数用作集合60将整数用作集合61将整数用作集合62将整数用作集合63交集64并集65补集66差集67统计元素个数68遍历集合元素69求集合中第k小元素

10、70求集合中大于x的最小元素71将集合中每个元素加上/减去x72枚举子集73枚举k个元素的子集74Bitset的扩展原因求第k小太慢！求下一个元素太慢！方式Bitset+线段树Bitset线段树75其他应用搞笑的搞笑的76判断奇偶性77乘以或除以二的幂左移、右移78对二的幂取模79前缀0个数80交换两个数81绝对值82比较两个数是否相等异或是否为083比较两个数的大小84求两数较小值/较大值85选择86例题87筷子88筷子将所有数异或即可异或的交换律、结合律从每个二进制位的角度考虑8990搜索每行只能放一个皇后依次枚举每行放在那里同列、同对角线放过的位置不能放9192最小斯坦纳树93最小斯坦纳

11、树94抓企鹅Time Limit: 2 s95抓企鹅Time Limit: 2 s96Summer EarningsTime Limit: 9 s97Summer EarningsTime Limit: 9 s98Quick TortoiseTime Limit: 3 s99Quick TortoiseTime Limit: 3 s100Quick TortoiseTime Limit: 3 s101Robot in BasementTime Limit: 4 s102Robot in BasementTime Limit: 4 s103Robot in BasementTime Limit: 4 s104Bags and CoinsTime Limit: 2.5 s105Bags and CoinsTime Limit: 2.5 s106Inna and Binary LogicTime Limit: 3 s107Inna and Binary LogicTime Limit: 3 s108Inna and Binary LogicTime Limit: 3 s109FriendsTime