10.02_按位或

按位或

问题描述

按位或运算(|)是一种基本的位运算，当两个位至少有一个为1时结果为1，否则为0。常用于位标记、状态合并等场景。
性质：越或越大。

基本操作

算法思想

至少一个位为1时结果为1
可用于设置特定位
适用于状态合并和标记设置
时间复杂度 $\mathcal{O}(1)$

代码实现

c++
java
python

class Solution {
public:
    // 设置位
    int setBit(int x, int pos) {
        return x | (1 << pos);
    }
    
    // 设置最低的n位
    int setLowestBits(int x, int n) {
        return x | ((1 << n) - 1);
    }
    
    // 合并状态
    int mergeState(int state1, int state2) {
        return state1 | state2;
    }
    
    // 判断是否包含子集
    bool containsSubset(int set, int subset) {
        return (set | subset) == set;
    }
};

class Solution {
    // 设置位
    public int setBit(int x, int pos) {
        return x | (1 << pos);
    }
    
    // 设置最低的n位
    public int setLowestBits(int x, int n) {
        return x | ((1 << n) - 1);
    }
    
    // 合并状态
    public int mergeState(int state1, int state2) {
        return state1 | state2;
    }
    
    // 判断是否包含子集
    public boolean containsSubset(int set, int subset) {
        return (set | subset) == set;
    }
}

class Solution:
    # 设置位
    def setBit(self, x: int, pos: int) -> int:
        return x | (1 << pos)
    
    # 设置最低的n位
    def setLowestBits(self, x: int, n: int) -> int:
        return x | ((1 << n) - 1)
    
    # 合并状态
    def mergeState(self, state1: int, state2: int) -> int:
        return state1 | state2
    
    # 判断是否包含子集
    def containsSubset(self, set_: int, subset: int) -> bool:
        return (set_ | subset) == set_

时间复杂度分析

操作时间复杂度空间复杂度

基本按位或	$\mathcal{O}(1)$	$\mathcal{O}(1)$
设置位	$\mathcal{O}(1)$	$\mathcal{O}(1)$
合并状态	$\mathcal{O}(1)$	$\mathcal{O}(1)$
子集判断	$\mathcal{O}(1)$	$\mathcal{O}(1)$

应用场景

状态合并
权限设置
标记管理
集合运算
特征标记

注意事项

运算优先级
位数限制
状态冲突
溢出处理
性能优化

常见变形

权限管理

cpp
java
python

class Solution {
public:
    // 添加权限
    int addPermission(int current, int permission) {
        return current | permission;
    }
    
    // 批量添加权限
    int addPermissions(int current, vector<int>& permissions) {
        int result = current;
        for (int perm : permissions) {
            result |= perm;
        }
        return result;
    }
    
    // 检查是否有任一权限
    bool hasAnyPermission(int current, int permissions) {
        return (current & permissions) != 0;
    }
};

class Solution {
    // 添加权限
    public int addPermission(int current, int permission) {
        return current | permission;
    }
    
    // 批量添加权限
    public int addPermissions(int current, int[] permissions) {
        int result = current;
        for (int perm : permissions) {
            result |= perm;
        }
        return result;
    }
    
    // 检查是否有任一权限
    public boolean hasAnyPermission(int current, int permissions) {
        return (current & permissions) != 0;
    }
}

class Solution:
    # 添加权限
    def addPermission(self, current: int, permission: int) -> int:
        return current | permission
    
    # 批量添加权限
    def addPermissions(self, current: int, permissions: List[int]) -> int:
        result = current
        for perm in permissions:
            result |= perm
        return result
    
    # 检查是否有任一权限
    def hasAnyPermission(self, current: int, permissions: int) -> bool:
        return (current & permissions) != 0

状态合并

cpp
java
python

class Solution {
public:
    // 合并多个状态
    int mergeStates(vector<int>& states) {
        int result = 0;
        for (int state : states) {
            result |= state;
        }
        return result;
    }
    
    // 设置状态区间
    int setStateRange(int x, int start, int len) {
        int mask = ((1 << len) - 1) << start;
        return x | mask;
    }
    
    // 合并带优先级的状态
    int mergePriorityStates(int highPriority, int lowPriority) {
        return highPriority | (lowPriority & ~highPriority);
    }
};

class Solution {
    // 合并多个状态
    public int mergeStates(int[] states) {
        int result = 0;
        for (int state : states) {
            result |= state;
        }
        return result;
    }
    
    // 设置状态区间
    public int setStateRange(int x, int start, int len) {
        int mask = ((1 << len) - 1) << start;
        return x | mask;
    }
    
    // 合并带优先级的状态
    public int mergePriorityStates(int highPriority, int lowPriority) {
        return highPriority | (lowPriority & ~highPriority);
    }
}

class Solution:
    # 合并多个状态
    def mergeStates(self, states: List[int]) -> int:
        result = 0
        for state in states:
            result |= state
        return result
    
    # 设置状态区间
    def setStateRange(self, x: int, start: int, length: int) -> int:
        mask = ((1 << length) - 1) << start
        return x | mask
    
    # 合并带优先级的状态
    def mergePriorityStates(self, high_priority: int, low_priority: int) -> int:
        return high_priority | (low_priority & ~high_priority)