LeetCode esay mid 记录

位运算（基础/性质/拆位/试填/恒等式/贪心/脑筋急转弯）

一、基础题

1486. 数组异或操作

感觉一般也用不到 emmm

灵茶山艾府传送门

推导过程可以结合官网部分观看
重点由两部分的结合

---

将特定部分转换为常见部分

---

    public static int xorOperation(int n, int start){int a = start / 2;int b = n & start & 1;  // 当n和start都为奇数时，b = 1return (xor(a + n - 1) ^ xor(a - 1) * 2 + 1);}// 计算从 0 到 n的异或和// 0 ^ 1 = 1 , ... ,  i ^ (i+1) = 1;// 令 n = 4k + (1,2,3,4)// n = 4k + 1时， (n+1)/2 = (4k+2)/2 = 2k+1，等于有奇数个 i ^ (i+1) = 1，所以等于 1// n = 4k + 2时,  单独拿出一个n，这样就简化为4k+1的情况，最后等于 n ^ 1，即 (4k+2)^1 = 4k+3 = n+1// n = 4k + 3时， (n+1)/2 = (4k+4)/2 = 2k+2，等于有偶数个 i ^ (i+1) = 1, 最后等于 1 ^ 1 = 0// n = 4k + 4时， 单独拿出一个n，这样就简化为4k+3的情况，最后等于 n ^ 0，即 n
//    public static int xor(int n){
//        return switch(n % 4){
//            case 0 -> n;
//            case 1 -> 1;
//            case 2 -> n + 1;
//            default -> 0;
//        };
//    }public static int xor(int n) {int result;switch (n % 4) {case 0:result = n;break;case 1:result = 1;break;case 2:result = n + 1;break;default:result = 0;break;}return result;}

0到n的异或和表示

---

2595. 奇偶位数

0x555是十六进制数，转换为二进制为 0101 0101 0101

class Solution {public int[] evenOddBit(int n) {int mask = 0x555;return new int[]{Integer.bitCount(n & mask), Integer.bitCount(n & (mask >> 1))};}
}

231. 2 的幂

如果 n = 2的幂，则 n & (n-1) 一定等于 0

class Solution {static final int BIG = 1 << 30;public boolean isPowerOfTwo(int n) {return n > 0 && (n & (n-1)) == 0;}
}

342. 4的幂

在2的幂的基础上，加上n%3==1的特性

class Solution {public boolean isPowerOfFour(int n) {return n > 0 && (n & (n-1)) == 0 && n % 3 == 1;}
}

476. 数字的补数

class Solution {public int findComplement(int num) {int res = 0;for(int i = 0 ; num > 0; i++){int temp = num % 2;temp = temp == 1? 0:1;res += temp * Math.pow(2, i);num >>= 1;}return res;}
}

191. 位1的个数

class Solution {public int hammingWeight(int n) {int res = 0;while(n != 0){n &= n-1;res++;}return res;}
}

338. 比特位计数

class Solution {public int[] countBits(int n) {int[] res = new int[n + 1];for(int i = 0 ; i <= n; i++){res[i] = Integer.bitCount(i);}return res;}
}

1356. 根据数字二进制下 1 的数目排序

自定义排序

    public int[] sortByBits(int[] arr) {// 初始化// 0 <= arr[i] <= 10^4int[] bits = new int[10001];ArrayList<Integer> counts = new ArrayList<>();for(int i = 0 ; i < arr.length; i++){counts.add(arr[i]);bits[arr[i]] = Integer.bitCount(arr[i]);}counts.sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {if(bits[o1] != bits[o2]){return bits[o1] - bits[o2];}else{return o1 - o2;}}});int[] res = new int[arr.length];for(int i = 0; i < res.length; i++){res[i] = counts.get(i);}return res;}

461. 汉明距离

    public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y);}

2220. 转换数字的最少位翻转次数

    class Solution {public int minBitFlips(int start, int goal) {return Integer.bitCount(start ^ goal);}}

693. 交替位二进制数

    public boolean hasAlternatingBits(int n) {int a = n ^ (n >> 1);return (a & (a + 1)) == 0;}

二、与或（AND/OR）的性质

2980. 检查按位或是否存在尾随零

    public boolean hasTrailingZeros(int[] nums) {int even = nums.length;for (int x : nums) {even -= x % 2;}return even >= 2;}

2401. 最长优雅子数组

// 相当于退队while ((or & nums[right]) > 0) // 有交集or ^= nums[left++]; // 从 or 中去掉集合 nums[left]

// 相当于入队
or |= nums[right]; // 把集合 nums[right] 并入 or 中

class Solution {public int longestNiceSubarray(int[] nums) {int ans = 0;for (int left = 0, right = 0, or = 0; right < nums.length; right++) {while ((or & nums[right]) > 0) // 有交集or ^= nums[left++]; // 从 or 中去掉集合 nums[left]or |= nums[right]; // 把集合 nums[right] 并入 or 中ans = Math.max(ans, right - left + 1);}return ans;}
}