位运算常见面试题

请判断一个整数是否为奇数？

1
2
3
4
bool isOdd(int n) {
	//return n % 2 != 0;
	return n & 0x1;
}

如何判断一个整数是否为2的幂(1, 2, 4, 8, 16, …)？

1
2
3
4
5
6
7
8
9
10
bool isPowerOf2(int n) {
	//int i = 1;
	//while (i < n) {
	//	i *= 2;//i = 1, 2 ,4, 8 ,16 ...
	//}
	////i >= n
	//if (i == n) return true;
	//else return false;
	return (n & (n - 1)) == 0;
}

给定一个值不为0的整数，请找出值为1的最低有效位。(last set bit)

输入：n = 24

输出：8

解释：24的二进制表示为 11000，值为 1 的最低有效位为 2^3。

思路一：判断最低位是否为1，并依次往后移动1位，从而找到last set bit

1
2
3
4
5
6
7
8
9
10
11
12
13
int lastSetBit1(int n) {
	int cnt = 0;
	do{
		//最低位是一
		if (n & 0x1) {
			return cnt;
		}
		cnt++;
		n = n >> 1;
	} while (n);
	return -1;
}rn -1;
}

思路二：利用x + (-x) = 10…00(n个0)的性质

n: 1101 1000

-n: 0010 1000

两者 & 运算得到0000 1000就能判断last set bit

1
2
3
int lastSetBit2(int n) {
	return n & (-n);//直接得到2的k次方的值是多少
}

给定两个整数 a 和 b，请交换它们两个的值 (要求不使用中间临时变量)。

1
2
3
a = a ^ b;
b = a ^ b;
a = a ^ b;

如果写成调用函数的形式，记得写成引用类型的形式参数

1
2
3
4
5
6
void swap(int &a, int &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

给你一个 非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

输入：nums = [1,4,2,1,2]

输出：4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int findSingleNum(int num[], int n);
int main(void)
{
	
	int num[] = { 1, 4, 2, 1, 2 };
	int length = sizeof(num) / sizeof(int);
	int result = findSingleNum(num, length);
	printf("只出现一次的数字是%d\n", result);

	return 0;
}

int findSingleNum(int num[] ,int n) {
	int result = 0;
	for (int i = 0; i < n ; i++)
	{
		result = result ^ num[i];
	}
	return result;
}

如果不在主函数里面求出length的值，传参也不传int n，就不把length的值传进去的话，写成这样会报错：

C6384 用另一个值除指针的 sizeof 值

1
2
3
4
5
6
7
8
int findSingleNum(int num[]) {
	int result = 0;
	for (int i = 0; i < sizeof(num) / sizeof(int); i++)
	{
		result = result ^ num[i];
	}
	return result;
}

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。

输入：nums = [1,2,1,3,2,5]

输出：[3,5]

解释：[5, 3]也是有效的答案。

思路：通过lsb把原来的数组分成两组，一组有a, x1,x1,x2,x3,….xn,xn;另一组有b, y1,y1,y2,y2…ym,ym

从而套用第五题的做法得出a和b的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(void)
{
	int nums[] = { 1, 2, 1, 3, 2 , 5 };
	//求出 a ^ b
	int xor = 0;
	int length = sizeof(nums) / sizeof(int);
	for (int i = 0; i < length; i++)
		xor ^= nums[i];
	//xor = a ^ b
	//求xor的lastSetBit
	int lsb = xor &(-xor);
	//分成两组
	int a = 0, b = 0;
	for (int i = 0; i < length; i++)
		if (lsb & nums[i]) a ^= nums[i];
		else b ^= nums[i];
	printf("a = %d, b = %d", a, b);
	return 0;
}