位运算详解

位运算

n的二进制表示中,第k位是几

1
2
3
//先把第k位移到最后一位,n>>k
//看最后一位是几,x&1

lowbit(x),返回x的最后一位1的位置

1
2
3
4
int lowbit(int x)
{
return x&(-x);
}

消去x最后一个的1

1
x&(x-1)

十进制数10的二进制为1010,9的二进制数为1001,那么(1010)&(1001)=1000,现在10的二进制中最后一位的1已经被消去

可以计算一个数的二进制中1的个数

1
2
3
4
5
6
7
8
9
10
int bitcount (unsigned int n)
{
int count=0 ;
while (n) {
count++ ;
n &= (n - 1) ;
}
return count ;
}

乘以2的m次方

1
x << m

除以2的m次方

1
x >> m

判断一个数的奇偶性

1
(n & 1) == 1//true为奇数,false为偶数

不用临时变量交换两个数

1
2
3
4
5
a ^= b ^= a ^= b;     
//或者,一样
a ^= b;
b ^= a;
a ^= b;

取绝对值

1
(n ^ (n >> 31)) - (n >> 31)

从低位到高位,取n的第m位

1
(n >> (m-1)) & 1;