常见位运算
1．任何一个数和0异或是它的本身：
a^0=a
a^a=0
void swap(int *a, int *b)
{
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
1） 将第n位置位或清零：
#define BITN (1<<n)
置位：a
|= BITN;
清零：a
&= ~BITN
2） 清除整数a最右边的1。
方法：a
& (a – 1)
问题：如何判断判断整数x的二进制中含有多少个1？
分析：此题是微软公司的一道笔试题。下面用&运算来解决此题。
代码如下：
int func(int x )
{
int countx = 0;
while ( x )
{
countx ++;
x = x&(x-1);
}
return countx;
}
|
功能 |
示例 |
位运算 |
|
去掉最后一位 |
(101101->10110) |
x >> 1 |
|
在最后加一个0 |
(101101->1011010) |
x << 1 |
|
在最后加一个1 |
(101101->1011011) |
(x << 1)
+ 1 |
|
把最后一位变成1 |
(101100->101101) |
x | 1 |
|
把最后一位变成0 |
(101101->101100) |
(x | 1)
- 1 |
|
最后一位取反 |
(101101->101100) |
x ^ 1 |
|
把右数第k位变成1 |
(101001->101101,k=3) |
x | (1
<< (k
- 1)) |
|
把右数第k位变成0 |
(101101->101001,k=3) |
x & ~
(1 << (k
- 1)) |
|
右数第k位取反 |
(101001->101101,k=3) |
x ^ (1 << (k
- 1)) |
|
取末三位 |
(1101101->101) |
x & 7 |
|
取末k位 |
(1101101->1101,k=5) |
x & ((1
<< k) - 1) |
|
取右数第k位 |
(1101101->1,k=4) |
x >> (k
- 1) &
1 |
|
把末k位变成1 |
(101001->101111,k=4) |
x | ((1
<< k )- 1) |
|
末k位取反 |
(101001->100110,k=4) |
x ^ ((1
<< k)
- 1) |
|
去掉整数最右边的1 |
(100101111->100101110) |
x & (x
– 1) |
|
把右边连续的1变成0 |
(100101111->100100000) |
x & (x
+ 1) |
|
把右起第一个0变成1 |
(100101111->100111111) |
x | (x
+ 1) |
|
把右边连续的0变成1 |
(11011000->11011111) |
x | (x
- 1) |
|
去掉右起第一个1的左边 |
(100101000->1000) |
x & (x ^ (x
- 1)) |
|
取右边连续的1 |
(100101111->1111) |
(x ^ (x + 1)) >> 1 |
