【算法题】满足 a^b=c 的 (a, b) 对的个数

题目描述

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

对于任何整数 $x$，一定存在整数对 $(a, b)$，使得 $x \oplus a \oplus b$ 最大。其中，$\oplus$ 表示异或，$0≤x,a,b≤2^{31}-1$。给定一个 $x$，输出使得 $\vert a-b\vert $ 最小的 $(a, b)$ 对的个数。

示例：

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

异或运算的规则

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

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

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

题目解析

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

var TMAX32 = 1<<31 -1

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

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

左右同时异或 $x$，有：

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

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

不难看出，仅有当 $a$ 和 $b$ 中与 axorb 中的 1 对应的那些位是 0、1 交错的情况下，$\vert a-b\vert$ 才是最小的。比如当 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。因此使得 $\vert a-b\vert$ 最小的 $(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)
	}
}