1) int型变量循环左移k次,即a=a < <k |a>>16-k  (设sizeof(int)=16)
(2) int型变量a循环右移k次,即a=a>>k |a < <16-k  (设sizeof(int)=16)
(3)整数的平均值
对于两个整数x,y,如果用 (x+y)/2 求平均值,会产生溢出,因为 x+y 可能会大于INT_MAX,但是我们知道它们的平均值是肯定不会溢出的,我们用如下算法:
int average(int x, int y)  //返回X,Y 的平均值
{   
    return (x&y)+((x^y)>>1);
}
(4)判断一个整数是不是2的幂,对于一个数 x >= 0,判断他是不是2的幂
boolean power2(int x)
{
    return ((x&(x-1))==0)&&(x!=0);
}
(5)不用temp交换两个整数
void swap(int x , int y)
{
    x ^= y;
    y ^= x;
    x ^= y;
}
(6)计算绝对值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ;        //or: (x+y)^y
}
(7)取模运算转化成位运算 (在不产生溢出的情况下)
        a % (2^n) 等价于 a & (2^n - 1)
(8)乘法运算转化成位运算 (在不产生溢出的情况下)
        a * (2^n) 等价于 a < < n
(9)除法运算转化成位运算 (在不产生溢出的情况下)
        a / (2^n) 等价于 a>> n
        例: 12/8 == 12>>3
(10) a % 2 等价于 a & 1       
(11) if (x == a) x= b;
            else x= a;
        等价于 x= a ^ b ^ x;
(12) x 的 相反数 表示为 (~x+1)

(13)求从x位(高)到y位(低)间共有多少个1

public static int FindChessNum(int x, int y, ushort k)
        {
            int re = 0;
            for (int i = y; i <= x; i++)
            {
                re += ((k >> (i - 1)) & 1);
            }
            return re;
        }
(14)
/*将32位数分解为4个8位数处理后再合成32位数返回*/
DWORD GetDW(DWORD dw)
{
 DWORD dwRet=0;
 if (dw!=0)
 {
  BYTE b1=(dw>>24)&0xff,b2=(dw>>16)&0xff,b3=(dw>>8)&0xff,b4=dw&0xff;
  //分别处理 b1,b2,b3,b4
  dwRet=b1;
  dwRet=(dwRet<<8)+b2;
  dwRet=(dwRet<<8)+b3;
  dwRet=(dwRet<<8)+b4;

  return dwRet;
 }
 else{
  return 0;
 }
}


  检测一个无符号数是不为2^n-1(^为幂):   x&(x+1)   
    
  将最右侧0位改为1位:   x   |   (x+1)   
    
  二进制补码运算公式:   
  -x   =   ~x   +   1   =   ~(x-1)   
  ~x   =   -x-1     
  -(~x)   =   x+1   
  ~(-x)   =   x-1   
  x+y   =   x   -   ~y   -   1   =   (x|y)+(x&y)     
  x-y   =   x   +   ~y   +   1   =   (x|~y)-(~x&y)     
  x^y   =   (x|y)-(x&y)   
  x|y   =   (x&~y)+y   
  x&y   =   (~x|y)-~x   
    
  x==y:         ~(x-y|y-x)   
  x!=y:         x-y|y-x   
  x<   y:         (x-y)^((x^y)&((x-y)^x))   
  x<=y:         (x|~y)&((x^y)|~(y-x))   
  x<   y:         (~x&y)|((~x|y)&(x-y))//无符号x,y比较   
  x<=y:         (~x|y)&((x^y)|~(y-x))//无符号x,y比较   
    
    
  使用位运算的无分支代码:   
    
  计算绝对值   
  int   abs(   int   x   )     
  {   
  int   y   ;   
  y   =   x   >>   31   ;   
  return   (x^y)-y   ;//or:   (x+y)^y   
  }   
    
  符号函数:sign(x)   =   -1,   x<0;   0,   x   ==   0   ;   1,   x   >   0   
  int   sign(int   x)   
  {   
  return   (x>>31)   |   (unsigned(-x))>>31   ;//x=-2^31时失败(^为幂)   
  }   
    
  三值比较:cmp(x,y)   =   -1,   x<y;   0,   x==y;   1,   x   >   y   
  int   cmp(   int   x,   int   y   )   
  {   
  return   (x>y)-(x-y)   ;   
  }   
    
  doz=x-y,   x>=y;   0,   x<y   
  int   doz(int   x,   int   y   )   
  {   
  int   d   ;   
  d   =   x-y   ;   
  return   d   &   ((~(d^((x^y)&(d^x))))>>31)   ;   
  }   
    
  int   max(int   x,   int   y   )     
  {   
  int   m   ;   
  m   =   (x-y)>>31   ;     
  return   y   &   m   |   x   &   ~m   ;   
  }   
    
  不使用第三方交换x,y:   
  1.x   ^=   y   ;   y   ^=   x   ;   x   ^=   y   ;   
  2.x   =   x+y   ;   y   =   x-y   ;   x   =   x-y   ;   
  3.x   =   x-y   ;   y   =   y+x   ;   x   =   y-x   ;   
  4.x   =   y-x   ;   x   =   y-x   ;   x   =   x+y   ;     
    
  双值交换:x   =   a,   x==b;   b,   x==a//常规编码为x   =   x==a   ?   b   :a   ;   
  1.x   =   a+b-x   ;   
  2.x   =   a^b^x   ;   
    
  下舍入到2的k次方的倍数:   
  1.x   &   ((-1)<<k)   
  2.(((unsigned)x)>>k)<<k   
  上舍入:   
  1.   t   =   (1<<k)-1   ;   x   =   (x+t)&~t   ;   
  2.t   =   (-1)<<k   ;   x   =   (x-t-1)&t   ;   
    
  位计数,统计1位的数量:   
  1.   
  int   pop(unsigned   x)   
  {   
  x   =   x-((x>>1)&0x55555555)   ;   
  x   =   (x&0x33333333)   +   ((x>>2)   &   0x33333333   )   ;   
  x   =   (x+(x>>4))   &   0x0f0f0f0f   ;   
  x   =   x   +   (x>>8)   ;   
  x   =   x   +   (x>>16)   ;   
  return   x   &   0x0000003f   ;   
  }   
  2.   
  int   pop(unsigned   x)   {   
  static   char   table[256]   =   {   0,1,1,2,   1,2,2,3,   ....,   6,7,7,8   }   ;   
  return   table[x&0xff]+table[(x>>8)&0xff]+table[(x>>16)&0xff]+table[(x>>24)]   ;   
  }   
    
  奇偶性计算:   
  x   =   x   ^   (   x>>1   )   ;   
  x   =   x   ^   (   x>>2   )   ;   
  x   =   x   ^   (   x>>4   )   ;   
  x   =   x   ^   (   x>>8   )   ;   
  x   =   x   ^   (   x>>16   )   ;   
  结果中位于x最低位,对无符号x,结果的第i位是原数第i位到最左侧位的奇偶性   
    
    
  位反转:   
  unsigned   rev(unsigned   x)   
  {   
  x   =   (x   &   0x55555555)   <<   1   |   (x>>1)   &   0x55555555   ;   
  x   =   (x   &   0x33333333)   <<   2   |   (x>>2)   &   0x33333333   ;   
  x   =   (x   &   0x0f0f0f0f)   <<   4   |   (x>>4)   &   0x0f0f0f0f   ;   
  x   =   (x<<24)   |   ((x&0xff00)<<8)   |   ((x>>8)   &   0xff00)   |   (x>>24)   ;   
  return   x   ;   
  }   
    
  递增位反转后的数:   
  unsigned   inc_r(unsigned   x)   
  {   
  unsigned   m   =   0x80000000   ;   
  x   ^=   m   ;   
  if(   (int)x   >=   0   )     
  do   {   m   >>=   1   ;   x   ^=   m   ;   }   while(   x   <   m   )   ;   
  return   x   ;   
  }   
    
  混选位:   
  abcd   efgh   ijkl   mnop   ABCD   EFGH   IJKL   MNOP->aAbB   cCdD   eEfF   gGhH   iIjJ   kKlL   mMnN   oOpP   
  unsigned   ps(unsigned   x)   
  {   
  unsigned   t   ;   
  t   =   (x   ^   (x>>8))   &   0x0000ff00;   x   =   x   ^   t   ^   (t<<8)   ;   
  t   =   (x   ^   (x>>4))   &   0x00f000f0;   x   =   x   ^   t   ^   (t<<4)   ;   
  t   =   (x   ^   (x>>2))   &   0x0c0c0c0c;   x   =   x   ^   t   ^   (t<<2)   ;   
  t   =   (x   ^   (x>>1))   &   0x22222222;   x   =   x   ^   t   ^   (t<<1)   ;   
  return   x   ;   
  }   
    
  位压缩:   
  选择并右移字x中对应于掩码m的1位的位,如:compress(abcdefgh,01010101)=0000bdfh   
  compress_left(x,m)操作与此类似,但结果位在左边:   bdfh0000.   
  unsigned   compress(unsigned   x,   unsigned   m)   
  {   
  unsigned   mk,   mp,   mv,   t   ;   
  int   i   ;   
    
  x   &=   m   ;   
  mk   =   ~m   <<   1   ;   
  for(   i   =   0   ;   i   <   5   ;   ++i   )   {   
  mp   =   mk   ^   (   mk   <<   1)   ;   
  mp   ^=   (   mp   <<   2   )   ;   
  mp   ^=   (   mp   <<   4   )   ;   
  mp   ^=   (   mp   <<   8   )   ;   
  mp   ^=   (   mp   <<   16   )   ;   
  mv   =   mp   &   m   ;   
  m   =   m   ^   mv   |   (mv   >>   (1<<i)   )   ;   
  t   =   x   &   mv   ;   
  x     =   x   ^   t   |   (   t   >>   (   1<<i)   )   ;   
  mk   =   mk   &   ~mp   ;   
  }   
  return   x   ;   
  }   
    
    
  位置换:   
  用32个5位数表示从最低位开始的位的目标位置,结果是一个32*5的位矩阵,   
  将该矩阵沿次对角线转置后用5个32位字p[5]存放。   
  SAG(x,m)   =   compress_left(x,m)   |   compress(x,~m)   ;   
  准备工作:   
  void   init(   unsigned   *p   )   {   
  p[1]   =   SAG(   p[1],   p[0]   )   ;   
  p[2]   =   SAG(   SAG(   p[2],   p[0]),   p[1]   )   ;   
  p[3]   =   SAG(   SAG(   SAG(   p[3],   p[0]   ),   p[1]),   p[2]   )   ;   
  p[4]   =   SAG(   SAG(   SAG(   SAG(   p[4],   p[0]   ),   p[1])   ,p[2]),   p[3]   )   ;   
  }   
  实际置换:   
  int   rep(   unsigned   x   )   {   
  x   =   SAG(x,p[0]);   
  x   =   SAG(x,p[1]);   
  x   =   SAG(x,p[2]);   
  x   =   SAG(x,p[3]);   
  x   =   SAG(x,p[4]);   
  return   x   ;   
  }   
    
  二进制码到GRAY码的转换:   
  unsigned   B2G(unsigned   B   )   
  {   
  return   B   ^   (B>>1)   ;   
  }   
  GRAY码到二进制码:   
  unsigned   G2B(unsigned   G)   
  {   
  unsigned   B   ;   
  B   =   G   ^   (G>>1)   ;   
  B   =   G   ^   (G>>2)   ;   
  B   =   G   ^   (G>>4)   ;   
  B   =   G   ^   (G>>8)   ;   
  B   =   G   ^   (G>>16)   ;   
  return   B   ;   
  }   
    
  找出最左0字节的位置:   
  int   zbytel(   unsigned   x   )   
  {   
  static   cahr   table[16]   =   {   4,3,2,2,   1,1,1,1,   0,0,0,0,   0,0,0,0   }   ;   
  unsigned   y   ;   
  y   =   (x&0x7f7f7f7f)   +   0x7f7f7f7f   ;   
  y   =   ~(y|x|0x7f7f7f7f)   ;   
  return   table[y*0x00204081   >>   28]   ;//乘法可用移位和加完成   
  }   


