位运算包括与运算(and &),或运算(or |), 取反运算（~），左移运算(<<)，右移运算(>>)。运算规则不多说，主要看看位运算的应用。

1. 乘除法运算。

利用左移可以实现2次幂乘法运算，比如比如n * 8, 则 n << 3，而n * 9 ,可以写成 n + （n << 3）;除法运算同理。

2、加减法运算。

先做无进位加法，即1 + 1 = [1]0, 进位去丢掉，即异或运算。然后加上进位，显然只有1 + 1才会产生进位10, 我们可以写成 (1 & 1 ) << 1即进位可以先做与运算再左移以为得到，根据这样的思路，c代码为：

int add(int a, int b)
{
	if (a == 0)
		return b;
	if (b == 0)
		return a;
	int t = a ^ b;
	int c = (a & b) << 1;
	return add(t, c);
}
int sub(int a, int b)
{
	return add(a, add(~b, 1));
}

3、交换两个数。

我们知道x ^ x == 0, a ^ x ^ x == a;根据这个思路交换两个数为：

void swap(int &a, int &b)
{
	a ^= b; /* 此时a = a ^ b */
	b ^= a; /* b = b ^ a ^ b , 相当于 b = a; */
	a ^= b; /* a = a ^ a ^ b ，此时a = b */
}

4、把一个数的最低位1置0.

即1110变为1100, 1111变为1110,1000变为0000等。常规做法是找到最低位1,即不断用1左移做位与运算看看是否等于1,然后再设置该位为0。更简单的方法是直接与n-1做位与运算，即

n &= n - 1

5、计算一个数1的个数。

根据4,每次把最低位1设为0, 直到等于0.即

int count(int n)
{
	int c = 0;
	while (n) {
		c++;
		n &= (n - 1);
	}
	return c;
}

6、 判断奇偶性。

bool is_odd(int n)
{
	return n & 0x1;
}

7、奇偶校验。

8、若一个数组中除了一个重复奇数次外，其他数字均重复偶数次，求那个重复奇数次数的数。

如1, 1, 2, 2, 3则返回3。思路还是x ^x ^ x ... ^x，当有偶数个x时，结果为0, 奇数次数则为x，因此把数组所有元素异或起来，偶数次的必然抵掉掉，剩下一个奇数次的。

int oddNumber(int *a, int n)
{
	assert(a != NULL);
	assert(n > 0);
	int t = 0, i;
	for (i = 0; i < n; i++)
		t ^= a[i];
	return t;
}

9、获取整型最大值

#define INT_MAX (((unsigned int) -1) >> 1)
#define LONG_MAX (((unsigned long) -1) >> 1)
#define LLONG_MAX (((unsigned long long) -1) >> 1)

10、判断一个数是否2的幂，只要是2的幂，则这个数至多只有一个1。

bool is_pow_2(int n)
{
	return (n & (n - 1)) == 0;
}

11、另外还有设置某位，获取某位等，根据常识，不多解释。

还有更多关于位运算的应用技巧，以后想到或者看到，再补充。

• 相关文章
• 全局相关文章