题目

类型：位运算

解题思路

令 n 为 nums 的长度，利用 n 不超过 16 ，我们可以使用一个 int 数值来代指 nums 的使用情况（子集状态）。

假设当前子集状态为 state ，state 为一个仅考虑低 n 位的二进制数，当第 k 位为 1，代表 nums[k] 参与到当前的按位或运算，当第 k 位为 0，代表 nums[i] 不参与到当前的按位或运算。

在枚举这 个状态过程中，我们使用变量 max 记录最大的按位或得分，使用 ans 记录能够取得最大得分的状态数量。

代码

class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int n = nums.length, mask = 1 << n;
        int max = 0, ans = 0;
        for (int s = 0; s < mask; s++) {
            int cur = 0;
            for (int i = 0; i < n; i++) {
                if (((s >> i) & 1) == 1) cur |= nums[i];
            }
            if (cur > max) {
                max = cur; ans = 1;
            } else if (cur == max) {
                ans++;
            }
        }
        return ans;
    }
}