面试题积累_01

1

如何判断一个数是否为奇数？

//常规方法
bool isOdd_Method1(int n)
{
	if (n % 2)
		return true;
	else
		return false;		 
}
//高效方法
bool isOdd_Method2(int n)
{
	//奇数的二进制形式最后一位一定是1
	return n & 0x1;
}

注：二进制除了最后一位其他均是2的倍数，故如为奇数，则二进制形式的最后一位一定为1.

2

如何判断一个整数是否为2的幂？

bool isPowerof2_Method1(unsigned n)
{
	unsigned i = 1;
	//i = 1,2,4,8,...
	while (i < n)
	{
		i <<= 1;
	}
	//i >= n
	return i == n;
}

bool isPowerof2_Method2(unsigned n)
{
	//2的整数幂的二进制形式，只有一位为1，其余均为0
	//此方法n不可以取0
	return (n * n - 1) == 0;
}

示例：

3

给定一个不为0的整数，找出last set bit.
例：
输入 0011 0100
输出 4

int lastSetBit(int n)
{
   return n & -n;
}

4

给定一个数组，里面的整数都是成对出现的，只有一个数例外，请找出这个数。
例：
输入：[1,2,3,4,4,5,2,3,1]
输出：5

关键要知道异或运算的性质：

• a ^ 0 = a
• a ^ a = 0
• a ^ b = b ^ a
• (a ^ b) ^ c = a ^ (b ^ c)

int findSigleNum(int arr[], int n)
{
	int sigleNum = 0;
	for (int i = 0; i < n; i++)
	{
		sigleNum ^= arr[i];
	}

	return sigleNum;
}

4_拓展

给定一个数组，里面的整数都是成对出现的，只有两个数例外，请找出这两个数。
例：
输入：[1,2,3,4,4,5,2,3,1,6]
输出：5 6

void findSigleNum(int arr[], int n, int* pa, int* pb)
{
	int tmp = 0;
	for (int i = 0; i < n; i++)
	{
		tmp ^= arr[i];
	}
	// 此时tmp = a ^ b,即要找的两个数的异或

	/*tmp有个特点，即它的二进制形式从右向左为1（异或运算，不同为1）的一位就是这两个不同的数第一个不相同的一位
	故根据此特征将整组数分为两组数，再分别在这两组数里找到例外的这个数即是最终结果*/
	int lastSetBit = tmp & (-tmp);
	for (int i = 0; i < n; i++)
	{
		if (arr[i] & lastSetBit)
		{
			*pa ^= arr[i];
		}
		else
		{
			*pb ^= arr[i];
		}
	}
}

原文链接：https://www.cnblogs.com/MyXjil/p/17080916.html