10.01_按位与

按位与

问题描述

按位与运算(&)是一种基本的位运算，当两个位都为1时结果为1，否则为0。常用于位掩码、状态判断等场景。
性质：越与越小。

基本操作

算法思想

两个位都为1时结果为1
可用于提取特定位
适用于状态判断和位掩码
时间复杂度 $\mathcal{O}(1)$

代码实现

c++
java
python

class Solution {
public:
    // 判断奇偶
    bool isEven(int n) {
        return (n & 1) == 0;
    }
    
    // 获取最低位的1
    int lowbit(int x) {
        return x & -x;
    }
    
    // 清除最低位的1
    int clearLowestOne(int x) {
        return x & (x - 1);
    }
    
    // 判断是否为2的幂
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

class Solution {
    // 判断奇偶
    public boolean isEven(int n) {
        return (n & 1) == 0;
    }
    
    // 获取最低位的1
    public int lowbit(int x) {
        return x & -x;
    }
    
    // 清除最低位的1
    public int clearLowestOne(int x) {
        return x & (x - 1);
    }
    
    // 判断是否为2的幂
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

class Solution:
    # 判断奇偶
    def isEven(self, n: int) -> bool:
        return (n & 1) == 0
    
    # 获取最低位的1
    def lowbit(self, x: int) -> int:
        return x & -x
    
    # 清除最低位的1
    def clearLowestOne(self, x: int) -> int:
        return x & (x - 1)
    
    # 判断是否为2的幂
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

时间复杂度分析

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

基本按位与	$\mathcal{O}(1)$	$\mathcal{O}(1)$
lowbit	$\mathcal{O}(1)$	$\mathcal{O}(1)$
清除最低位1	$\mathcal{O}(1)$	$\mathcal{O}(1)$
判断2的幂	$\mathcal{O}(1)$	$\mathcal{O}(1)$

应用场景

位掩码操作
状态判断
权限控制
特征提取
优化计算

注意事项

运算优先级
符号位处理
位数限制
边界情况
性能考虑

常见变形

位掩码

cpp
java
python

class Solution {
public:
    // 设置位
    int setBit(int x, int pos) {
        return x | (1 << pos);
    }
    
    // 清除位
    int clearBit(int x, int pos) {
        return x & ~(1 << pos);
    }
    
    // 检查位
    bool checkBit(int x, int pos) {
        return (x & (1 << pos)) != 0;
    }
};

class Solution {
    // 设置位
    public int setBit(int x, int pos) {
        return x | (1 << pos);
    }
    
    // 清除位
    public int clearBit(int x, int pos) {
        return x & ~(1 << pos);
    }
    
    // 检查位
    public boolean checkBit(int x, int pos) {
        return (x & (1 << pos)) != 0;
    }
}

class Solution:
    # 设置位
    def setBit(self, x: int, pos: int) -> int:
        return x | (1 << pos)
    
    # 清除位
    def clearBit(self, x: int, pos: int) -> int:
        return x & ~(1 << pos)
    
    # 检查位
    def checkBit(self, x: int, pos: int) -> bool:
        return (x & (1 << pos)) != 0

状态判断

cpp
java
python

class Solution {
public:
    // 判断是否设置了所有位
    bool hasAllBits(int x, int mask) {
        return (x & mask) == mask;
    }
    
    // 判断是否至少设置了一位
    bool hasAnyBit(int x, int mask) {
        return (x & mask) != 0;
    }
    
    // 保留指定位
    int keepBits(int x, int mask) {
        return x & mask;
    }
};

class Solution {
    // 判断是否设置了所有位
    public boolean hasAllBits(int x, int mask) {
        return (x & mask) == mask;
    }
    
    // 判断是否至少设置了一位
    public boolean hasAnyBit(int x, int mask) {
        return (x & mask) != 0;
    }
    
    // 保留指定位
    public int keepBits(int x, int mask) {
        return x & mask;
    }
}

class Solution:
    # 判断是否设置了所有位
    def hasAllBits(self, x: int, mask: int) -> bool:
        return (x & mask) == mask
    
    # 判断是否至少设置了一位
    def hasAnyBit(self, x: int, mask: int) -> bool:
        return (x & mask) != 0
    
    # 保留指定位
    def keepBits(self, x: int, mask: int) -> int:
        return x & mask