题目描述

这是今晚阿里巴巴笔试编程题的其中一道。原题描述如下：

对于任何整数 x，一定存在整数对 (a,b)，使得 x⊕a⊕b 最大。其中，⊕ 表示异或，0≤x,a,b≤231−1。给定一个 x，输出使得 |a−b| 最小的 (a,b) 对的个数。

示例：

输入 0，输出 2
输入 100，输出 16

异或运算的规则

两个二进制位进行异或运算，相同为 0，不同为 1：

⊕ 0 1
0 0 1
1 1 0

异或满足交换律与结合律。异或两个重要的性质：

  • 一个数与自己异或等于 0，X⊕X=0
  • 任何数与 0 异或不变，0⊕X=X

题目解析

记 32 位最大整数为 TMAX32，可以表示为：

var TMAX32 = 1<<31 -1

其十六进制表示为 0x7FFFFFFF。见如何表示最大、最小的整数。

题目中要求「x⊕a⊕b 最大」，因此有：

x⊕a⊕b=TMAX32

左右同时异或 x，有：

a⊕b=x⊕TMAX32

将上式的计算结果记作变量 axorb，即 a⊕b = axorb。axorb 二进制的每一位由 a 和 b 的对应位通过异或运算得到。

题目中要求「|a−b| 最小」。根据异或的规则，如果 axorb 的某一位是 0，那么 a 和 b 的对应位相同，这些位不会影响 |a−b| 的大小；如果 axorb 的某一位是 1，那么 a 和 b 的对应位不同，这些位会影响 |a−b| 的大小。

不难看出，仅有当 a 和 b 中与 axorb 中的 1 对应的那些位是 0、1 交错的情况下，|a−b| 才是最小的。比如当 axorb 中有 3 个 1 时，则 a、b 中对应的位应该是 101、010；当 axorb 中有 4 个 1 时，则 a、b 中对应的位应该是 1010、0101…

对于 axorb 中的所有 1，a、b 的对应位共有 2 种情况，即 101..、010... 或 010..、101...。而对于 axorb 中的每个 0，a、b 的对应位有 2 种情况，即 0、0，或 1、1。因此使得 |a−b| 最小的 (a,b) 对的个数，就是 2 * 2 ^ axorb 的二进制除去第一位的 0 的个数，除去第一位是因为非负整数的二进制首位不能是 1。如果 axorb 二进制中没有 1，那么不 *2。具体见代码。

代码

func main() {
	n := 0 // 测试用例个数
	fmt.Scan(&n)

	tmax32 := 1<<31 - 1
	for i := 0; i < n; i++ {
		x := 0
		fmt.Scan(&x)
		axorb := tmax32 ^ x
		ans := 1
		if axorb != 0 { // 如果 axorb 二进制中有 1
			ans = 2 // 101... 010...，两种情况
		}
		for i := 0; i < 31; i++ { // 忽略第一位 0
			if axorb&1 == 0 {
				ans <<= 1
			}
			axorb >>= 1
		}
		fmt.Printf("%d\n", ans)
	}
}