位运算专题

分享丨【题单】位运算（基础/性质/拆位/试填/恒等式/思维） - 力扣（LeetCode）

Leetcode 3133. 数组最后一个元素的最小值

我的答案与思路：

class Solution {
public:
// 4 --> (100)2    7 --> (0111)2
// 5 --> (101)2    15--> (1111)2
// 6 --> (110)2
// 插入的时候①1 = (1)10 ②10 = (2)10 ③11 = (3)10 ④100 = (4)10 ⑤101 ⑥110 ⑦111string getBin(int x){string ans = "";while (x){if(x & 1)   ans += "1";else        ans += "0";x >>= 1;}reverse(ans.begin(), ans.end());return ans;}string getInsert(int n){int sit = n - 1;return getBin(sit);}long long minEnd(int n, int x) {// x 一定是整个数组中最小的string xbin = getBin(x);string inbin = getInsert(n);int idx = xbin.length() - 1;for(int i = inbin.length() - 1; i >= 0; i --){if(idx >= 0){while(idx >= 0 && xbin[idx] != '0'){idx --;}   // 找到第一个为"0"的地方if(idx < 0) xbin = inbin[i] + xbin;else    xbin[idx] = inbin[i];idx --;}elsexbin = inbin[i] + xbin;}// 将2进制string转换为十进制整数long long res = 0;for(auto& v: xbin){res <<= 1;res += (v - '0');}return res;}
};

更加优雅的实现方式：从集合论的角度进行实现

class Solution {
public:long long minEnd(int n, int x) {n --;   // 插入数位就是n - 1long long res = x;int i = 0, j = 0;while (n >> j){if((res >> i & 1) == 0){   // 当x的第i个bit是0(需要填入数)// 空位填入n的第j个bitres |= (long long) (n >> j & 1) << i;j ++;}i ++;}return res;}
};

优化方法：lowbit

        把 x 取反，用 lowbit 枚举其中的 1，就是要填的空位。

class Solution {
public:long long minEnd(int n, int x) {n --;   // 插入数位就是n - 1long long res = x;int j = 0;for (long long t = ~x, lb; n >> j; t ^= lb){lb = t & -t;res |= (long long)(n >> j ++ & 1) * lb;}return res;}
};