0%

位运算

发表于 更新于 分类于
本文字数： 阅读时长 ≈

1，不用额外变量交换两个整数的值
题目：如何不用任何额外变量交换两个整数的值。
解答：给定a、b、c，以下三行代码就可以交换a和b的值

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

如何理解呢？理解异或运算符的特点：一个数异或另一个数两次得到的还是这个数。

2，不用任何比较判断找出两个数中较大的数
题目:给定两个32位的整数a和b，返回a和b中较大的数。
要求：不用任何比较。
解答：
方法一：得到a-b的值得符号，就可以知道是返回a还是返回b。具体请参看如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int flip(int n) {
	return n ^ 1;
}

public static int sign(int n) {
	return flip((n >> 31) & 1);
}

public static int getMax1(int a, int b) {
	int c = a - b;
	int scA = sign(c);
	int scB = flip(scA);
	return a * scA + b * scB;
}

方法二代码如下：

1
2
3
4
5
6
7
8
9
10
11
   public static int getMax2(int a, int b) {
	int c = a - b;
	int sa = sign(a);
	int sb = sign(b);
	int sc = sign(c);
	int difSab = sa ^ sb;
	int sameSab = flip(difSab);
	int returnA = difSab * sa + sameSab * sc;
	int returnB = flip(returnA);
	return a * returnA + b * returnB;
}

方法一是有局限性的，因为如果a和b的值溢出，返回结果会不正确。方法二解决了溢出的问题。