|
|
51CTO旗下网站
|
|
移步端
  • 你说你会位运算,那你用位运算来解下八皇后问题吧

    位运算在生养或算法解题中并不常见,不过如果你用得好,可以达到事半功倍的功力,而且位运算用得好,也得以极大地提升性能。

    笔者:码海 来源:码海| 2020-03-25 10:44

    前言

    位运算在生养或算法解题中并不常见,不过如果你用得好,可以达到事半功倍的功力,而且位运算用得好,也得以极大地提升性能,如果在生养或面试中能收看使用位运算来解题,会让人眼前一亮,认为你还是有点逼格的,巧用位运算,不仅会提升性能,还会让代码的读报更好,到达四两拨千斤的功力,当日我们就来学学位运算在解题中的一些艺术,说到底会用位运算来看望怎么解八娘娘这道大 Boss 题,相信你看完肯定会有收获!

    本文将会从以下几个地方来讲学位运算

  • 什么是位运算,位运算常见操作
  • 位运算使用技巧简介
  • 巧用位运算解算法题
  • 什么是位运算,位运算常见操作

    在近代计算机中全方位的多寡在内存中都是以股份合作制存在的,位运算就是直接对整数在内存中的二进制位进行操作,出于位运算直接对内存数据进行操作,不要转成十进制,故此使用位运算的拍卖速度是很快之。

    举个简单的例证, 顶我们要计算 6 & 4 的结果,在做位运算的时节首先要把 6,4 转成股份合作制,下一场再做相应的位操作(与)。

    基本的位运算有与、或、异或、取反、左移、朔移这6种,介绍如下:

    & 与:只有当两位都是 1 时结果才是 1,否则为 0 。

          
    1.  0110 
    2. &   0100 
    3. ----------- 
    4.     0100 

    | 或:两位中只要有 1 位为 1 结果就是 1,两位都为 0 则结果为 0。

          
    1.  0110 
    2. &   0110 
    3. ----------- 
    4.     0110 

    ^ 异或:两个位相同则为 0,不同则为 1

          
    1.   0110 
    2. ^   0100 
    3. ----------- 
    4.     0010 

    ~ 取反:0 则成为 1,1 则成为 0

          
    1. ~   0110 
    2. ----------- 
    3.     1001 

    << 左移:向左进行运动操作,高位丢弃,低位补 0

          
    1. int a = 8; 
    2. a << 3; 
    3. 移步前:0000 0000 0000 0000 0000 0000 0000 1000 
    4. 移步后:0000 0000 0000 0000 0000 0000 0100 0000 

    >> 朔移:向右进行运动操作,对现代化符号数,高位补 0,对于有记号数,高位补符号位

          
    1. unsigned int a = 8; 
    2. a >> 3; 
    3. 移步前:0000 0000 0000 0000 0000 0000 0000 1000 
    4. 移步后:0000 0000 0000 0000 0000 0000 0000 0001 
    5.  
    6. int a = -8; 
    7. a >> 3; 
    8. 移步前:1111 1111 1111 1111 1111 1111 1111 1000 
    9. 移步后:1111 1111 1111 1111 1111 1111 1111 1111 

    位运算使用技巧简介

    然后我们就由浅入深地来学习一下用到位运算的这些黑科技

    1、 认清整型的奇偶性

    采用位运算操作如下

          
    1. if((x & 1) == 0) { 
    2.     // 偶数 
    3. else { 
    4.     // 奇数 

    其一例子相信大家都见过,只需判断整型的首要位是否是 1 即可,如果是说明是分数,否则是分数

    2、 认清第 n 位是否设置为 1

          
    1. if (x & (1<<n)) { 
    2.     // 先后 n 位设置为 1 
    3. else { 
    4.     // 先后 n 位设置为 1 

    在上例中我们判断第一位是否为 1,故此如果要认清第 n 位是否 1,只要把 1 左移 n 位再作与运算不就完了。

    3、名将先后 n 位设置为 1

          
    1. y = x | (1<<n) 

    思路同第二地,先把 1 移到第 n 位再作或运算,这样第 n 位就肯定为 1。

    4、名将先后 n 位设置为 0

          
    1. y = x & ~(1< 

    先将 1 东方移到 先后 n 位,再对他取反,此刻第 n 位为 0,其它位都为 1,这样与 x 房与运算后,x 的程序 n 位愿意定为 0。

    5名将先后 n 位的值取反

          
    1. y = x ^ (1< 

    咱们掌握异或操作是两指数的每一位相同,结果为 0,否则是 1,故此现在把 1 东方移到第 n 位,则如果 x 的程序 n 位为 1,两指数相同结果 0,如果 x 的程序 n 位为 0,两指数不相同,则为 1。来看个简单的例证

          
    1. 01110101 
    2.   00100000 
    3.   -------- 
    4.   01010101 

    如图示,先后五位刚好取反

    6、名将最右边的 1 设为 0

          
    1. y = x & (x-1) 

    如果说地方的 5 点技巧有点无聊,那次 6 条技巧确实很有趣,也是在 leetcode 经常出现的突破点,下文中多数习题都会用到这个知识点,必须要谨记!控制这个很重大,有啥用呢,比如我要统计 1 的用户数有几个,只要写个如下循环即可,不断地将 x 最右边的 1 置为 0,说到底当值为 0 时统计就结束了。

          
    1. count = 0   
    2. while(x) { 
    3.   x = x & (x - 1); 
    4.   count++; 

    先介绍这么多吧,如果大家对其它的位运算技巧感兴趣可以看看文末之参考链接

    巧用位运算解算法题

    然后我们看看位运算在书法题中的应用。

    1、高频面试题:老鼠试毒

    有 8 个一模一样的瓶子,其中有 7 瓶是一般的川,有一瓶是毒药。其它喝下毒药的古生物都会在一星期后死亡。如今,你只有 3 只小白鼠和一星期的年华,如何检验出哪个瓶子里有毒药?

    解题步骤如下:

    (1)把这 8 个瓶子从 0 到 7 拓展编号,用二进制表示如下

          
    1. 000 
    2. 001 
    3. 010 
    4. 011 
    5. 100 
    6. 101 
    7. 110 
    8. 111 

    (2)名将 0 到 7 编号中一言九鼎位为 1 的一切瓶子(即 1,3,5,7)的水混在总共给老鼠 1 吃,其次位值为 1 的一切瓶子(即2,3,6,7)的水混在总共给老鼠 2 吃, 先后三位值为 1 的一切瓶子(4,5,6,7)的水混在总共给老鼠 3 吃,如今假设老鼠 1,3 死了,这就是说有毒的瓶子编号中先后 1,3 位愿意定为 1,老鼠 2 没死,则有毒的瓶子编号中先后 2 位愿意定为 0,得到值 101 ,对应的号码是 5, 也就是第五瓶的川有毒。

    这道题及其相关的工种在面试中出现地比较频繁,比如我今天把 8 瓶水换成 1000 瓶,问你至少需要几只老鼠才能测出有毒的瓶子,有了上述的笔触相信应该不难,几只老鼠就相当于几个进制位,众目睽睽 2^10 = 1024 > 1000,即 10 只老鼠即可测出来。

    2、leetcode 232

    给定一个指数,认清它是否是可以用 2 的覆盖次方表示,可以返回 true,不可以返回 false,比如 8 = 2^3, 表明可以用 2 的覆盖次方表示,回到 true,9 不可以,故此返回 false。

    解题分析:这题常规解法是做个循环不断地乘以 2 ,瞧下是否等于给定的值,如果等于说明是 2 的覆盖次方,否则如果不断累乘 2 此后大于给定的值,表明不能用 2 的覆盖次方表示,时光复杂度是所做的累乘的用户数,即 2^n >= 给定的值中的 n。

    那只是有更快的做法呢?

    上文的介绍中其实我们已经埋下伏笔了,正确用 x & (x-1),第一我们要发现能用 2 的覆盖次方表示的股票数之性状:他的一切位中有且仅有一位为 1,如

          
    1. 00001        2^0 = 1 
    2. 00010        2^1 = 2 
    3. 00100        2^2 = 4 
    4. 01000        2^3 = 8 
    5. 10000        2^3 = 16 

    如图示,整整 2 的覆盖次方最多只有一位为 1

    了解了这一点, 咱们的笔触就简单了,出于符合 2 的覆盖次方的股票数只有一位为 1,x & (x-1) 是把最后一位 1 置为 0,故此只要做一次 x & (x-1) 运算,瞧他的值是否等于 0 即可,如果是 0 表明他可以用 2 的覆盖次方表示,否则不可以,代码如下:

          
    1. if(x&(x-1)) { //采用与运算判断一个指数是否是2的覆盖次方 
    2.     printf("%d不是2的覆盖次方!\n", num); 
    3. else { 
    4.     printf("%d是2的%d先后方!\n", num, log2(num)); 

    只用一行代码即可搞定,富有了很多!

    3、leetcode 232

    给定一个非负整数 num. 对于 0 ≤ i ≤ num 规模中的每个数字 i, 计算其二进制数中 1 的多少并将它们作为数组返回。步入: 5 进出口: [0,1,1,2,1,2]

    这题的正常化解法相信大家都能猜到,就是从 0 到 num 循环一遍,求出每个数字 i 官方 1 的多少。

    如果用位运算怎么做呢,先来看下解法,下一场我们再来分析为啥这样写,异常巧妙!

    Python 代码

          
    1. vector<int> countBits(int num) { 
    2.     vector<int> bits(num+1, 0); 
    3.     for (int i = 1; i<= num; i++) { 
    4.         bits[i] += bits[i & (i-1)] + 1; 
    5.     } 

    Java 代码

          
    1. public static int[] countBits(int num) { 
    2.     int[] bits = new int[num+1]; 
    3.     Arrays.fill(bits, 0); 
    4.  
    5.     for (int i = 1; i <= num; i++) { 
    6.         bits[i] = bits[i & (i-1)] + 1; 
    7.     } 
    8.     return bits; 

    最主要的编码看这一行

          
    1. bits[i] += bits[i & (i-1)] + 1; 

    这趟代码是哪意思呢,i & (i-1) 是把 i 的最终一个值为 1 的位设为 0,轻而易举发现整数「i & (i-1)」 官方 1 的用户数比 i 官方 1 的用户数少一个 ,故此要加 1(即 bits[i & (i-1)] + 1)。异常巧妙,这样从 1 起来走一遍循环即可,中间不要做其他针对变量 i 的 1 的底数的算计,只不过付出了一番 bits 数组的平价。此地也是采取了以空间换时间之思维。

    4、采取位运算来解八娘娘问题

    然后我们来看望终级 Boss 题,如何用位运算来解八娘娘问题,解题中采用到了特别多之位运算技巧,相信你学完会收获不少。

    在 8×8 格的围棋上布置八个皇后,使他不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有好多种摆法

    举个简单的下图所示的例证,如果在棋盘上放置一个皇后,则与这个皇后同一行,同一列,且皇后所在斜线经过的格子不能再放其他皇后。

    如图示,在其中任意一行放置一个皇后,则与此皇后同行,同列,同对角线的都不同意再放其他皇后,希冀中蓝色区块不同意放其他皇后。

    普通我们用回溯法解八娘娘。此地简单介绍一下啥是回首法。

    在重要列从南方到右先选择一个位置放置皇后,出于第一列放了皇后,其次列可放皇后的岗位受到了限制(下图蓝色区块表示对应行的格子不能放皇后)

    如图示,其次列放皇后的岗位只能从第三个格子开始选

    其次列我们选第三个格子放皇后,选完开始在先后三列选,先后三方可选的岗位也受到了举足轻重,二列皇后所放位置的影响

    如图示,先后三列只能从第五个格子开始放置皇后

    同理,先后三,四,五行都下南方到右选择符合规范的的格子放置皇后,选完后问题来了,先后六列所在行没有可选的岗位了!如图示

    怎么办呢,想起!重新摆放第五行的皇后,名将他放到第八格上

    重新摆放后发现第六列还是没有符合规范的格子,咋办,咱们掌握第六列可摆放皇后的格子受第五行影响,而第五行受第四列摆放皇后位置的影响之,故此回溯到第四列,名将皇后位置摆放到目前行的任何位置(先后七格),再接着往下放 5,6,7,8 列的皇后。。。,只要不满足条件,转移上一层的的尺度重新来,上一层调整后还是不符合规范,再调整上上层的。。。,调整完后重新往下递归选择,直到找到符合规范的,找到之后再在重要层换一个位置选皇后递归往基层选择执行,直到找到所有的解,这种不满足条件就回退上层调整再试的思维就是回首法,可以看出回溯法一般是用递归实现的。

    想起算法有诸多变种,此地我们着重介绍使用位运算的追思算法,他是全部解法中最便捷的!如果在面试中能利用位运算来解回溯算法,绝对会让面试官给你个大大的赞!

    然后是根本了,怎么用位运算来求解。

    在以上回溯法的剖析中,咱们不难发现,在八皇后问题中,题材的严重性是找到行可放皇后的格子。找到之后问题就解决了 90%,故此接下来我们就来看望怎么找这些可用之格子。

    假设我们要求解第三列可放皇后的格子(表明一二列的皇后已放好了)这就是说第三列可放皇后的岗位受到哪些条件的限制呢。众目睽睽在重要二列已放皇后的格子所在的进,东方斜线,朔斜线对应的方格都不能放皇后,如图示:

    咱们以 column 来记录所有上方行已放置的皇后导致当前行格子不可用之集聚,八方列如果放了皇后,则当前行格子对应的岗位为 1,否则为 0,同理,以 pie(撇,东方斜线) 记录所有已放置的皇后左斜方向导致当前行格子不可用之集聚, na(捺,朔斜线) 表示所有已放置的皇后右斜方向导致当前行不可用之集聚。则对于第三列来说我们有:

          
    1. column = 10010000 (上图中的第一个图,先后 1,4 趟放了皇后,故此 1,4 位置为 1,其它位置为 0) 
    2. pie = 00100000 (上图中的第二个图,东方斜线经过第三列的程序三个方格,所以第三位为 1) 
    3. na = 00101000 (上图中的第三个图,朔斜线经过第三列的程序三, 五个方格,所以第三,五位为 1) 

    名将这三个变量作或运算得到结果如下

          
    1.  10010000 
    2. |   00100000 
    3. |   00101000 
    4. ----------------------- 
    5.     10111000 

    具体地说对于第三层来说第 1,3,4,5 个格子不能放皇后。如图示

    于是乎可知 column | pie | na 得到的结果中值为 0 的代表当前行对应的格子可放皇后, 1 代表不能放,但我们想改成 1 代表格子可放皇后, 0 代表不可放皇后,毕竟这样更符合我们的思辨方式,怎么办,取反不就行了,于是乎我们有~(column| pie | na)。

    题材来了,这样取反是有问题的,因为这三个变量都是定义之 int 型,为 32 位,取反之后高位的 0 全方位变成了 1,而我辈只想保留低 8 位(因为是 8 皇后),想把高位都置为 0,怎么办,此地就要用到位运算的黑暗科技了

          
    1. ~(column | pie | na) & ((1 << 8)-1) 

    后面的的 ((1<< 8) -1) 表示先把 1 往左移 8 位,值为 100000000,再减 1 ,则低 8 位一体为 1,高位全部为 0!(即 0011111111)再作与运算,即可保留低 8 位,剔除高位。

    费了这么大的力气,咱们终于把目前行可放皇后的格子都找出来了(所有位值为 1 的格子可放置皇后)。然后我们只要做个循环,遍历所有位为 1 的格子,每次取出可用格子放上皇后,再找下一层可放置皇后的格子,依此递归下去即可,直到所有行都遍历完毕(递归的终止条件)。

    还有一个问题,已知当前行的 column,pie,na,怎么确定下一行的 column,pie,na 的值(毕竟选完当前行的皇后后,要肯定下一行的商用格子,而从一行的商用格子依赖于 column,pie,na 的值)

    上文可知,咱们已经选出了现阶段行可用之格子(应当位为 1 对应的格子可用),假设我们在眼前行选择了其中一个格子来放置皇后,此位置记为 p(如果是目前行的最终一个格子最后一个格子,则值为 1,如果放在倒数第二个,值为 10,数第三个则为 100,举一反三),则对于下一行来说,众目睽睽 column = column | p

    这就是说 pie 呢,精心看下图,众目睽睽应该为 (pie | p) << 1, 东方斜线往下一行的格子延展时,方便于左移一位,

    如图示:从一行的 pie 众目睽睽为 (pie | p) << 1。

    同理 从一行的 na 为 (na | p) >> 1。

    有了上述详细地剖析,咱们就足以写出伪代码了

          
    1. void queenSettle(row, colomn,pie,na) { 
    2.     N = 8; // 8皇后 
    3.     if (row >= N) { 
    4.         // 遍历到最后一行说明已经找到符合的尺度了 
    5.         count++;return 
    6.     } 
    7.  
    8.         // 取出当前行可放置皇后的格子 
    9.     bits = (~(colomn|pie|na)) & ((1 << N)-1) 
    10.  
    11.     while(bits > 0) { 
    12.             // 每次从目前行可用之格子中取出最右边位为 1 的格子放置皇后 
    13.             p = bits & -bits 
    14.  
    15.             // 紧接着在下一行继续放皇后 
    16.             queenSettle(row+1, colomn | p, (pie|p) << 1, (na | p) >> 1) 
    17.  
    18.             // 眼前行最右边格子已经选完了,名将他置成 0,代表这个格子已遍历过 
    19.             bits = bits & (bits-1) 
    20.     } 

    一开始传入 queenSettle(0,0,0,0) 这样即可得到最终的解。伪代码写得很清楚了,相信用相关语言不困难实现,此地就留给大家作个练习吧。

    总结

    本文带大家由浅入深地做到了位运算的读书,控制好位运算不仅仅是为了提升逼格,还能极大地提升效率,位运算也常见地应用于代码编写中,采用得当能极大地简化代码,且可读性更好,限于篇幅关系,此地不进行,大家如有兴趣可参照文末的链接。

    如有帮助,迎接大家关心公号哦。后将会讲解大量算法的解答思路,瞩望我们一起攻克算法难题!

    【编纂推荐】

    1. Redis 敢在线上做Keys正则匹配操作!你可以离职了!
    2. Python借鉴MySQL存储,该署你都会了吗?
    3. 用Python贯彻磁盘IO借鉴全攻略,让数据流动起来!
    4. 控制这些Redis技术,让你掌控住千亿数目量
    【义务编辑: 武晓燕 TEL:(010)68476606】

    点赞 0
  • 位运算  借鉴  技术
  • 分享:
    大家都在看
    猜你喜欢
  • 24H热文
    一周话题
    每月获赞
  • 简直不要太硬了!一文带你彻底理解文件系统ECC内存和一般内存有什么区别,有必不可少买ECC内存吗恢复时间目标(RTO)和恢复点目标(RPO)的了解差异此地帮你总结了一下Linux从查看内存使用状态之多种艺术~Redis集群的5种使用办法,各自优缺点分析Redis内存淘汰策略,瞧这一篇就够了!Redis官方8种多少结构的底色数据结构源码详解云存储技术之规律是什么?百度网盘技术原理分析
  • ECC内存和一般内存有什么区别,有必不可少买ECC内存吗此地帮你总结了一下Linux从查看内存使用状态之多种艺术~恢复时间目标(RTO)和恢复点目标(RPO)的了解差异简直不要太硬了!一文带你彻底理解文件系统Redis集群的5种使用办法,各自优缺点分析Redis内存淘汰策略,瞧这一篇就够了!Redis官方8种多少结构的底色数据结构源码详解每个程序员都不能不掌握的 8 种多少结构!
  • ECC内存和一般内存有什么区别,有必不可少买ECC内存吗此地帮你总结了一下Linux从查看内存使用状态之多种艺术~恢复时间目标(RTO)和恢复点目标(RPO)的了解差异Redis集群的5种使用办法,各自优缺点分析搞懂这些Redis知识点,吊打面试官!Redis内存淘汰策略,瞧这一篇就够了!云存储技术之规律是什么?百度网盘技术原理分析Redis官方8种多少结构的底色数据结构源码详解
  • 订阅专栏+更多

     迅速无敌之 Gitlab CI 接轨集成

    迅速无敌之 Gitlab CI 接轨集成

    打破运维与科研壁垒
    共5章 | KaliArch

    74人口订阅学习

    秒杀高并发白话实战

    秒杀高并发白话实战

    主流高并发架构
    共15章 | 51CTO崔皓

    59人口订阅学习

    网络排障一点通

    网络排障一点通

    网络排障及优化调整案例
    共20章 | 捷哥CCIE

    465人口订阅学习

    订阅51CTO邮刊

    点击这里查看样刊

    订阅51CTO邮刊

    51CTO劳务号

    51CTO官微

    1. &lt;menu id="e1158e6e"&gt;&lt;/menu&gt;
      1.