设最终所有数变为的值为 \(u\)，\(\operatorname{bitcount}(x)\) 为 \(x\) 二进制上为 \(1\) 的位数，由题可得答案即为 \(\sum\limits_{i = 1}^n \operatorname{bitcount}(u - a_i)\)。
此时让 \(a_i\) 从小到大排序，答案即为 \(\sum\limits_{i = 1}^n \operatorname{bitcount}(u - a_n + (a_n - a_i))\)。
令 \(v = u - a_n, a_i = a_n - a_i\)，答案即为 \(\sum\limits_{i = 1}^n \operatorname{bitcount}(v + a_i)\)。
然后可以想到类似于数位 DP 枚举 \(v\) 二进制每位的数字一步一步往后推得到答案。
考虑每一步需要什么条件：
第 \(i\) 位，枚举得来；为 \(0\) 或 \(1\)，同理；\(a_j\) 第 \(i\) 为是否为 \(1\)，能 \(O(1)\) 求出；\(a_j\) 第 \(i - 1\) 位有没有进位，这个好像有点难解决，似乎只能 \(O(2^n)\)。
其实有一个比较贪心的想法，就是 \(a_j\) 前 \(i - 1\) 位（即 \(a_j\bmod 2^i\)）越大就越有可能进位，所以只需要在处理第 \(i\) 位时按 \(a_j\bmod 2^i\) 从大至小排序，这样就只用枚举前缀了，优化到了 \(O(n)\)。
设 \(f_{i, j}\) 为第 \(i\) 位产生了 \(j\) 个进位的答案最小值，现在考虑由 \(f_{i}\) 推到 \(f_{i + 1}\)。
设 \(a_{1}\sim a_{n}\) 第 \(i\) 位一共有 \(x\) 个 \(1\)，\(a_1\sim a_{j}\) 第 \(i\) 位一共有 \(y\) 个 \(1\)，于是可以得到：
- 第 \(i\) 位为 \(1\) 且进位，个数为 \(y\)；
- 第 \(i\) 位为 \(0\) 且进位，个数为 \(j - y\)；
- 第 \(i\) 位为 \(1\) 且不进位，个数为 \(x - y\)；
- 第 \(i\) 位为 \(0\) 且不进位，个数为 \(n - j - (x - y)\)。
考虑 \(v\) 第 \(i\) 位不同取值会有什么贡献：
- 为 \(0\)，则 1 情况会进位，23 情况会增加 \(1\) 的贡献，\(f_{i, j} + (j - y) + (x - y)\rightarrow f_{i + 1, y}\)；
- 为 \(1\)，则 123 情况会进位，14 情况会增加 \(1\) 的贡献，\(f_{i, j} + y + (n - j - (x - y))\rightarrow f_{i + 1, y +(j - y) + (x - y)}\)。
时间复杂度 \(O(n\log_2 n\log_2 \max\{a_i\})\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 60;
long long a[N];
int f[M + 2][N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
a[i] = a[n] - a[i];
}
// for (int i = 1; i <= n; i++) {
// printf("%lld ", a[i]);
// }
// printf("\n");
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 0; i < M; i++) {
sort(a + 1, a + n + 1, [&i](long long x, long long y) {
return (x & ((1ll << i) - 1)) > (y & ((1ll << i) - 1));
});
int x = 0;
for (int j = 1; j <= n; j++) {
x += ((a[j] >> i) & 1);
}
int y = 0;
for (int j = 0; j <= n; j++) {
// printf("%d ", f[i][j]);
y += ((a[j] >> i) & 1);
function<void (int&, int)> Min = [](int& a, int b) -> void {
a = min(a, b);
return ;
};
Min(f[i + 1][(y) + (j - y) + (x - y)], f[i][j] + y + (n - j - (x - y)));
Min(f[i + 1][y], f[i][j] + (j - y) + (x - y));
}
// printf("\n");
}
printf("%d\n", f[M][0]);
return 0;
}