亲宝软件园·资讯

展开

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

DeepLearnerC 人气:1

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

位运算

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

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

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

简单技巧

  1. 判断整型的奇偶
   if (x & 1)
       // 奇数
   else
       // 偶数
  1. 将一个数符号取反,即取相反数
int x;
x = ~x+1; //相反数
  1. 判断第n位是否设置为1
   if (x & (1 << n))
       // 是
   else
       // 否
  1. 将第n位设置为1
x = x | (1 << n);
  1. 将第n位设置为0
x = x & ~ (1 << n);
  1. 将第n位取反
x = x ^ (1 << n);
  1. 【】将最右边的1设为0
x = x & (x-1);

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

  1. 设置第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...的形式

  1. 设置第n到m位为0
#define SETBITS0(x, n, m) (x) & ~((~(0U)<<(sizeof(x)-(m-n+1)))>>n)
  1. 取第n到m位
#define GETBITSN_M(x, n, m) (x) & ((~(0U)<<(sizeof(x)-(m-n+1)))>>n)
  1. 取第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

  1. 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;
}
  1. 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;
	
}
  1. 求解八皇后问题

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

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);
	}	
}

加载全部内容

相关教程
猜你喜欢
用户评论