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, 我就知道我自己的机器是小尾顺序的了。