LeetCode 416
1. 报错代码
// 01背包，从n个数字里面选，能否凑出和为s的方案
class Solution {
public:
bool canPartition(vector<int>& nums) {
int m = accumulate(nums.begin(), nums.end(), 0);
if(m & 1) return false;
m >>= 1;
vector<bool> dp(m + 1);
dp[0] = true;
for(auto &x : nums) {
for(int j = m; j >= x; j -- ) {
dp[j] |= dp[j - x];
}
}
return dp[m];
}
};
2. 错误信息
Line 13: Char 23: error: no viable overloaded '|='
13 | dp[j] |= dp[j - x];
| ~~~~~ ^ ~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/cstddef:168:3: note: candidate function not viable: no known conversion from 'reference' (aka 'std::_Bit_reference') to 'byte &' for 1st argument
159 | operator|=(byte& __l, byte __r) noexcept
| ^ ~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/ios_base.h:104:3: note: candidate function not viable: no known conversion from 'reference' (aka 'std::_Bit_reference') to '_Ios_Fmtflags &' for 1st argument
95 | operator|=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b) _GLIBCXX_NOTHROW
| ^ ~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/ios_base.h:154:3: note: candidate function not viable: no known conversion from 'reference' (aka 'std::_Bit_reference') to '_Ios_Openmode &' for 1st argument
145 | operator|=(_Ios_Openmode& __a, _Ios_Openmode __b) _GLIBCXX_NOTHROW
| ^ ~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/ios_base.h:201:3: note: candidate function not viable: no known conversion from 'reference' (aka 'std::_Bit_reference') to '_Ios_Iostate &' for 1st argument
192 | operator|=(_Ios_Iostate& __a, _Ios_Iostate __b) _GLIBCXX_NOTHROW
| ^ ~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/charconv:646:3: note: candidate function not viable: no known conversion from 'reference' (aka 'std::_Bit_reference') to 'chars_format &' for 1st argument
637 | operator|=(chars_format& __lhs, chars_format __rhs) noexcept
| ^ ~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/future:185:18: note: candidate function not viable: no known conversion from 'reference' (aka 'std::_Bit_reference') to 'launch &' for 1st argument
176 | inline launch& operator|=(launch& __x, launch __y) noexcept
| ^ ~~~~~~~~~~~
1 error generated.
3. 为什么bool类型需要占用1字节
bool 明明只用来存储 01 两个二进制数据，按理来说一个 bit 就够了，为什么 sizeof(bool)=1 呢？
这是因为计算机硬件对内存的访问以 字节（Byte） 为最小单位。即使一个变量只需要 1 比特的空间，系统也无法直接操作单个比特。
- 硬件限制：CPU 的指令集通常以字节为单位读写内存，直接操作比特需要额外的位掩码（Bitmask）和位移操作，这会降低性能。
- 地址对齐：若
bool占 1 比特，多个bool变量可能共享一个字节的地址，但读写时需要复杂的位操作，且无法保证原子性（线程安全问题）。
其次，直接操作字节比操作比特更高效：
减少指令开销：访问一个字节只需一条内存读取指令，而操作一个比特需要：
读取整个字节
用掩码提取目标比特
修改比特
将修改后的字节写回内存
缓存友好性：字节对齐的数据更符合 CPU 缓存行的设计（通常 64 字节/行），频繁的位操作可能导致缓存未命中，降低性能。
如果确实需要节省内存，可通过以下方式实现 比特级存储：
(1) 位域（Bit Fields）
在结构体中显式定义比特字段：
struct PackedBools {
bool flag1 : 1; // 占用 1 比特
bool flag2 : 1;
bool flag3 : 1;
// 剩余 5 比特未使用
};
// sizeof(PackedBools) = 1 字节（存储 3 个布尔值）
- 优点：显式控制比特分配，节省内存。
- 缺点：访问效率低，无法直接取地址，且不同编译器的位域实现可能不同。
(2) std::bitset
固定大小的比特集合，支持位操作：
#include <bitset>
std::bitset<8> flags; // 8 比特（1 字节）
flags[0] = true; // 访问第 0 位
flags |= 0b00001111; // 位运算
- 优点：内存紧凑，支持位运算。
- 缺点：大小必须在编译时确定，无法动态调整。
(3) vector<bool> 的特化
std::vector<bool> 是标准库中唯一压缩存储的容器，每个元素占 1 比特：
std::vector<bool> vec(8, false); // 仅占 1 字节
vec[0] = true; // 通过代理对象操作
- 优点：动态大小，内存高效。
- 缺点：返回代理对象（非
bool&），部分操作受限（如auto&、|=）。
4. vector<bool>
std::vector<bool> 是 C++ 的特殊容器，其内部使用位压缩（每个元素占 1 个比特位）。访问元素时返回的是 std::_Bit_reference 类型的代理对象，而不是直接的 bool&。这个代理对象不支持位运算的复合赋值操作符（如 |=, &=, ^=），因此编译会报错。
在这里，我们可以替换 |= 为 ||=，因为前者是数值运算，后者是逻辑运算。
详细解释：
std::vector<bool>的特殊性- 普通
vector<T>的operator[]返回T&，但vector<bool>为了节省空间，用 1 个比特存储一个布尔值，因此返回的是std::_Bit_reference类型的代理对象。 - 代理对象只能模拟布尔值的读写，无法直接支持位运算的复合赋值。
- 普通
- 为什么
|=不合法？a |= b等价于a = a | b，但std::_Bit_reference没有重载operator|=。std::_Bit_reference支持operator=和operator bool()，但不支持位运算的复合操作符。
- 正确替代方案
- 布尔值的逻辑或 (
||) 是短路操作符，直接返回true或false。 - 通过
=赋值给代理对象，即可正确更新布尔值。
- 布尔值的逻辑或 (
额外建议：
如果性能敏感，可用 std::vector<char> 代替 std::vector<bool>（每个元素占 1 字节，但支持所有位操作）。例如：
std::vector<char> dp(target + 1, false);
// ...
dp[j] |= dp[j - x]; // 合法操作
5. 按位或运算符|
在 C++ 中，按位或运算（| 和 |=） 主要用于直接操作数据的二进制位。以下数据类型支持按位或运算：
1. 基础整数类型
所有 整型（Integral Types） 及其变体均支持按位或运算：
- 有符号整数：
int,short,long,long long - 无符号整数：
unsigned int,unsigned short, 等 - 字符类型：
char,unsigned char,signed char - 布尔类型：
bool（但bool的按位或运算可能不符合直觉，见下文注意事项）
示例：
int a = 0b1010; // 二进制 1010 (10)
int b = 0b1100; // 二进制 1100 (12)
int c = a | b; // 结果 0b1110 (14)
2. 枚举类型（Enum）
若枚举的底层类型（Underlying Type）是整型（默认是 int），则支持按位或运算：
enum Flags {
FlagA = 0b001,
FlagB = 0b010,
FlagC = 0b100
};
Flags f = FlagA | FlagB; // 结果为 0b011 (3)
3. 标准库类型
(1) std::bitset
专为位操作设计，支持 |、|= 等位运算：
#include <bitset>
std::bitset<4> a("1010");
std::bitset<4> b("1100");
auto c = a | b; // 结果 "1110"
a |= b; // 直接修改 a
(2) std::byte (C++17 起)
表示原始字节数据，支持位运算：
#include <cstddef>
std::byte x = std::byte{0b1010};
std::byte y = std::byte{0b1100};
std::byte z = x | y; // 结果 0b1110
4. 用户自定义类型
通过 运算符重载 可自定义 | 和 |= 的行为：
struct Bitmask {
int value;
Bitmask(int v) : value(v) {}
// 重载 |
Bitmask operator|(const Bitmask& other) const {
return Bitmask(value | other.value);
}
// 重载 |=
Bitmask& operator|=(const Bitmask& other) {
value |= other.value;
return *this;
}
};
Bitmask a(0b1010), b(0b1100);
Bitmask c = a | b; // 结果 0b1110
a |= b; // 修改 a 的值
5. 不支持按位或运算的类型
以下类型 不直接支持 | 或 |=：
- 浮点类型（
float,double）：按位运算对浮点数无意义。 - 指针类型：虽然指针是整数地址，但直接对其使用
|可能导致未定义行为。 - 非整数类类型（如
std::string、容器类）：除非显式重载运算符。 std::vector<bool>：虽然存储布尔值，但元素访问返回代理对象（不支持|=）。
注意事项: 关于 bool 的按位或运算
虽然 bool 是整型，但逻辑或（||）和按位或（|）的行为可能不同：
bool a = true, b = false;
bool c = a | b; // true（按位或：1 | 0 = 1）
bool d = a || b; // true（逻辑或：true || false = true）
但若需要将 bool 视为比特位参与位运算，建议先转换为 int 或 unsigned char。