题解 | 游游的除2操作

#include <iostream>
#include <vector>
using namespace std;

// 大致思路就是所有数的二进制表示的有效位都变成同样位数
//然后再计算这些同样有效位的二进制数集合他们的每一个共同位是否相同
//最后从最高有效位开始往后遍历，直到发现不同的第一个数位，从该数位到最后一个数位都应该移掉（不清楚自己列几个数试试就知道了）
void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n ; i++) {
        cin >> a[i];
    }

    // 所有数二进制表示，取每个数最高有效位，对这些最高有效位求最小值
    // 110，10，1的最高有效位的最小值为0（从0开始算）
    int high = 32;
    for(int i = 0; i < n ; i++) {
        int x = a[i];
        for(int j = 31; j >= 0 ; j--) {
            if (((x >> j) & 1) == 1) {
                high = min(high, j);
                b[i] = j;
                break;
            }
        }
    }

    // 把所有数的二进制有效位都变为high，同时计算移动次数
    int ans = 0;
    for(int i = 0; i < n ; i++) {
        int r = b[i] - high;
        a[i] = (a[i] >> r);
        ans += r;
    }

    // 计算从从0-high位中哪一位不同
    vector<int> tb(32, -1);
    for(int i = 0; i < n ; i++) {
        for(int j = 0; j <= high ; j++) {
            int bt = ((a[i] >> j) & 1);
            if (tb[j] == -2) {
                continue;
            } else if(tb[j] == -1) {
                tb[j] = bt;
            } else {
                if (tb[j] != bt) {
                    tb[j] = -2;
                }
            }
        }
    } 

    // 从最高有效位开始算，如果某个位不相同，后面都不同
    int cnt = 0;
    for(int i = high; i >= 0 ; i--) {
        if (tb[i] == -2) {
            cnt = i + 1;
            break;
        }
    }

    // 加上每个数后面移动的位数
    ans = ans + n * cnt;
    cout << ans;
}

int main() {
    solve();
    return 0;
}