如何消除类游程编码的连续值范围存储逻辑中的分支？

你的核心需求是去掉原代码里的条件分支，通过std::adjacent_difference来定位布尔值连续true段的起始/结束位置，以下是具体实现思路和代码：

原代码逻辑回顾 #

这段代码用于追踪布尔值curr的连续true区间，记录每个区间的start和end，但依赖条件分支判断状态切换：

struct Range {
  int start;
  int end;
};

bool prev = false;
Range range;
std::vector<Range> result;
for (int i = 0; i < n; i++) {
  bool curr = ...; // 随机布尔值
  if (curr && !prev)
    range.start = i;
  if (!curr && prev){
    range.end = i-1;
    result.push_back(range);
  }
  prev = curr;
}
// 处理末尾的边界情况

无分支实现思路 #

1. 布尔值数值化：将curr的true/false转换为整数1/0，存入数组values，用数值运算替代布尔判断。
2. 计算相邻差值：用std::adjacent_difference生成差值数组diffs，差值的含义：
   • diffs[i] = 1：第i位从false（0）变为true（1），是true段的起始位置。
   • diffs[i] = -1：第i位从true（1）变为false（0），对应true段的结束位置为i-1。
   • diffs[0] = values[0]：如果为1，说明开头就是true段的起始。
3. 配对起始/结束位置：遍历差值数组，收集起始位置，遇到结束标记时生成Range并加入结果，最后处理末尾未闭合的true段。

具体代码实现 #

#include <vector>
#include <numeric> // 用于std::adjacent_difference

struct Range {
  int start;
  int end;
};

std::vector<Range> find_true_ranges(const std::vector<bool>& curr_values) {
  const int n = curr_values.size();
  if (n == 0) return {};

  // 1. 将布尔值转为1/0的整数数组
  std::vector<int> values(n);
  for (int i = 0; i < n; ++i) {
    values[i] = curr_values[i] ? 1 : 0;
  }

  // 2. 计算相邻差值
  std::vector<int> diffs(n);
  std::adjacent_difference(values.begin(), values.end(), diffs.begin());

  std::vector<Range> result;
  int current_start = -1;

  // 处理开头的true段
  if (diffs[0] == 1) {
    current_start = 0;
  }

  // 遍历差值数组，定位区间
  for (int i = 1; i < n; ++i) {
    // 检测起始标记：从0变1
    if (diffs[i] == 1) {
      current_start = i;
    }
    // 检测结束标记：从1变0
    else if (diffs[i] == -1) {
      result.push_back({current_start, i - 1});
      current_start = -1;
    }
    // 差值为0时，状态无变化，无需处理
  }

  // 处理末尾未闭合的true段
  if (current_start != -1) {
    result.push_back({current_start, n - 1});
  }

  return result;
}

进一步优化分支（可选） #

如果想要彻底消除显式分支，可以用数值映射的方式，比如通过数组索引或者位运算，但实际场景中上面的代码已经大幅简化了分支逻辑，且利用标准库函数提升了可读性。如果追求极致无分支，可以将差值的判断转化为索引偏移，例如：

// 示例：用数组映射替代if判断（仅思路，需根据实际调整）
const int offsets[3] = {-1, 0, 1}; // 对应差值-1、0、1的处理
for (int i = 1; i < n; ++i) {
  int idx = diffs[i] + 1; // 将-1/0/1转为0/1/2
  // 根据idx执行对应操作，比如用函数指针数组或者预定义逻辑
}

不过这种方式会牺牲可读性，除非有明确的性能需求，否则不推荐。

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