📄 位运算简介及实用技巧（三）：进阶篇(2).htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0047)http://www.matrix67.com/blog/article.asp?id=314 -->
<HTML lang=UTF-8 xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>位运算简介及实用技巧（三）：进阶篇(2) - Matrix67: My Blog</TITLE>
<META http-equiv=Content-Type content="text/html; charset=UTF-8">
<META http-equiv=Content-Language content=UTF-8>
<META content=all name=robots>
<META content=matrix67@tom.com,Matrix67 name=author>
<META content="PJBlog2 CopyRight 2005" name=Copyright>
<META
content=matrix67,PJBlog,blog,博客,OI,OIer,NOI,NOIp,Pascal,信息学,算法,数据结构,数学,趣题,美剧,电影
name=keywords>
<META
content="Matrix67: My Blog - 50% Informatics, 50% Mathematics, and 50% Imagination"
name=description><LINK
title="订阅 Matrix67: My Blog - Program Impossible 所有文章(rss2)"
href="http://www.matrix67.com/blog/feed.asp?cateID=6" type=application/rss+xml
rel=alternate><LINK title="订阅 Matrix67: My Blog - Program Impossible 所有文章(atom)"
href="http://www.matrix67.com/blog/atom.asp?cateID=6" type=application/atom+xml
rel=alternate><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（三）：进阶篇(2).files/global.css" type=text/css rel=stylesheet><!--全局样式表--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（三）：进阶篇(2).files/layout.css" type=text/css rel=stylesheet><!--层次样式表--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（三）：进阶篇(2).files/typography.css" type=text/css rel=stylesheet><!--局部样式表--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（三）：进阶篇(2).files/link.css" type=text/css rel=stylesheet><!--超链接样式表--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（三）：进阶篇(2).files/editor.css" type=text/css rel=stylesheet><!--UBB编辑器代码--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（三）：进阶篇(2).files/highlight.css" type=text/css
rel=stylesheet><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（三）：进阶篇(2).files/bt.css" type=text/css rel=stylesheet><LINK
href="favicon.ico" type=image/x-icon rel=icon><LINK href="favicon.ico"
type=image/x-icon rel="shortcut icon">
<SCRIPT src="位运算简介及实用技巧（三）：进阶篇(2).files/common.js"
type=text/javascript></SCRIPT>
<SCRIPT src="位运算简介及实用技巧（三）：进阶篇(2).files/BubbleTooltips.js"
type=text/javascript></SCRIPT>
<META content="MSHTML 6.00.2900.3268" name=GENERATOR></HEAD>
<BODY onkeydown=PressKey() onload=initJS()><A accessKey=i
href="http://www.matrix67.com/blog/default.asp"></A><A accessKey=z
href="javascript:history.go(-1)"></A>
<DIV id=container><!--顶部-->
<DIV id=header>
<DIV id=blogname>Matrix67: My Blog
<DIV id=blogTitle>50% Informatics, 50% Mathematics, and 50%
Imagination</DIV></DIV>
<DIV id=menu>
<DIV id=Left></DIV>
<DIV id=Right></DIV>
<UL>
<LI class=menuL></LI>
<LI><A class=menuA title=日志首页
href="http://www.matrix67.com/blog/default.asp">Index</A></LI>
<LI class=menuDiv></LI>
<LI><A class=menuA title=标签云集
href="http://www.matrix67.com/blog/tag.asp">TagsCloud</A></LI>
<LI class=menuDiv></LI>
<LI><A class=menuA title=个人档案
href="http://www.matrix67.com/blog/LoadMod.asp?plugins=AboutMeForPJBlog">Profile</A></LI>
<LI class=menuDiv></LI>
<LI><A class=menuA title=留言板
href="http://www.matrix67.com/blog/LoadMod.asp?plugins=GuestBookForPJBlog">GuestBook</A></LI>
<LI class=menuDiv></LI>
<LI><A class=menuA title=讨论区
href="http://www.matrix67.com/blog/discuss.asp?action=index">Discuss(beta)</A></LI>
<LI class=menuR></LI></UL></DIV></DIV><!--内容-->
<DIV id=Tbody>
<DIV id=mainContent>
<DIV id=innermainContent>
<DIV id=mainContent-topimg></DIV>
<DIV class=content-width id=Content_ContentList><A accessKey=B
href="http://www.matrix67.com/blog/article.asp?id=314#body" name=body></A>
<DIV class=pageContent>
<DIV style="FLOAT: right; WIDTH: auto"><A title=订阅所有日志 accessKey=F
href="http://www.matrix67.com/blog/feed.asp?cateID=6" target=_blank><IMG
style="MARGIN-BOTTOM: -3px" alt=订阅所有日志 src="位运算简介及实用技巧（三）：进阶篇(2).files/rss.png"
border=0> 订阅</A> | <A title="上一篇日志: 第300篇日志：祝福所有NOI选手" accessKey=,
href="http://www.matrix67.com/blog/article.asp?id=313"><IMG alt=""
src="位运算简介及实用技巧（三）：进阶篇(2).files/Cprevious.gif" border=0>上一篇</A> | <A
title="下一篇日志: CAN YOU FIND THE HIDDEN TIGER" accessKey=.
href="http://www.matrix67.com/blog/article.asp?id=315"><IMG alt=""
src="位运算简介及实用技巧（三）：进阶篇(2).files/Cnext.gif" border=0>下一篇</A> </DIV><IMG
style="MARGIN: 0px 2px -4px 0px" alt="" src="位运算简介及实用技巧（三）：进阶篇(2).files/24.gif">
<STRONG><A title="查看所有Program Impossible的日志"
href="http://www.matrix67.com/blog/default.asp?cateID=6">Program
Impossible</A></STRONG> </DIV>
<DIV class=Content>
<DIV class=Content-top>
<DIV class=ContentLeft></DIV>
<DIV class=ContentRight></DIV>
<H1 class=ContentTitle><STRONG>位运算简介及实用技巧（三）：进阶篇(2)</STRONG></H1>
<H2 class=ContentAuthor>作者:matrix67 日期:2007-07-26</H2></DIV>
<DIV class=Content-Info>
<DIV class=InfoOther>字体大小: <A accessKey=1
href="javascript:SetFont('12px')">小</A> <A accessKey=2
href="javascript:SetFont('14px')">中</A> <A accessKey=3
href="javascript:SetFont('16px')">大</A></DIV>
<DIV class=InfoAuthor><IMG style="MARGIN: 0px 2px -6px 0px" alt=""
src="位运算简介及实用技巧（三）：进阶篇(2).files/hn2_sunny.gif"><IMG alt=""
src="位运算简介及实用技巧（三）：进阶篇(2).files/hn2_t_sunny.gif"> <IMG
style="MARGIN: 0px 2px -1px 0px" alt=""
src="位运算简介及实用技巧（三）：进阶篇(2).files/level5.gif"> | 本文内容遵从<A
href="http://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh"
target=_blank>CC版权协议</A> 转载请注明出自matrix67.com </DIV></DIV>
<DIV class=Content-body
id=logPanel>今天我们来看两个稍微复杂一点的例子。<BR><BR><STRONG>n皇后问题位运算版</STRONG><BR> n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1
shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。<BR>
<DIV class=UBBPanel>
<DIV class=UBBTitle><IMG style="MARGIN: 0px 2px -3px 0px" alt=程序代码
src="位运算简介及实用技巧（三）：进阶篇(2).files/quote.gif"> 程序代码</DIV>
<DIV class=UBBContent><PRE><CODE class=pascal>procedure test(row,ld,rd:longint);<BR>var<BR> pos,p:longint;<BR>begin<BR><BR>{ 1} if row<>upperlim then<BR>{ 2} begin<BR>{ 3} pos:=upperlim and not (row or ld or rd);<BR>{ 4} while pos<>0 do<BR>{ 5} begin<BR>{ 6} p:=pos and -pos;<BR>{ 7} pos:=pos-p;<BR>{ 8} test(row+p,(ld+p)shl 1,(rd+p)shr 1);<BR>{ 9} end;<BR>{10} end<BR>{11} else inc(sum);<BR><BR>end;</CODE></PRE></DIV></DIV><BR> 乍一看似乎完全摸不着头脑，实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟，实在没研究出来再看下面的解说。<BR><BR><IMG
alt="" src="位运算简介及实用技巧（三）：进阶篇(2).files/200707261.gif" border=0> <IMG
alt="" src="位运算简介及实用技巧（三）：进阶篇(2).files/200707262.gif"
border=0><BR> 和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于not
a + 1，这里的代码第6行就相当于pos and (not pos +
1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。<BR><BR> ~~~~====~~~~=====
华丽的分割线
=====~~~~====~~~~<BR><BR><STRONG>Gray码</STRONG><BR> 假如我有4个潜在的GF，我需要决定最终到底和谁在一起。一个简单的办法就是，依次和每个MM交往一段时间，最后选择给我带来的“满意度”最大的MM。但看了<A
href="http://tianyi.yo2.cn/go/89403.html"
target=_blank>dd牛的理论</A>后，事情开始变得复杂了：我可以选择和多个MM在一起。这样，需要考核的状态变成了2^4=16种（当然包括0000这一状态，因为我有可能是玻璃）。现在的问题就是，我应该用什么顺序来遍历这16种状态呢？<BR> 传统的做法是，用二进制数的顺序来遍历所有可能的组合。也就是说，我需要以0000->0001->0010->0011->0100->...->1111这样的顺序对每种状态进行测试。这个顺序很不科学，很多时候状态的转移都很耗时。比如从0111到1000时我需要暂时甩掉当前所有的3个MM，然后去把第4个MM。同时改变所有MM与我的关系是一件何等巨大的工程啊。因此，我希望知道，是否有一种方法可以使得，从没有MM这一状态出发，每次只改变我和一个MM的关系（追或者甩），15次操作后恰好遍历完所有可能的组合（最终状态不一定是1111）。大家自己先试一试看行不行。<BR> 解决这个问题的方法很巧妙。我们来说明，假如我们已经知道了n=2时的合法遍历顺序，我们如何得到n=3的遍历顺序。显然，n=2的遍历顺序如下：<BR><BR>00<BR>01<BR>11<BR>10<BR><BR> 你可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态，其中前面4个把n=2的遍历顺序照搬下来，然后把它们对称翻折下去并在最前面加上1作为后面4个状态：<BR><BR><SPAN
style="COLOR: blue">0</SPAN><SPAN style="COLOR: red">00</SPAN><BR><SPAN
style="COLOR: blue">0</SPAN><SPAN style="COLOR: red">01</SPAN><BR><SPAN
style="COLOR: blue">0</SPAN><SPAN style="COLOR: red">11</SPAN><BR><SPAN
style="COLOR: blue">0</SPAN><SPAN
style="COLOR: red">10</SPAN> ↑<BR>--------<BR><SPAN
style="COLOR: blue">1</SPAN><SPAN
style="COLOR: red">10</SPAN> ↓<BR><SPAN
style="COLOR: blue">1</SPAN><SPAN style="COLOR: red">11</SPAN><BR><SPAN
style="COLOR: blue">1</SPAN><SPAN style="COLOR: red">01</SPAN><BR><SPAN
style="COLOR: blue">1</SPAN><SPAN
style="COLOR: red">00</SPAN><BR><BR> 用这种方法得到的遍历顺序显然符合要求。首先，上面8个状态恰好是n=3时的所有8种组合，因为它们是在n=2的全部四种组合的基础上考虑选不选第3个元素所得到的。然后我们看到，后面一半的状态应该和前面一半一样满足“相邻状态间仅一位不同”的限制，而“镜面”处则是最前面那一位数不同。再次翻折三阶遍历顺序，我们就得到了刚才的问题的答案：<BR><BR>0000<BR>0001<BR>0011<BR>0010<BR>0110<BR>0111<BR>0101<BR>0100<BR>1100<BR>1101<BR>1111<BR>1110<BR>1010<BR>1011<BR>1001<BR>1000<BR><BR> 这种遍历顺序作为一种编码方式存在，叫做Gray码（写个中文让蜘蛛来抓：格雷码）。它的应用范围很广。比如，n阶的Gray码相当于在n维立方体上的Hamilton回路，因为沿着立方体上的边走一步，n维坐标中只会有一个值改变。再比如，Gray码和Hanoi塔问题等价。Gray码改变的是第几个数，Hanoi塔就该移动哪个盘子。比如，3阶的Gray码每次改变的元素所在位置依次为1-2-1-3-1-2-1，这正好是3阶Hanoi塔每次移动盘子编号。如果我们可以快速求出Gray码的第n个数是多少，我们就可以输出任意步数后Hanoi塔的移动步骤。现在我告诉你，Gray码的第n个数（从0算起）是n
xor (n shr
1)，你能想出来这是为什么吗？先自己想想吧。<BR><BR> 下面我们把二进制数和Gray码都写在下面，可以看到左边的数异或自身右移的结果就等于右边的数。<BR><BR><SPAN
style="FONT-FAMILY: 宋体">二进制数 Gray码<BR>
000 000<BR>
001 001<BR>
010 011<BR>
011 010<BR>
100 110<BR>
101 111<BR>
110 101<BR>
111
100</SPAN><BR><BR> 从二进制数的角度看，“镜像”位置上的数即是对原数进行not运算后的结果。比如，第3个数010和倒数第3个数101的每一位都正好相反。假设这两个数分别为x和y，那么x
xor (x shr 1)和y xor (y shr
1)的结果只有一点不同：后者的首位是1，前者的首位是0。而这正好是Gray码的生成方法。这就说明了，Gray码的第n个数确实是n xor (n shr
1)。<BR><BR> 今年四月份<A
href="http://failedshuo.spaces.live.com/" target=_blank>mashuo</A>给我看了<A
href="http://acm.sgu.ru/problem.php?contest=0&problem=249"
target=_blank>这道题</A>，是二维意义上的Gray码。题目大意是说，把0到2^(n+m)-1的数写成2^n *
2^m的矩阵，使得位置相邻两数的二进制表示只有一位之差。答案其实很简单，所有数都是由m位的Gray码和n位Gray码拼接而成，需要用左移操作和or运算完成。完整的代码如下：<BR>
<DIV class=UBBPanel>
<DIV class=UBBTitle><IMG style="MARGIN: 0px 2px -3px 0px" alt=程序代码
src="位运算简介及实用技巧（三）：进阶篇(2).files/quote.gif"> 程序代码</DIV>
<DIV class=UBBContent><PRE><CODE class=pascal>var<BR> x,y,m,n,u:longint;<BR>begin<BR> readln(m,n);<BR> for x:=0 to 1 shl m-1 do begin<BR> u:=(x xor (x shr 1)) shl n; //输出数的左边是一个m位的Gray码<BR> for y:=0 to 1 shl n-1 do<BR> write(u or (y xor (y shr 1)),' '); //并上一个n位Gray码<BR> writeln;<BR> end;<BR>end.</CODE></PRE></DIV></DIV><BR><BR>Matrix67原创<BR>转贴请注明出处
<BR><BR><BR></DIV>
<SCRIPT type=text/javascript><!--google_ad_client = "pub-8918918108662869";google_ad_width = 728;google_ad_height = 90;google_ad_format = "728x90_as";google_ad_type = "text_image";google_ad_channel = "";google_color_border = "CCCCCC";google_color_bg = "F3F3F3";google_color_link = "6060FF";google_color_text = "292929";google_color_url = "000000";//--></SCRIPT>
<SCRIPT src="位运算简介及实用技巧（三）：进阶篇(2).files/show_ads.js"
type=text/javascript></SCRIPT>
<DIV class=Content-body><IMG style="MARGIN: 0px 2px -4px 0px" alt=""
src="位运算简介及实用技巧（三）：进阶篇(2).files/icon_trackback.gif"><STRONG>引用通告地址:</STRONG>
http://www.matrix67.com/blog/trackback.asp?tbID=JOFOFRD8&key=JOKOJQDPMMDQM8<BR><IMG
style="MARGIN: 4px 2px -4px 0px" alt=""
src="位运算简介及实用技巧（三）：进阶篇(2).files/tag.gif"><STRONG>Tags:</STRONG> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E4%BD%8D%E8%BF%90%E7%AE%97">位运算</A><A
style="DISPLAY: none" href="http://technorati.com/tag/位运算" rel=tag>位运算</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E4%BA%8C%E8%BF%9B%E5%88%B6">二进制</A><A
style="DISPLAY: none" href="http://technorati.com/tag/二进制" rel=tag>二进制</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=Pascal%E8%AF%AD%E8%A8%80">Pascal语言</A><A
style="DISPLAY: none" href="http://technorati.com/tag/Pascal语言"
rel=tag>Pascal语言</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E4%BB%A3%E7%A0%81">代码</A><A
style="DISPLAY: none" href="http://technorati.com/tag/代码" rel=tag>代码</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E7%AE%97%E6%B3%95">算法</A><A
style="DISPLAY: none" href="http://technorati.com/tag/算法" rel=tag>算法</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E9%80%92%E5%BD%92">递归</A><A
style="DISPLAY: none" href="http://technorati.com/tag/递归" rel=tag>递归</A> <A
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -