位运算[转帖]

转帖：http://topic.csdn.net/t/20041019/00/3468250.html（snowingbf（snowingbf）2004-10-19 00:03:07 在 C/C++ / C++ 语言 提问）
有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;




============================================================================
负数的二进制表示方法

例如 －5 
第一步：首先要把5变成101的二进制形式
第二步：再者就是安位取反，（形成前面全是1）010
第三步：在最后加1 形成：11111111 11111111 11111111 11111011
反过来如果把最高位是1的二进制变成负的整形时
第一步：位取反，变成00000000 00000000 00000000 00000100
第二步：在最低位加上1，形成101
第三步：形成整形5 ，在加上负号；
在二进制中，相反数的转变过程是这样的：先取反然后加1.


1.移位运算避免乘法

使用移位运算来避免乘法运算是一种常用技巧，不过乘数必须都是正整数，而且必须至少有一个是 2 的 n 次方，例如：2，4，8，16，32……移位运算的特点是速度快，而乘法运算速度较慢，把乘法运算转化为移位运算可以稍微提高程序运行效率。例如：

        num *= 32;
        等同于
        num <<= 5; /* 2 的 5 次方等于 32 */

如果乘数不是 2 的 n 次方，我们可以把乘数分解成几个 2 的 n 次方的和：
        num *= 20;
        等于
        num *= (16 + 4);
        等于
        num = num * 16 + num * 4;
        等于
        num = (num << 4) + (num << 2);

不过，现在的编译器很聪明，它们会代替我们做这种优化。也就是说，如果我们写的语句是：
        num *= 100;
编译器会把这个语句优化为：
        num = (num << 6) + (num << 5) + (num << 2);

所以，我们没有必要手工进行这种优化，因为编译器会替我们完成。而且，就算进行了这种优化，速度也不会有太大提高。我们应该把精力用来改进算法，一个好的算法可以让程序运行效率大大提高！