解题思路

1. 由于反转操作可以针对任意仪器的任意二进制位独立进行，问题可转化为：对于每一个二进制位，需要将所有仪器在该位上的值变成相同。
2. 对于第 $i$ 位，统计 $n$ 个读数中该位为 $1$ 的仪器数量 $\text{cnt}_1$ 和为 $0$ 的数量 $\text{cnt}_0$（显然 $\text{cnt}_0 = n - \text{cnt}_1$）。
3. 要使所有仪器在该位相等，有两种选择：
   • 将所有该位为 $0$ 的仪器反转成 $1$，需要 $\text{cnt}_0$ 次操作；
   • 将所有该位为 $1$ 的仪器反转成 $0$，需要 $\text{cnt}_1$ 次操作。
4. 该位的最小操作次数即为 $\min(\text{cnt}_0, \text{cnt}_1)$。
5. 由于每一位的决策相互独立，总最少操作次数等于所有二进制位最小操作次数之和。

题目内容

在一间实验室中，工程师记录了 $n$ 台仪器的读数，每个读数都是一个非负整数。他可以对任意一台仪器的读数进行操作：每次操作选定该读数二进制表示下的一个比特位，将其反转（即 $0$ 变为 $1$，$1$ 变为 $0$）。

工程师希望经过若干次这样的操作后，所有仪器的读数完全相等。请计算达成该目标所需的最少操作次数。

约束：读数个数 $n$ 不超过 $10^5$，每个读数 $a_i$ 满足 $0 \le a_i \le 2^{31}-1$。

输入描述

第一行包含一个正整数 $n$，表示仪器的数量。 第二行包含 $n$ 个非负整数，依次表示各仪器的初始读数，数之间用空格分隔。

输出描述

输出一个整数，表示让所有读数相等所需的最少反转操作次数。

样例1

输入

3
2 3 2

输出

1

说明

三个读数分别为 2、3、2，二进制表示依次为 10、11、10。

按位独立统计：

• 第 $0$ 位（最低位）：0 出现 2 次（来自两个 2），1 出现 1 次（来自 3），该位最少操作次数为 $\min(2,1)=1$。
• 第 $1$ 位：三个数均为 1，0 出现 0 次，1 出现 3 次，最少操作次数为 $\min(0,3)=0$。 更高位所有读数均为 0，操作次数为 $0$。

总最少操作次数为 $1+0=1$。实际操作可以是翻转 3 的第 $0$ 位，使其从 1 变为 0，从而三个数都变成 2。

样例2

输入

4
7 7 7 7

输出

0

说明

所有读数已经相等，均为 7。

在二进制下，每个比特位上的值完全一致，0 和 1 的计数中总有一方为 0，因此每一位的最少操作次数均为 $0$。总最少操作次数为 $0$。不需要任何操作。

样例3

输入

5
0 1 2 4 8

输出

4

说明

五个读数分别为 0、1、2、4、8。

考虑二进制低 $4$ 位（第 $0$ 位到第 $3$ 位）：

• 第 $0$ 位：1（来自 1）出现 1 次，0 出现 4 次，最少操作次数 $\min(1,4)=1$。
• 第 $1$ 位：1（来自 2）出现 1 次，0 出现 4 次，最少操作次数 $1$。
• 第 $2$ 位：1（来自 4）出现 1 次，0 出现 4 次，最少操作次数 $1$。
• 第 $3$ 位：1（来自 8）出现 1 次，0 出现 4 次，最少操作次数 $1$。 更高位所有读数均为 0。

总最少操作次数为 $1+1+1+1=4$。一种可行方案是将所有非零读数通过一次反转变为 0，总共需要 4 次操作。

样例4

输入

2
0 2147483647

输出

31

说明

两个读数分别为 0 和 2147483647（即 $2^{31}-1$）。

0 的二进制表示包含 $31$ 个 0，而 2147483647 的二进制表示包含 $31$ 个 1。 对于第 $0$ 位到第 $30$ 位，每一位上 0 出现 1 次，1 出现 1 次，该位最少操作次数为 $\min(1,1)=1$。 共 $31$ 位，因此总最少操作次数为 $31$。可以全部变为 0（将 2147483647 的 $31$ 个 1 逐一反转）或全部变为 2147483647（将 0 的 $31$ 个 0 逐一反转）。