📄 位运算简介及实用技巧（一）：基础篇.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=311 -->
<HTML lang=UTF-8 xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>位运算简介及实用技巧（一）：基础篇 - 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="位运算简介及实用技巧（一）：基础篇.files/global.css" type=text/css rel=stylesheet><!--全局样式表--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（一）：基础篇.files/layout.css" type=text/css rel=stylesheet><!--层次样式表--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（一）：基础篇.files/typography.css" type=text/css rel=stylesheet><!--局部样式表--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（一）：基础篇.files/link.css" type=text/css rel=stylesheet><!--超链接样式表--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（一）：基础篇.files/editor.css" type=text/css rel=stylesheet><!--UBB编辑器代码--><LINK rev=stylesheet media=all
href="位运算简介及实用技巧（一）：基础篇.files/highlight.css" type=text/css rel=stylesheet><LINK
rev=stylesheet media=all href="位运算简介及实用技巧（一）：基础篇.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="位运算简介及实用技巧（一）：基础篇.files/common.js" type=text/javascript></SCRIPT>
<SCRIPT src="位运算简介及实用技巧（一）：基础篇.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=311#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="位运算简介及实用技巧（一）：基础篇.files/rss.png"
border=0> 订阅</A> | <A title="上一篇日志: 404页面：被二进制困住的朦胧系MM" accessKey=,
href="http://www.matrix67.com/blog/article.asp?id=310"><IMG alt=""
src="位运算简介及实用技巧（一）：基础篇.files/Cprevious.gif" border=0>上一篇</A> | <A
title="下一篇日志: 位运算简介及实用技巧（二）：进阶篇(1)" accessKey=.
href="http://www.matrix67.com/blog/article.asp?id=312"><IMG alt=""
src="位运算简介及实用技巧（一）：基础篇.files/Cnext.gif" border=0>下一篇</A> </DIV><IMG
style="MARGIN: 0px 2px -4px 0px" alt="" src="位运算简介及实用技巧（一）：基础篇.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>位运算简介及实用技巧（一）：基础篇</STRONG></H1>
<H2 class=ContentAuthor>作者:matrix67 日期:2007-07-23</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="位运算简介及实用技巧（一）：基础篇.files/hn2_sunny.gif"><IMG alt=""
src="位运算简介及实用技巧（一）：基础篇.files/hn2_t_sunny.gif"> <IMG
style="MARGIN: 0px 2px -1px 0px" alt=""
src="位运算简介及实用技巧（一）：基础篇.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> 去年年底写的关于<A
href="http://www.matrix67.com/blog/article.asp?id=153"
target=_blank>位运算</A>的日志是这个Blog里少数大受欢迎的文章之一，很多人都希望我能不断完善那篇文章。后来我看到了不少其它的资料，学习到了更多关于位运算的知识，有了重新整理位运算技巧的想法。从今天起我就开始写这一系列位运算讲解文章，与其说是原来那篇文章的follow-up，不如说是一个remake。当然首先我还是从最基础的东西说起。<BR><BR><STRONG>什么是位运算？</STRONG><BR> 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6
and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：<BR><SPAN
style="FONT-FAMILY: 宋体"> 110<BR>AND
1011<BR>----------<BR> 0010 --> 2</SPAN><BR> 由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6
and
11没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。<BR><BR><BR><STRONG>Pascal和C中的位运算符号</STRONG><BR> 下面的a和b都是整数类型，则：<BR><SPAN
style="FONT-FAMILY: 宋体">C语言 | Pascal语言<BR>-------+-------------<BR>a
& b | a and b<BR>a | b | a or
b<BR>a ^ b | a xor b<BR> ~a
| not a<BR>a << b | a shl b<BR>a >> b
| a shr
b</SPAN><BR> 注意C中的逻辑运算和位运算符号是不同的。520|1314=1834，但520||1314=1，因为逻辑运算时520和1314都相当于True。同样的，!a和~a也是有区别的。<BR><BR><BR><STRONG>各种位运算的使用</STRONG><BR> ===
1. and运算 ===<BR> and运算通常用于二进制取位操作，例如一个数 and
1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数.<BR><BR> ===
2. or运算 ===<BR> or运算通常用于二进制特定位上的无条件赋值，例如一个数or
1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or
1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。<BR><BR> === 3. xor运算
===<BR> xor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。<BR> xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a
xor b) xor b =
a。xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520 xor
19880516 = 20665500，我就把20665500告诉MM。MM再次计算20665500 xor
19880516的值，得到1314520，于是她就明白了我的企图。<BR> 下面我们看另外一个东西。定义两个符号#和@（我怎么找不到那个圈里有个叉的字符），这两个符号互为逆运算，也就是说(x
# y) @ y = x。现在依次执行下面三条命令，结果是什么？<BR>
<DIV class=UBBPanel>
<DIV class=UBBTitle><IMG style="MARGIN: 0px 2px -3px 0px" alt=程序代码
src="位运算简介及实用技巧（一）：基础篇.files/code.gif"> 程序代码</DIV>
<DIV class=UBBContentCode>x <- x # y<BR>y <- x @ y<BR>x <- x @
y</DIV></DIV><BR> 执行了第一句后x变成了x # y。那么第二句实质就是y <- x # y
@ y，由于#和@互为逆运算，那么此时的y变成了原来的x。第三句中x实际上被赋值为(x # y) @
x，如果#运算具有交换律，那么赋值后x就变成最初的y了。这三句话的结果是，x和y的位置互换了。<BR> 加法和减法互为逆运算，并且加法满足交换律。把#换成+，把@换成-，我们可以写出一个不需要临时变量的swap过程(Pascal)。<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>procedure swap(var a,b:longint);<BR>begin<BR> a:=a + b;<BR> b:=a - b;<BR> a:=a - b;<BR>end;</CODE></PRE></DIV></DIV><BR> 好了，刚才不是说xor的逆运算是它本身吗？于是我们就有了一个看起来非常诡异的swap过程：<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>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;</CODE></PRE></DIV></DIV><BR><BR> ===
4. not运算
===<BR> not运算的定义是把内存中的0和1全部取反。使用not运算时要格外小心，你需要注意整数类型有没有符号。如果not的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用$0000到$FFFF依次表示的。下面的两个程序（仅语言不同）均返回65435。<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:word;<BR>begin<BR> a:=100;<BR> a:=not a;<BR> writeln(a);<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> unsigned short a=100;<BR> a = ~a;<BR> printf( "%d\n", a ); <BR> return 0;<BR>}</CODE></PRE></DIV></DIV><BR> 如果not的对象是有符号的整数，情况就不一样了，稍后我们会在“整数类型的储存”小节中提到。<BR><BR> ===
5. shl运算 ===<BR> a shl
b就表示把a转为二进制后左移b位（在后面添b个0）。例如100的二进制为1100100，而110010000转成十进制是400，那么100 shl 2 =
400。可以看出，a shl
b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。<BR> 通常认为a shl 1比a
*
2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。<BR> 定义一些常量可能会用到shl运算。你可以方便地用1
shl 16 -
1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用shl来定义Max_N等常量。<BR><BR> ===
6. shr运算 ===<BR> 和shl相似，a shr
b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们也经常用shr 1来代替div
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -