位运算的拆位技巧

逃离我推掉我的手 2024-03-30 16:35 73阅读 0赞

## 题目引出 ##

给你一个下标从 **0** 开始的整数数组 `nums` 。

三个下标 `i` ，`j` 和 `k` 的 **有效值** 定义为 `((nums[i] | nums[j]) & nums[k])` 。

一个数组的 **xor 美丽值** 是数组中所有满足 `0 <= i, j, k < n` **的三元组** `(i, j, k)` 的 **有效值** 的异或结果。

请你返回 `nums` 的 xor 美丽值。(力扣周赛:[力扣][Link 1])

**注意：**

*  `val1 | val2` 是 `val1` 和 `val2` 的按位或。
 *  `val1 & val2` 是 `val1` 和 `val2` 的按位与。

这一题首先想到的肯定是暴力求解:回溯便可以求出来,代码如下

public int xorBeauty(int[] nums) {
            backTracking(nums);
            int res = 0;
            for (Integer integer : result) {
                res ^= integer;
            }
            return res;
    
        }
    
        ArrayList<Integer> list = new ArrayList<>();
    
        public void backTracking(int[] nums) {
            if (list.size() == 3) {
                result.add((list.get(0) | list.get(1)) & list.get(2));
                return;
            }
            for (int i = 0; i < nums.length; ++i) {
                list.add(nums[i]);
                backTracking(nums);
                list.remove(list.size() - 1);
            }
        }

这样的时间复杂度是很高的,因此我们不采用这种方法

因为这是| & ^运算,因此每一bite上的数字必然是0或者1,并且不同位置上的0和1是相互之间不影响的,只是对应位置上的相互影响,![8568faa4afea45279ae82fa5c34d60c9.png][]

设 含有三个比特位分别为a,b,c,

则(a|b)&c=1 则必须c=1,a和b有一个1的时候才成立

设这一共有n个元素,则一共一列共含有n个0或者1

设一共含有x个1,n-x个0

(a|b)&c=1 则有a|b为1则有:![n^2][n_2]\-![(n-x)^2][n-x_2]

(a|b)&c=1 有x(![n^2][n_2]\-![(n-x)^2][n-x_2])=x(2\*n\*x-![x^2][x_2])个

因为^运算的值为1时有奇数个1,则推导之后仅与x的数量有关,

**结论:因此有奇数个1,则异或之后的结果为1**

public int xorBeauty(int[] nums) {
            int res=0;
            for(int num:nums){
                res^=num;
            }
            return res;
    
        }

这一题也可以推出结论:详细见:[力扣][Link 2]

[Link 1]: https://leetcode.cn/problems/find-xor-beauty-of-array/description/
[8568faa4afea45279ae82fa5c34d60c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a7e610a5d2494721854f29944791de0b.png
[n_2]: https://latex.csdn.net/eq?n%5E2
[n-x_2]: https://latex.csdn.net/eq?%28n-x%29%5E2
[x_2]: https://latex.csdn.net/eq?x%5E2
[Link 2]: https://leetcode.cn/problems/find-xor-beauty-of-array/solutions/2050337/no6289-cha-xun-shu-zu-xor-mei-li-zhi-by-d5ylk/