📄 位运算简介及实用技巧（一）：基础篇.htm
字号:
2，比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的mod运算，效率可以提高60%。<BR><BR><BR><STRONG>位运算的简单应用</STRONG><BR> 有时我们的程序需要一个规模不大的Hash表来记录状态。比如，做数独时我们需要27个Hash表来统计每一行、每一列和每一个小九宫格里已经有哪些数了。此时，我们可以用27个小于2^9的整数进行记录。例如，一个只填了2和5的小九宫格就用数字18表示（二进制为000010010），而某一行的状态为511则表示这一行已经填满。需要改变状态时我们不需要把这个数转成二进制修改后再转回去，而是直接进行位操作。在搜索时，把状态表示成整数可以更好地进行判重等操作。<A
href="http://www.vijos.cn/Problem_Show.asp?id=1197"
target=_blank>这道题</A>是在搜索中使用位运算加速的经典例子。以后我们会看到更多的例子。<BR> 下面列举了一些常见的二进制位的变换操作。<BR><BR><SPAN
style="FONT-FAMILY: 宋体"> 功能 |
示例 | 位运算<BR>----------------------+---------------------------+--------------------<BR>去掉最后一位 |
(101101->10110) |
x shr 1<BR>在最后加一个0 |
(101101->1011010) | x shl
1<BR>在最后加一个1 |
(101101->1011011) | x shl
1+1<BR>把最后一位变成1 |
(101100->101101) |
x or 1<BR>把最后一位变成0 |
(101101->101100) |
x or 1-1<BR>最后一位取反 |
(101101->101100) |
x xor 1<BR>把右数第k位变成1 |
(101001->101101,k=3) | x or (1 shl
(k-1))<BR>把右数第k位变成0 |
(101101->101001,k=3) | x and not (1 shl
(k-1))<BR>右数第k位取反 |
(101001->101101,k=3) | x xor (1 shl
(k-1))<BR>取末三位 |
(1101101->101) |
x and
7<BR>取末k位
| (1101101->1101,k=5) | x and (1 shl
k-1)<BR>取右数第k位 |
(1101101->1,k=4) |
x shr (k-1) and
1<BR>把末k位变成1 |
(101001->101111,k=4) | x or (1 shl
k-1)<BR>末k位取反
| (101001->100110,k=4) | x xor (1 shl
k-1)<BR>把右边连续的1变成0 |
(100101111->100100000) | x and
(x+1)<BR>把右起第一个0变成1 |
(100101111->100111111) | x or
(x+1)<BR>把右边连续的0变成1 |
(11011000->11011111) | x or
(x-1)<BR>取右边连续的1 |
(100101111->1111) | (x xor
(x+1)) shr 1<BR>去掉右起第一个1的左边 |
(100101000->1000) | x and (x
xor
(x-1))</SPAN><BR><BR> 最后这一个在树状数组中会用到。<BR><BR><BR><STRONG>Pascal和C中的16进制表示</STRONG><BR> Pascal中需要在16进制数前加$符号表示，C中需要在前面加0x来表示。这个以后我们会经常用到。<BR><BR><STRONG>整数类型的储存</STRONG><BR> 我们前面所说的位运算都没有涉及负数，都假设这些运算是在unsigned/word类型（只能表示正数的整型）上进行操作。但计算机如何处理有正负符号的整数类型呢？下面两个程序都是考察16位整数的储存方式（只是语言不同）。<BR>
<DIV class=UBBPanel>
<DIV class=UBBTitle><IMG style="MARGIN: 0px 2px -3px 0px" alt=程序代码
src="位运算简介及实用技巧（一）：基础篇.files/quote.gif"> 程序代码</DIV>
<DIV class=UBBContent><PRE><CODE class=pascal>var<BR> a,b:integer;<BR>begin<BR> a:=$0000;<BR> b:=$0001;<BR> write(a,' ',b,' ');<BR> a:=$FFFE;<BR> b:=$FFFF;<BR> write(a,' ',b,' ');<BR> a:=$7FFF;<BR> b:=$8000;<BR> writeln(a,' ',b);<BR>end.</CODE></PRE></DIV></DIV><BR>
<DIV class=UBBPanel>
<DIV class=UBBTitle><IMG style="MARGIN: 0px 2px -3px 0px" alt=程序代码
src="位运算简介及实用技巧（一）：基础篇.files/quote.gif"> 程序代码</DIV>
<DIV class=UBBContent><PRE><CODE class=cpp>#include <stdio.h><BR>int main()<BR>{<BR> short int a, b;<BR> a = 0x0000;<BR> b = 0x0001;<BR> printf( "%d %d ", a, b );<BR> a = 0xFFFE;<BR> b = 0xFFFF;<BR> printf( "%d %d ", a, b );<BR> a = 0x7FFF;<BR> b = 0x8000;<BR> printf( "%d %d\n", a, b );<BR> return 0;<BR>}</CODE></PRE></DIV></DIV><BR> 两个程序的输出均为0
1 -2 -1 32767
-32768。其中前两个数是内存值最小的时候，中间两个数则是内存值最大的时候，最后输出的两个数是正数与负数的分界处。由此你可以清楚地看到计算机是如何储存一个整数的：计算机用$0000到$7FFF依次表示0到32767的数，剩下的$8000到$FFFF依次表示-32768到-1的数。32位有符号整数的储存方式也是类似的。稍加注意你会发现，二进制的第一位是用来表示正负号的，0表示正，1表示负。这里有一个问题：0本来既不是正数，也不是负数，但它占用了$0000的位置，因此有符号的整数类型范围中正数个数比负数少一个。对一个有符号的数进行not运算后，最高位的变化将导致正负颠倒，并且数的绝对值会差1。也就是说，not
a实际上等于-a-1。这种整数储存方式叫做“补码”。<BR><BR><STRONG>最后还有两句话</STRONG><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="位运算简介及实用技巧（一）：基础篇.files/show_ads.js"
type=text/javascript></SCRIPT>
<DIV class=Content-body><IMG style="MARGIN: 0px 2px -4px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.files/icon_trackback.gif"><STRONG>引用通告地址:</STRONG>
http://www.matrix67.com/blog/trackback.asp?tbID=JOFNKPI4&key=JOKOJQDPMMDQM8<BR><IMG
style="MARGIN: 4px 2px -4px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.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=C%E8%AF%AD%E8%A8%80">C语言</A><A
style="DISPLAY: none" href="http://technorati.com/tag/C语言" rel=tag>C语言</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=%E5%AF%86%E7%A0%81">密码</A><A
style="DISPLAY: none" href="http://technorati.com/tag/密码" rel=tag>密码</A> <BR><!--Add By WBC --><IMG style="MARGIN: 4px 2px -4px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.files/tag.gif"><STRONG>我猜你可能喜欢:</STRONG><BR>
<DIV class=Content-body id=wbc_tag></DIV><BR><!--End By WBC --></DIV>
<DIV class=Content-bottom>
<DIV class=ContentBLeft></DIV>
<DIV class=ContentBRight></DIV>评论: 22</A> | <A
href="http://www.matrix67.com/blog/trackback.asp?tbID=JOFNKPI4&key=JOKOJQDPMMDQM8"
target=_blank>引用: 0</A> | 查看次数: 5131 </DIV></DIV></DIV><A accessKey=C
href="http://www.matrix67.com/blog/article.asp?id=311#comm_top"
name=comm_top></A>
<DIV class=pageContent>
<DIV class=page style="FLOAT: right">
<UL>
<LI class=pageNumber><STRONG>1</STRONG> | <A
href="http://www.matrix67.com/blog/article.asp?id=311&page=2#comm_top">2</A>
| <A
href="http://www.matrix67.com/blog/article.asp?id=311&page=3#comm_top">3</A>
| <A title=下一页 style="TEXT-DECORATION: none" accessKey=.
href="http://www.matrix67.com/blog/article.asp?id=311&page=2"></A><A
title=最后一页 style="TEXT-DECORATION: none"
href="http://www.matrix67.com/blog/article.asp?id=311&page=3#comm_top">></A></LI></UL></DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A
href="javascript:addQuote('fafeymao','commcontent_3034')" name=comm_3034><IMG
style="MARGIN: 0px 4px -3px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.files/icon_quote.gif" border=0></A> fafeymao <SPAN
class=commentinfo>[楼层: 22楼 发表时间: 2008-02-17 03:00 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_3034><IMG style="MARGIN: 0px 0px -2px"
alt="" src="位运算简介及实用技巧（一）：基础篇.files/Face_01.gif" border=0>,谢过</DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A href="javascript:addQuote('csf','commcontent_2753')"
name=comm_2753><IMG style="MARGIN: 0px 4px -3px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.files/icon_quote.gif" border=0></A> csf <SPAN
class=commentinfo>[楼层: 21楼 发表时间: 2008-01-25 09:49 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_2753>果然牛！学习了！</DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A href="javascript:addQuote('xia0ji','commcontent_1909')"
name=comm_1909><IMG style="MARGIN: 0px 4px -3px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.files/icon_quote.gif" border=0></A> <A
href="http://www.matrix67.com/blog/member.asp?action=view&memName=xia0ji"
target=_blank><STRONG>xia0ji</STRONG></A> <SPAN class=commentinfo>[楼层: 20楼 发表时间:
2007-11-10 03:14 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_1909>请教一下<BR>procedure swap(var
a,b:longint);<BR>begin<BR> a:=a xor b;<BR> b:=a xor
b;<BR> a:=a xor b;<BR>end;<BR><BR>procedure swap(var
a,b:longint);<BR>var<BR>
t:longint;<BR>begin<BR> t:=a;<BR> a:=b;<BR> b:=t;<BR>end;<BR>那个快一些呢?<BR><BR><SPAN
style="COLOR: red">回复：自己写一个循环运行10000000次的程序来测一测吧</SPAN></DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A
href="javascript:addQuote('ergyioreya','commcontent_1800')" name=comm_1800><IMG
style="MARGIN: 0px 4px -3px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.files/icon_quote.gif" border=0></A> <A
href="http://ergyioreyf.blog.163.com/"
target=_blank><STRONG>ergyioreya</STRONG></A> <SPAN class=commentinfo>[楼层:
19楼 发表时间: 2007-11-01 04:17 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_1800>SORRY
<BR>没看到下面的人已经问了，一时头脑发热，我说的那个错了，Matrix67 正解</DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A
href="javascript:addQuote('ergyioreya','commcontent_1799')" name=comm_1799><IMG
style="MARGIN: 0px 4px -3px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.files/icon_quote.gif" border=0></A> <A
href="http://ergyioreyf.blog.163.com/"
target=_blank><STRONG>ergyioreya</STRONG></A> <SPAN class=commentinfo>[楼层:
18楼 发表时间: 2007-11-01 04:13 PM]</SPAN></DIV>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -