位运算使用技巧及巧解算法题

位运算

简单的复习一下基本的位运算，这些使用技巧在下面都有用到。

// 按位与 & , 双1得1, 其他都得0，使用：比如设置某些位为0，或者取某些位
// 按位或 | ， 单1即可得1， 只有双0才得0，使用：比如设置某些位为1
// 异或 ^ ， 相同则为0，相反则为1，即 10相碰得1，使用：比如取某些位的相反位

//下面这四个一般用来构造某些特殊的二进制数
// 按位取反 ~  很简单，取反即可
// 左移 <<  把数向左移，右边空出来的补0
// （无符号数）逻辑右移 >>   把数往右移，左边空出来的补0，注意在C中只有无符号数才如此
// （有符号数）算术右移 >>    把数往右移，左边空出来的补符号位，即正数补0，负数补1，有符号数执行的是算术运算
// 在其他语言中可能有不同，比如Java中算术右移和逻辑右移就是不同的运算符： >>和>>>

简单技巧

1. 判断整型的奇偶

   if (x & 1)
       // 奇数
   else
       // 偶数

2. 将一个数符号取反，即取相反数

int x;
x = ~x+1; //相反数

3. 判断第n位是否设置为1

   if (x & (1 << n))
       // 是
   else
       // 否

4. 将第n位设置为1

x = x | (1 << n);

5. 将第n位设置为0

x = x & ~ (1 << n);

6. 将第n位取反

x = x ^ (1 << n);

7. 【】将最右边的1设为0

x = x & (x-1);

【重要技巧】即可得到比当前数二进位少1的数（且数值恰比当前数小）

8. 设置第n到m位为1（最左边为第0位）以下皆利用宏来实现

#define SETBITS1(x, n, m) (x) | ((~(0U)<<(sizeof(x)-(m-n+1)))>>n)

【注】：((~(0U)<<(sizeof(x)-(m-n+1)))>>n)是得到第n位到第m位为1，其他位为0，如00...000111111110000000...的形式

9. 设置第n到m位为0

#define SETBITS0(x, n, m) (x) & ~((~(0U)<<(sizeof(x)-(m-n+1)))>>n)

10. 取第n到m位

#define GETBITSN_M(x, n, m) (x) & ((~(0U)<<(sizeof(x)-(m-n+1)))>>n)

11. 取第n到m位的相反位

#define GET_REVERSE_BITS(x, n, m) (x) ^ ((~(0U)<<(sizeof(x)-(m-n+1)))>>n)

巧用位运算解算法题

1. 老鼠试毒问题
   有8个一模一样的瓶子，其中有7瓶是水，一瓶是毒药。任何喝下毒药的生物都会在一个星期之内死亡。现在你有三只老鼠和一星期的时间，如何检验哪个瓶子里是毒药？
   【解】
   1）把8个瓶子进行编号，0-7，使用二进制表示，如下：

   000
   001
   010
   011
   100
   101
   110
   111

2）将第一位是1的瓶子里的液体混合喂给第一只老鼠吃，将第二位是1的瓶子里的液体喂给第二只老鼠吃，将第三位是1的瓶子里的液体喂给第三只老鼠吃。之后即可根据老鼠的死亡情况确定是那一瓶液体有毒。
如：第1、3只老鼠死亡。即第一位、第三位是1的瓶子里必有毒，第二位是0，即为101瓶子里是毒药。
【总结】：老鼠即为所需的二进制位，假如现有1000瓶水，问你至少需要几只老鼠才能测出有毒的瓶子？2^10 = 1024 > 1000

2. Leetcode 232
   给定一个数，判定他是否可以用2的幂次方来表示，可以返回true，不可以返回false
   【常规解法】不断用2去除，或者从1 乘到大于等于该数为止。O(logn)
   【解】如果一个数是2的幂次方，则它必定可以表示为100....的形式，当然，0也可以，所以该数的二进制表示至多有一个1。则可以利用之前的将最后一个1设置为0的技巧，循环遍历至x为0为止。O(1)

int is2Power(int x)
{
    int y = abs(x);
    y &= (y-1); // 0也可以使用
    if (!y)
    	return 1;
    else
    	return 0;
}

3. Leetcode 232
   给定一个非负整数num， 对于0<=i<=num范围中的每个数字i，计算其二进制数中1的数目并将它们作为数组返回。
   【常规解法】对每个数字调用函数计算二进制数的数目。
   【解】利用x&(x-1)这个数比x的二进制位1的数目少1个

int bits[MAX] = {0};
int countBits(int num)
{
	int i;
	for (i = 1; i <= num; i++)
		bits[i] = bits[i&(i-1)]+1;
	
}

4. 求解八皇后问题

   八皇后问题，待补充解释说明

void queenSettle(row, colomn, Lline, Rline)
{
	int count = 0;
	//column二进制表示，1代表当前列之前行已经放置了棋子，不可再放棋子
	//Lline和Rline，表示之前行放置的棋子的左斜行和右斜行的位置，不可再放棋子
	int N = 8; // 8皇后问题
	if (row > = N)
	{
		//遍历到最后一行，最后一行无需在找，只需找到空的那一列即可，说明已经找到了符合的解法
		count++;
		return ;
	}
	// 取出当前行可放置皇后的格子
	bits = ~((column|Lline|Rline)) & ((1 << N)-1); //按位与是只取后N位，取反是为了保证将原来0表示可以放置棋子变成1可以放置棋子
	while(bits > 0)
	{
		//每次从当前行可用的格子中取出最右边位为1的格子放置皇后
		p = bits & -bits;
		//紧接着在下一行继续放皇后
		queenSettle(row+1, column|p, (Lline|p) << 1, (Rline|p) >> 1)
		//当前行最右边的格子已经选完了，将其置为0，表示已经这个格子已经遍历过
		bits = bits & (bits-1);
	}	
}