位运算
前言
看到有些人对位运算还存在问题，于是决定写这篇文章作个简要说明。
什么是位(bit)？
很简单，位(bit)就是单个的0或1，位是我们在计算机上所作一切的基础。计算机上的所有数据都是用位来存储的。一个字节(BYTE)由八个位组成，一个字(WORD)是二个字节或十六位，一个双字(DWORD)是二个字(WORDS)或三十二位。如下所示：
0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0
| | | | | | |
| +- bit 31 | | | bit 0 -+ |
| | | | |
+-- BYTE 3 ---- -+---- BYTE 2 ---+---- BYTE 1 ---+--- BYTE 0 -----+
| | |
+------------ WORD 1 ------------+----------- WORD 0 -------------+
| |
+----------------------------- DWORD -----------------------------+
使用位运算的好处是可以将BYTE, WORD 或 DWORD 作为小数组或结构使用。通过位运算可以检查位的值或赋值，也可以对整组的位进行运算。
16进制数及其与位的关系
用0或1表示的数值就是二进制数，很难理解。因此用到16进制数。
16进制数用4个位表示0 - 15的值，4个位组成一个16进制数。也把4位成为半字节(nibble)。一个BYTE有二个nibble，因此可以用二个16进制数表示一个BYTE。如下所示：
NIBBLE HEX VALUE
====== =========
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 A
1011 B
1100 C
1101 D
1110 E
1111 F
如果用一个字节存放字母"r"(ASCII码114)，结果是：
0111 0010 二进制
7 2 16进制
可以表达为：'0x72'
有6种位运算：
& 与运算
| 或运算
^ 异或运算
~ 非运算(求补)
>> 右移运算
<< 左移运算
与运算(&)
双目运算。二个位都置位(等于1)时，结果等于1，其它的结果都等于0。
1 & 1 == 1
1 & 0 == 0
0 & 1 == 0
0 & 0 == 0
与运算的一个用途是检查指定位是否置位(等于1)。例如一个BYTE里有标识位，要检查第4位是否置位，代码如下：
BYTE b = 50;
if ( b & 0x10 )
cout << "Bit four is set" << endl;
else
cout << "Bit four is clear" << endl;
上述代码可表示为：
00110010 - b
& 00010000 - & 0x10
----------------------------
00010000 - result
可以看到第4位是置位了。
或运算( | )
双目运算。二个位只要有一个位置位，结果就等于1。二个位都为0时，结果为0。
1 | 1 == 1
1 | 0 == 1
0 | 1 == 1
0 | 0 == 0
与运算也可以用来检查置位。例如要检查某个值的第3位是否置位：
BYTE b = 50;
BYTE c = b | 0x04;
cout << "c = " << c << endl;
可表达为：
00110010 - b
| 00000100 - | 0x04
----------
00110110 - result
异或运算(^)
双目运算。二个位不相等时，结果为1，否则为0。
1 ^ 1 == 0
1 ^ 0 == 1
0 ^ 1 == 1
0 ^ 0 == 0
异或运算可用于位值翻转。例如将第3位与第4位的值翻转：
BYTE b = 50;
cout << "b = " << b << endl;
b = b ^ 0x18;
cout << "b = " << b << endl;
b = b ^ 0x18;
cout << "b = " << b << endl;
可表达为：
00110010 - b
^ 00011000 - ^0x18
----------
00101010 - result
00101010 - b
^ 00011000 - ^0x18
----------
00110010 - result
非运算(~)
单目运算。位值取反，置0为1，或置1为0。非运算的用途是将指定位清0，其余位置1。非运算与数值大小无关。例如将第1位和第2位清0，其余位置1：
BYTE b = ~0x03;
cout << "b = " << b << endl;
WORD w = ~0x03;
cout << "w = " << w << endl;
可表达为：
00000011 - 0x03
11111100 - ~0x03 b
0000000000000011 - 0x03
1111111111111100 - ~0x03 w
非运算和与运算结合，可以确保将指定为清0。如将第4位清0：
BYTE b = 50;
cout << "b = " << b << endl;
BYTE c = b & ~0x10;
cout << "c = " << c << endl;
可表达为：
00110010 - b
& 11101111 - ~0x10
----------
00100010 - result
移位运算(>> 与 <<)
将位值向一个方向移动指定的位数。右移 >> 算子从高位向低位移动，左移 << 算子从低位向高位移动。往往用位移来对齐位的排列(如MAKEWPARAM, HIWORD, LOWORD 宏的功能)。
BYTE b = 12;
cout << "b = " << b << endl;
BYTE c = b << 2;
cout << "c = " << c << endl;
c = b >> 2;
cout << "c = " << c << endl;
可表达为：
00001100 - b
00110000 - b << 2
00000011 - b >> 2
译注：以上示例都对，但举例用法未必恰当。请阅文末链接的文章，解释得较为清楚。
位域(Bit Field)
位操作中的一件有意义的事是位域。利用位域可以用BYTE, WORD或DWORD来创建最小化的数据结构。例如要保存日期数据，并尽可能减少内存占用，就可以声明这样的结构：
struct date_struct {
BYTE day : 5, // 1 to 31
month : 4, // 1 to 12
year : 14; // 0 to 9999
}date;
在结构中，日期数据占用最低5位，月份占用4位，年占用14位。这样整个日期数据只需占用23位，即3个字节。忽略第24位。如果用整数来表达各个域，整个结构要占用12个字节。
| 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 |
| | | |
+------------- year --------------+ month+-- day --+
现在分别看看在这个结构声明中发生了什么
首先看一下位域结构使用的数据类型。这里用的是BYTE。1个BYTE有8个位，编译器将分配1个BYTE的内存。如果结构内的数据超过8位，编译器就再分配1个BYTE，直到满足数据要求。如果用WORD或DWORD作结构的数据类型，编译器就分配一个完整的32位内存给结构。
其次看一下域声明。变量(day, month, year)名跟随一个冒号，冒号后是变量占用的位数。位域之间用逗号分隔，用分号结束。
使用了位域结构，就可以方便地象处理普通结构数据那样处理成员数据。尽管我们无法得到位域的地址，却可以使用结构地址。例如：
date.day = 12;
dateptr = &date;
dateptr->year = 1852;
ref:http://www.cnblogs.com/flying_bat/archive/2008/06/17/1224178.html
Sep 19, 2010 07:41:45 AM
功能 | 示例 | 位运算 ----------------------+---------------------------+-------------------- 去掉最后一位 | (101101->10110) | x shr 1 在最后加一个0 | (101101->1011010) | x shl 1 在最后加一个1 | (101101->1011011) | x shl 1+1 把最后一位变成1 | (101100->101101) | x or 1 把最后一位变成0 | (101101->101100) | x or 1-1 最后一位取反 | (101101->101100) | x xor 1 把右数第k位变成1 | (101001->101101,k=3) | x or (1 shl (k-1)) 把右数第k位变成0 | (101101->101001,k=3) | x and not (1 shl (k-1)) 右数第k位取反 | (101001->101101,k=3) | x xor (1 shl (k-1)) 取末三位 | (1101101->101) | x and 7 取末k位 | (1101101->1101,k=5) | x and (1 shl k-1) 取右数第k位 | (1101101->1,k=4) | x shr (k-1) and 1 把末k位变成1 | (101001->101111,k=4) | x or (1 shl k-1) 末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1) 把右边连续的1变成0 | (100101111->100100000) | x and (x+1) 把右起第一个0变成1 | (100101111->100111111) | x or (x+1) 把右边连续的0变成1 | (11011000->11011111) | x or (x-1) 取右边连续的1 | (100101111->1111) | (x xor (x+1)) shr 1 去掉右起第一个1的左边 | (100101000->1000) | x and (x xor (x-1)) 最后这一个在树状数组中会用到。 功能 | 示例 | 位运算 ----------------------+---------------------------+-------------------- 去掉最后一位 | (101101->10110) | x shr 1 在最后加一个0 | (101101->1011010) | x shl 1 在最后加一个1 | (101101->1011011) | x shl 1+1 把最后一位变成1 | (101100->101101) | x or 1 把最后一位变成0 | (101101->101100) | x or 1-1 最后一位取反 | (101101->101100) | x xor 1 把右数第k位变成1 | (101001->101101,k=3) | x or (1 shl (k-1)) 把右数第k位变成0 | (101101->101001,k=3) | x and not (1 shl (k-1)) 右数第k位取反 | (101001->101101,k=3) | x xor (1 shl (k-1)) 取末三位 | (1101101->101) | x and 7 取末k位 | (1101101->1101,k=5) | x and (1 shl k-1) 取右数第k位 | (1101101->1,k=4) | x shr (k-1) and 1 把末k位变成1 | (101001->101111,k=4) | x or (1 shl k-1) 末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1) 把右边连续的1变成0 | (100101111->100100000) | x and (x+1) 把右起第一个0变成1 | (100101111->100111111) | x or (x+1) 把右边连续的0变成1 | (11011000->11011111) | x or (x-1) 取右边连续的1 | (100101111->1111) | (x xor (x+1)) shr 1 去掉右起第一个1的左边 | (100101000->1000) | x and (x xor (x-1)) 最后这一个在树状数组中会用到。
Aug 20, 2022 12:20:37 AM
I’m impressed, I must say. Actually rarely must i encounter a weblog that’s both educative and entertaining, and let me tell you, you may have hit the nail for the head. Your notion is outstanding; the pain is something that not enough individuals are speaking intelligently about. My business is happy we found this at my seek out something regarding this. 뉴헤븐카지노주소
Aug 23, 2022 07:27:29 PM
You should join in a tournament first of the greatest blogs on the web. I will recommend this web site! 온라인바카라
Aug 26, 2022 09:02:14 PM
Hi, have you ever before asked yourself to write about Nintendo or PSP? 온라인바카라
Oct 27, 2022 12:37:02 AM
Respect to website author , some good selective information. Google AdSense Approval
Dec 30, 2022 11:55:01 PM
Hi there! I know this is somewhat off topic but I was wondering if you knew where I could locate a captcha plugin for my comment form? I’m using the same blog platform as yours and I’m having difficulty finding one? Thanks a lot! 강남셔츠룸
Dec 30, 2022 11:55:18 PM
Nice post. I learn some thing harder on various blogs everyday. Most commonly it is stimulating to study content from other writers and exercise a specific thing from their site. I’d opt to apply certain using the content in my small weblog regardless of whether you do not mind. Natually I’ll provide link for your internet weblog. Thanks for sharing. 노래방알바
Jan 01, 2023 09:44:43 PM
It’s a good shame you don’t contain a give money button! I’d definitely give money for this fantastic webpage! That i suppose for the time being i’ll be satisfied bookmarking together with including an individual’s Feed that will my best Msn balance. That i appearance forward that will recent messages and definitely will share the web site utilizing my best Facebook or twitter team: ) 바카라사이트
Jan 06, 2023 10:01:02 PM
Deference to author , some fantastic information . 메이저바카라
=================
Good web site! I truly love how it is simple on my eyes and the data are well written. I am wondering how I could be notified whenever a new post has been made. I have subscribed to your RSS which must do the trick! Have a nice day! 토토사이트
Jan 09, 2023 05:35:23 PM
The new Zune browser is surprisingly good, but not as good as the iPods. It works well, but isnt as fast as Safari, and has a clunkier interface. If you occasionally plan on using the web browser thats not an issue, but if youre planning to browse the web alot from your PMP then the iPods larger screen and better browser may be important. 룸알바
========================
you are really a just right webmaster. The web site loading velocity is amazing. It sort of feels that you’re doing any distinctive trick. Also, The contents are masterwork. you’ve performed a excellent job in this matter! 여우알바
Jan 09, 2023 11:51:57 PM
Online Quran Learning for Kids & Adults with Expert Male & Female Quran Teachers. 100% Free Trial Classes & Up to 10% Siblings Discounts. learning Quran online
Dec 04, 2023 11:27:35 PM
Hello, this weekend is good for me, since this time i am reading this enormous informative article here at my home.I haven’t any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us.This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value. Im glad to have found this post as its such an interesting one! I am always on the lookout for quality posts and articles so i suppose im lucky to have found this! I hope you will be adding more in the future... UFABETเว็บแทงบอลต่างประเทศ
Dec 04, 2023 11:29:50 PM
I can see that you are an expert at your field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business.i never know the use of adobe shadow until i saw this post. thank you for this! this is very helpful. UFABETกติกาแทงบอล
Dec 04, 2023 11:31:15 PM
Great job for publishing such a beneficial web site. Your web log isn’t only useful but it is additionally really creative too.I was surfing the Internet for information and came across your blog. I am impressed by the information you have on this blog. It shows how well you understand this subject. UFABETแทงบอลเว็บแม่
Dec 04, 2023 11:33:02 PM
I have read all the comments and suggestions posted by the visitors for this article are very fine,We will wait for your next article so only.Thanks!I guess I am not the only one having all the enjoyment here keep up the good work. Hey what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you. สมัครแทงบอลฟรีUFABET
Dec 04, 2023 11:35:01 PM
I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post.We have sell some products of different custom boxes.it is very useful and very low price please visits this site thanks and please share this post with your friends. UFABETเว็บแทงบอลดีที่สุด
Dec 04, 2023 11:36:11 PM
Interesting topic for a blog. I have been searching the Internet for fun and came upon your website.Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place..Admiring the time and effort you put into your blog and detailed information you offer!..Very nice article, I enjoyed reading your post, very nice share, I want to twit this to my followers. Thanks!.This blog is so nice to me. I will keep on coming here again and again. Visit my link as well.. UFABETสมัครเว็บบอลออนไลน์
Dec 04, 2023 11:38:28 PM
I was reading some of your content on this website..Thank you again for all the knowledge you distribute,Good post. I was very interested in the article, it's quite inspiring I should admit. I like visiting you site since I always come across interesting articles like this one.Great Job, I greatly appreciate that.Do Keep sharing! Regards, UFABETเว็บตรงแทงบอล
Dec 04, 2023 11:40:05 PM
Positive site, where did u come up with the information on this posting? I'm pleased I discovered it though, ill be checking back soon to find out what additional posts you include.Thank you because you have been willing to share information with us. we will always appreciate all you have done here because I know you are very concerned with our. UFABETเว็บตรงสมัครฟรี
Dec 04, 2023 11:41:37 PM
Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign.Stopping by your blog helped me to get what I was looking for. UFABETสมัครแทงบอลเว็บตรง
Dec 04, 2023 11:43:00 PM
Admiring the time and effort you put into your blog and detailed information you offer!..Great post, and great website. Thanks for the information! Thanks for all your help and wishing you all the success in your business. UFABETทางเข้าแทงบอลฟรี
Dec 06, 2023 12:26:07 AM
I love seeing blog that understand the value of providing a quality resource for free.This is my first time i visit here. I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here keep up the good workNice post! This is a very nice blog that I will definitively come back to more times this year! Thanks for informative post.Very efficiently written information. It will be beneficial to anybody who utilizes it, including me. Keep up the good work. For sure i will check out more posts. This site seems to get a good amount of visitors. UFABETทางเข้าเว็บไซต์แม่
Dec 06, 2023 12:28:37 AM
You made such an interesting piece to read, giving every subject enlightenment for us to gain knowledge. Thanks for sharing the such information with us to read this...This is my first visit to your web journal! We are a group of volunteers and new activities in the same specialty. Website gave us helpful data to work.I like your post. It is good to see you verbalize from the heart and clarity on this important subject can be easily observed...Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.Thanksi never know the use of adobe shadow until i saw this post. thank you for this! this is very helpful. UFABETทางเข้าเว็บหลัก
Dec 06, 2023 12:30:47 AM
This is really nice to read..informative post is very good to read..thanks a lot!Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome!We have sell some products of different custom boxes.it is very useful and very low price please visits this site thanks and please share this post with your friends.I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post. UFABETสมัครเว็บตรงแทงบอล
Dec 06, 2023 12:33:05 AM
Great job for publishing such a beneficial web site. Your web log isn’t only useful but it is additionally really creative too.I'm glad I found this web site, I couldn't find any knowledge on this matter prior to.Also operate a site and if you are ever interested in doing some visitor writing for me if possible feel free to let me know, im always look for people to check out my web site. UFABETเว็บตรงที่ดีที่สุด
Dec 06, 2023 12:35:32 AM
Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome!This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value. Im glad to have found this post as its such an interesting one! I am always on the lookout for quality posts and articles so i suppose im lucky to have found this! I hope you will be adding more in the future...Thanks for taking the time to discuss this, I feel strongly that love and read more on this topic. UFABETเว็บพนันตรง
Dec 06, 2023 12:37:40 AM
Wow i can say that this is another great article as expected of this blog.Bookmarked this site..We have sell some products of different custom boxes.I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post. UFABETเว็บพนันตรงไม่มีขั้นต่ำ
Dec 06, 2023 12:39:57 AM
I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article...When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your.Awesome article, it was exceptionally helpful! I simply began in this and I'm becoming more acquainted with it better! Cheers, keep doing awesome!Thanks for sharing the such information with us to read this...We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work. UFABETฝากถอนไม่มีขั้นต่ำ
Dec 06, 2023 12:43:35 AM
When your website or blog goes live for the first time, it is exciting. That is until you realize no one but you and your.Interesting topic for a blog. I have been searching the Internet for fun and came upon your website.I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article...Hello, I have browsed most of your posts. This post is probably where I got the most useful information for my research. Thanks for posting, maybe we can see more on this. Are you aware of any other websites on this subject.i love reading this article so beautiful!!great job! UFABETฝากขั้นต่ำ
Dec 06, 2023 12:45:42 AM
Nice post! This is a very nice blog that I will definitively come back to more times this year! I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You.I can set up my new idea from this post. It gives in depth information. Thanks for this valuable information for all,..This is just the information I am finding everywhere. This type of message always inspiring and I prefer to read quality content, so happy to find good place to many here in the post, the writing is just great, thanks for the post. UFABETเว็บพนันอันดับ1
Dec 06, 2023 12:48:06 AM
I have you bookmarked your site to check out the new stuff you post.This is such a great resource that you are providing and you give it away for free.Great survey, I'm sure you're getting a great response.I’m going to read this. I’ll be sure to come back. thanks for sharing. and also This article gives the light in which we can observe the reality. this is very nice one and gives indepth information. thanks for this nice article... UFABETเว็บแทงบอลดีสุด
Jan 13, 2024 10:22:51 PM
Yan Ting at The St. Regis Singapore presents fine Cantonese dining. best singapore dinner restaurant
Jan 17, 2024 09:40:00 PM
오피타임's location within officetels is so convenient; I can't imagine going anywhere else.
Jan 18, 2024 04:55:52 AM
I've experienced many massages, but 제주출장마사지 stands out.
Dec 07, 2024 10:37:29 PM
Thank you for sharing superb informations. Your site is very cool. I’m impressed by the details that you have on this website. It reveals how nicely you perceive this subject. Bookmarked this website page, will come back for extra articles. You, my friend, ROCK! I found just the info I already searched everywhere and just couldn’t come across. What a great web site. ECサイト セキュリティ
Dec 07, 2024 10:37:46 PM
Perfect work you have done, this site is really cool with excellent information. EC-CUBE カスタマイズ
Dec 13, 2024 05:03:40 PM
I’ve read some good stuff here. Definitely worth bookmarking for revisiting. 大人動画
Dec 15, 2024 07:36:46 PM
Its really a great and useful piece of info. I am happy that you simply shared this useful information with us. Please stay us informed like this. Thanks for sharing. 【フル映像】
Dec 17, 2024 09:04:47 PM
You are a very persuasive writer. I can see this in your article. You have a way of writing compelling information that sparks much interest. 盗撮エロ動画
Dec 17, 2024 09:05:00 PM
Oh my goodness! a tremendous article dude. Thank you Nonetheless I'm experiencing difficulty with ur rss . Don know why Unable to subscribe to it. Is there anybody getting equivalent rss problem? Anybody who is aware of kindly respond. Thnkx エロ動画のフル動画
Dec 21, 2024 08:04:22 PM
Finding this site made all the work I did to find it look like nothing. The reason being that this is such an informative post. I wanted to thank you for this special read of the subject. I definitely savored every little bit of it and I have you bookmarked to check out new stuff you post. Japanese Pokemon Card