6.算法讲解之-面试题中位运算的妙用1

1.前言

        现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态，计算机对二进制数据进行的运算(+、-、*、/)的本质都是通过位运算进行的，即将符号位共同参与运算的运算。

由于位运算的特殊性，其在算法中有很多的使用。

2.位运算概览

        常用的位运算符号有 &(与)   |(或)   ~(非，也称取反)   ^(异或)   >>(右移)  <<(左移)

&(与)            两个位都为1，结果才为1。其他情况都为0

|(或)              两个位都为0，结果才为0。

~(取反)          0变1，1变0

^(异或)          相同为0，相异为1

>>(右移)       各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）。（vs2022中是逻辑右移）

<<(左移)        各二进位全部左移若干位，高位丢弃，低位补0

3.面试题

        3.1 打印一个数x的二进制位

正常思路

        定义一个数组ans。用x不断对2取余并保存再ans中，再除二。

代码如下

void print1(int x)
{
	int ans[32] = { 0 };
	int index = 31;
	while (x > 0)
	{
		ans[index--] = x % 2;
		x /= 2;
	}
	
	for (int i = 0; i < 32; i++)
		cout << ans[i];
    cout << endl;
}

        由于二进制的关系，我们把低位都放在右边，所以需要使用一个数组来存储,并从末端开始存入获得的数据。否则打印的就是逆序的二进制位了。

是不是略显麻烦？

下面我介绍一种使用&运算特点的方法

        我们知道&运算的同为1，在二进制中，1 2 4 8 16 32....这些数字中其二进制都只有一个1，其他位数都为0。如下例

1        00000000 00000000 00000000 00000001

2        00000000 00000000 00000000 00000010

4        00000000 00000000 00000000 00000100

8        00000000 00000000 00000000 00001000

...

其中的规律为后面的数字是前面的数字左移1位

如果我们将一个数依次与这些数字做&运算，那么我们就能够得到x所有位次是0还是1

如何快速的得到1 2 4 8 16 32 64...这些数字呢？只要让 1不断左移就行，如下

1=1<<0        2=1<<1        4=1<<2        8=1<<3

        最终得出的代码如下

void ptint2(int x)
{
	for (int i = 31; i >= 0; i--)
	{
		if (((1 << i) & (x)))
			cout << 1;
		else
			cout << 0;
	}
    cout << endl;
}

如果(1<<i)这个数字与x做&运算为真，说明x这一位是1，否则是0。

这样只要从高位开始打印即可

简单测试

测试代码如下    

void print1(int x)
{
	int ans[32] = { 0 };
	int index = 31;
	while (x > 0)
	{
		ans[index--] = x % 2;
		x /= 2;
	}
	
	for (int i = 0; i < 32; i++)
		cout << ans[i];
	cout << endl;
}
 
void print2(int x)
{
	for (int i = 31; i >= 0; i--)
	{
		if (((1 << i) & (x)))
			cout << 1;
		else
			cout << 0;
	}
	cout << endl;
}
 
int main()
{
	cout << "方法1" << endl;
	print1(11);
	print1(49);
 
	cout << "放法2" << endl;
	print2(11);
	print2(49);
	return 0;
	
}

        测试结果如下图

        由结果可知两种方法都正确的得出的结果

3.2 不用额外中间变量交换两个数

        常见的交换两个变量的方法通过一个中间变量保存的方法交互两个数。

而我们利用异或(^)的性质可以不用中间变量来交互两个数

代码如下

void MySwap(int &a, int &b)//注意要保证a和b在内存中的位置不能在一起
{
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}

原理如下         ^，同为0，异为1

        开始                        a=a           b=b

        执行a=a^b后          a=a^b        b=b

        执行b=a^b后          a=a^b        b=a^b^b，此时b^b为0，0^a为a，故此时b=a

        执行a=a^b后        a=a^b=a^b^a，同理a=b

最终的结果为        a=b,b=a。完成了交换

测试代码如下

void MySwap(int& a, int& b)//注意要保证a和b在内存中的位置不能在一起
{
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}
 
int main()
{
	int a = 1, b = 2;
	cout << "交换前" << a << " " << b << endl;
	MySwap(a, b);
	cout << "交换后" << a << " " << b << endl;
	return 0;
}

测试结果如下

3.3 找到一个数x的二进制位的第一个1，并且以10进制输出  

思路：

1.一个数与它的取反数做&运算的结果为0

//a	00111010 01011000 01011011 10000000	//一个数最低位的1后面肯定是0
//~a	11000101 10100111 10100100 01111111	//一个数取反之后，其第一个1的右边都为1

a&~a的结果一定是0

然后我们让~a+1

//~a+1	11000101 10100111 10100100 10000000	//加1之后，最低位的1又从零变为1

再让a&(~a+1)，即可找到最低位的1

而根据原码，反码，补码的知识知道 

一个数的负数是这个数的原码连同符号位取反+1

故可以写下如下代码

下篇文章我将继续讲解位运算的其他妙用！

1. 一个数组中只有一个数其数量为奇数，其他数字都为偶数。找出这个数

2.一个数组中有两种数出现了奇数次，其他数都出现了偶数次。找出这两个数 a,b

3.在一个数组中有一个数出现了M次，M>1,其他数都出现K次(K>M) 找出出现了K次的这个数

   要求:空间复杂度O(1) 时间复杂度O(n)