位运算

marz posted @ Sep 19, 2010 03:55:11 AM in c/c++ with tags c/c++ bit operation , 3209 readers

 

前言   
  看到有些人对位运算还存在问题,于是决定写这篇文章作个简要说明。   
    
  什么是位(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

  • No match
Avatar_small
marz said:
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))   最后这一个在树状数组中会用到。


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter