10.01_按位与
按位与
问题描述
按位与运算(&)是一种基本的位运算，当两个位都为1时结果为1，否则为0。常用于位掩码、状态判断等场景。
性质：越与越小。
基本操作
算法思想
- 两个位都为1时结果为1
- 可用于提取特定位
- 适用于状态判断和位掩码
- 时间复杂度
代码实现
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
时间复杂度分析
| 基本按位与 | ||
| lowbit | ||
| 清除最低位1 | ||
| 判断2的幂 |
应用场景
- 位掩码操作
- 状态判断
- 权限控制
- 特征提取
- 优化计算
注意事项
- 运算优先级
- 符号位处理
- 位数限制
- 边界情况
- 性能考虑
常见变形
- 位掩码
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
- 状态判断
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
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
