奇妙的位运算

int32位 posted @ Nov 01, 2013 11:10:11 PM in c/cpp , 2052 阅读
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

位运算包括与运算(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、另外还有设置某位,获取某位等,根据常识,不多解释。

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

 

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter