题目描述

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

对于任何整数 $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:

$\oplus$ 0 1
0 0 1
1 1 0

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

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

题目解析

记 32 位最大整数为 TMAX32,可以表示为:

var TMAX32 = 1<<31 -1

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

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

\[x \oplus a\oplus b = TMAX32\]

左右同时异或 $x$,有:

\[a\oplus b = x \oplus TMAX32\]

将上式的计算结果记作变量 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)
	}
}