位运算能做什么


1、int变量的奇偶性(变量A)

A&1 = 0 (偶数)
A&1 = 1 (奇数)

2、int变量第K位的操作。(变量A)

(A>>K)&1 (比特位)

A=A|(1<<K) (置位)

A=A&~(1<<K)(清零)

3、两整数的平均值(变量A、B)

(A & B) + ( (A ^ B) >> 1)

4、是否为2的整数次幂(变量A)

(x != 0) && (A & (A - 1)) == 0)

5、两整型变量的交换(变量A、B)

B ^=A;

A ^= B;

B ^= A;

6、计算整数的绝对值(变量A)

( (A ^ (A>>31)) - (A>>31) );

7、求相反数(变量A)

~A + 1

8、实现整数的加减乘除


//加法运算
int add(int a, int b)
{
	return b==0 ? a: add(a^b,(a&b)<<1);
}
 
//补码中正数转负数的原理
int negative(int a)
{
	return add(1,~a);
}
 
//减法运算
int sub(int a,int b)
{
	return add(a,negative(b));
}
 
//判断正负
bool isNegative(int a)
{
	return (a&INT_MIN)!=0; //INT_MIN只有最高位为1,其余位为0
}
 
 
//仅计算正数乘法
int multi_help(int a,int b)  
{  
    int result= 0;  
    while(b)  
    {  
        if(b&1) result = add(result, a);  
        a <<=1;  
        b >>= 1;  
    }  
    return result;  
} 
 
//乘法
int multi(int a,int b)
{
	if(isNegative(a))
	{
		if(isNegative(b))
			return multi_help(negative(a),negative(b));
		else
			return negative(multi_help(negative(a),b));
	}
	else
	{
		if(isNegative(b))
			return negative(multi_help(a,negative(b)));
		else
			return multi_help(a,b);
	}
}
 
//仅计算正数除法
int div_help(int a,int b)  
{  
	if(a<b) return 0;
	if(a==b) return 1;
    int result=0; 
	//第32位为符号位,所以从第31位开始
    for(int i=30;i>=0;i--)  
    {  
        if((a>>i)>=b)  
        {  
            result=add(result,1<<i);  
            a=sub(a,b<<i);  
        }  
    }  
    return result;  
}
//除法
int div(int a,int b)
{
	if(isNegative(a))
	{
		if(isNegative(b))
			return div_help(negative(a),negative(b));
		else
			return negative(div_help(negative(a),b));
	}
	else
	{
		if(isNegative(b))
			return negative(div_help(a,negative(b)));
		else
			return div_help(a,b);
	}
}

注:上面的算法看起来确实极其简洁正确,也在人群中广泛流传。但是涉及到部分细节的问题却鲜有人能考虑到,这也造成了只知其一不知其二而犯下大错。例如,5,两变量的交换,有多少人能想到如果传入的两变量是同一个数,这样的交换得到的结果是完全错误的。所以使用算法之前,请注意好前提条件(例如上面,两变量)。