C\C++支持比较低阶的位运算,在是众人皆知的了。每本C\C++的教科书都会说到这部分的内容,不过都很简略,我想会有很多人不知道位运算用在什么地方。这个帖子就简略说说位运算的用处,更进一步的用法要大家自己去体会。而主要说的是操作标志值方面。

 

 /****************************************/

#define BTI_MSK(bit)    (1 << (bit))
#define BIT_SET(x,bit)  ((x) |=  BTI_MSK (bit))
#define BIT_CLR(x,bit)  ((x) &= ~BTI_MSK (bit))
#define BIT_TST(x,bit)  ((x) &   BTI_MSK (bit))

 /****************************************/

 

考虑一个事物、一个系统、或者一个程序可能会出现一种或者几种状态。为了在不同的状态下,作出不同的行为,你可以设立一些标志值,再根据标志值来做判断。比如C++的文件流,你就可以设定一些标志值,ios::app, ios::ate, ios::binary, ios::in, ios::out, ios::trunc,并且可以将它用|组合起来创建一个恰当的文件流。你可能会将这些标志值定义为bool类型,不过这样要是设置的标志值一多,就会很浪费空间。

而假如定义一个整型数值,unsigned int flags; 在现在的系统,flags应该是32位, 用1,2,3....32将位进行编号,我们可以进行这样的判断, 当位1取1时,表示用读方式打开文件,当位2取1时,表示用写方式打开文件,当位3取1时,用二进制方式打开文件....因为flags有32位,就可以设置32个不同的状态值,也相当于32个bool类型。这样一方面省了空间, 另一方面也多了个好处,就是如前面所说的,可以将标志值组合起来。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

好啦,上面有点不清不楚的。下面看看到底怎么操作这些标志值。
设想C++的类ios这样定义, 其实没有这个类,只有ios_basic类,typedef basic_ios<char> ios;

class ios
{
public:
    enum {    app = 0x0001, ate = 0x0002, binary = 0x0004,
        in = 0x0008,  out = 0x0010, trunc = 0x0020 };
    ....
private:
    unsigned int flags;
};

注意上面enum语句中,每一个数值只有1位是1,其余是0,这个很重要,你可以将它化成2进制看看。

现在将flags相应的位设置为1, 可以这样做 flags |= app。这个等于flags = flags | app, 为什么呢? app只有1位是1,其余是0,因为0 | 1 = 0, 0 | 0 = 0, 这样0对应的位是不变的。而1 | 1 = 1, 1 | 0 = 1, 1对应的位不论原来是什么状态,都一定为1。如果想要将几个位都设置为1,可以这样做 flags |= (app | ate | binary)。因为每个enum常数各有一位为1, 与运算之后就有3位为1,就如上面的分析,就可以将那3位都设置为1, 其余位不变。这个就是标志可以组合起来用的原因。也可以用+组合起来,原因在于(下面的数字是2进制)0001 + 0010 + 0100 = 0111 跟与运算结果一样。不过不提倡用+, 考虑(app | ate | binary)要是我不小心写多了个标志值,(app | ate | ate | binary)结果还是正确的,如果用+的话,就会产生进位,结果就会错误。通常我们不知道原先已经组合了多少个标志值了,用或运算会安全。

现在将flags对应的位设置为0, 可以这样做 flags &= ~app。相当于 flags = flags & (~app). app取反之后,只有1位是0,其余是1,做与运算之后,1对应的位并不会改变,0对应的为不管原来是1是0,都肯定为0,这样就将对应的位设置了0。同样同时设置几个标志位可以这样做,flags &= ~(app | ate | binary)。

现在将flags对应的位,如果是1就变成0,如果是0就变成1,可以这样做 flags ^= app。同时设置几个标志位可以写成 flags ^= (app | ate | binary)。不再做分析了,不然就太罗嗦了。不过也给大家一个例子,你查查Ascii表,会发现对应的大小写字母是相差倒数第6位,可以用这样的函数统一的将大写变成小写,小写变成大写。
void xchgUppLow(string& letters)
{
        const unsigned int mask = (1<<5);

        for (size_t i=0; i<letters.length(); i++)
                letters[i] ^= mask;
}
前提是输入的string一定要全是字母, 而要想是操作字母,可以在原来基础上加个判断。

好啦,上面已经可以设置flags的对应位值了,要是判断呢?可以这样写 if (flags & app) 这样可以判断对应的位值是否为1, 因为C\C++语言中非0就真。app只有一位是1,其余是0,如果, flags的对应位也是0,在与操作下就得到结果0,反之非0,这样就可以判断标志位了。

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
上面关于标志值的操作就介绍完毕。其实在C++中已经有了个bitset了,没有必要去自己进行低阶的位运算,上面的四个操作在bitset中分别叫做set, reset, flip, test。不过在C中,这样的代码还很常见, 反正知道多点也没有坏处。

用 windows API 编程,你也经常会碰到这样的标志值,要互相组合,可以用|, 也可以用+(只是建议用|,理由上面说了). 它的标志值也是这样定义的,不过用#define
#define WS_BORDER    0x0001
#define WS_CAPTION    0x0002
......
当初我就是想不明白为什么可以用|或者用+来组合,现在知道了。

(注:上面出现的数字是我自己作的,到底实际怎么定义其实没有关系,只要保证只有一位是1,其余是0就可以的了. 因为编程的时候用的是常量值,没有人这样笨去直接用数值的)

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
其实,位运算还有很多用处。比如移位相当于乘除2的幂数(不过通常编译器也将乘除2的幂数优化成汇编的移位指令,所以没有必要不要这样卖弄了。汇编的移位指令有两组,分别针对有符号和无符号的, 我猜想在C\C++的同一移位运算针对有符号整数和无符号整数的不同,会根据情况编译成不同的汇编移位指令,不过没有去证实), 其实移位更用得多的地方是去构造一个掩码, 比如上面的mask = (1<<5);

还有&运算,有时候可以用来求余数。比如 value & (1<<4 - 1) 这相当于将value的高位全变成0了,效果等于 value % 8. 

还有值得一提的是^运算,它有个很特殊的性质。比如 A ^= B, 变成另一个数,跟着再执行A ^= B,又变回原来的数了,不信你可以列真值表或者化简逻辑式看看。就因为这个性质,^有很多用途。比如加密,你将原文看成A, 用同一个B异或一次,就相当于加密,跟着在用B异或一次,相当于解密。不过这样是很容易破解就是了。要是一个B不够,还可以加个C, 比如A ^= B, A ^= C, A ^= C, A ^= B, 恢复原状。

下面一个小程序,用异或交换两个数字。
int x = 3;
int y = 4;

x ^= y;
y ^= x;
x ^= y;

其实何止交换数字,连交换对象也可以的
template <typename T>
void swap(T& obj1, T& obj2)
{
        const int sizeOfObj = sizeof(T);
        char* pt1 = (char*)&obj1;
        char* pt2 = (char*)&obj2;

        for (size_t i=0; i<sizeOfObj; i++)
        {
                pt1[i] ^= pt2[i];
                pt2[i] ^= pt1[i];
                pt1[i] ^= pt2[i];
        }
}

还有异或操作还可以用在图象的光栅操作。我们知道,颜色也是用二进制来表示的,对颜色进行不同的位运算,就可以得到不同的光栅。因为异或的特殊性质,我们用异或操作的光栅画了副图,跟着再在原来的地方画一次,那副图就刷除了。这样可以用来显示动画而不用保存原来的画像信息。以前我写过个双人的贪食蛇,就用了异或光栅。因为背景色是白色的,也就是全1,作A ^ 1 = A, 所以用画刷画一次是画了设定的颜色,再画一次就恢复。最有趣的是两蛇相交的时候,颜色也会作异或叠加,产生一种新的颜色了,离开的时候也会自动恢复。
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
好啦,够长了,就停止吧。在最后再给大家一段代码,是用来看看对象在内存中的位值的。可以看看。
string bitsOfUChar(unsigned char c)
{
        const int numOfBitsInUChar = 8;
        unsigned int mask = (1<<7);
        string result(8, '0');

        for (size_t i=0; i<numOfBitsInUChar; i++)
        {
                if ( mask & c)
                        result[i] = '1';

                mask >>= 1;
        }

        return result;
}

template <typename T>
string bitsInMemory(const T& obj)
{
        int sizeOfObj = sizeof(obj);
        unsigned char* pt = (unsigned char*)&obj;
        string result;

        for (size_t i=0; i<sizeOfObj; i++)
        {
                result += bitsOfUChar(pt[i]);
                result += ' ';
        }

        return result;
}

比如bitsInMemory(12),会输出00001100 00000000 00000000 00000000, 我就知道我自己的机器是小尾顺序的了。