为何int类型布尔运算比bool更快？附LeetCode案例分析

在LeetCode「分割等和子集」的C解法中，原本使用vector<int>存储DP状态时耗时30-40ms，将其改为vector<bool>后功能正常，但耗时骤增至250-300ms（慢7-8倍），本地用g编译、time工具测试也复现了该结果。

原解法代码（vector版本） #

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (const auto &x: nums) sum += x;
        if (sum % 2) return false;

        vector<int> dp(sum/2+1, false);
        dp[0] = true;

        for(int idx=n-1;idx>=0;idx--) {
            for(int t=sum/2;t>0;t--) {
                if (nums[idx] <= t)
                    dp[t] = dp[t] || dp[t-nums[idx]];
            }
        }

        return dp[sum / 2];
    }
};

测试代码 #

int main() {
  vector<int> q(1000);
  for (int i=0;i<1000;i++) {
    q[i] = (i*10+7)%201 + 2;
  }

  Solution s;
  cout << s.canPartition(q) << endl;
  return 0;
}

性能差异的核心原因 #

• vector是比特压缩容器，非普通vector：C++标准里vector<bool>不是vector的常规特化，它会把每个元素压缩到1个比特位存储，而vector<int>的每个元素占4/8字节（依平台而定）。这种压缩带来两个关键问题：
  1. 位操作的额外开销：读写vector<bool>元素时，CPU无法直接操作单个比特，必须先读取整个字节/机器字，修改对应比特后再写回。这比直接读写int多了掩码、移位等操作，在循环密集的DP场景中，这些开销会被大幅放大。
  2. 缓存利用效率低：虽然vector<bool>内存占用小，但CPU缓存以缓存行（通常64字节）为单位加载。vector<int>一个缓存行能存8-16个元素，而vector<bool>的缓存行虽能存512个比特，但访问时需要频繁拆分重组，无法有效利用缓存的空间局部性。加上DP循环的混合访问模式，会导致更多缓存未命中，增加内存延迟。
• 编译器优化受限：vector<bool>的元素访问返回的是代理对象（vector<bool>::reference），而非直接的布尔值引用。这种机制会干扰编译器的优化（比如循环展开、向量化），而vector<int>的元素是直接可寻址对象，编译器能生成更高效的机器码。

内容的提问来源于stack exchange，提问作者Jalaj Kumar