c - c语言中的ADDR宏是什么意思

Question

我在一些程序员的代码中多次遇到以下行。如果有人能告诉我这个宏的含义，我将不胜感激？

#define ADDR(x, y) (((x) + (y)) | ((x) != (y)))

以下是来自互联网的包含此宏的代码示例。它看起来像是某种平衡树的实现，声称能够解决 O(logn) 中固定数组的任意子区间内第 k 个元素的随机查询问题。

看起来 ADDR 宏正在计算区间的一些索引。

这个宏是不是有什么技巧？我在其他树相关问题的代码中也看到了这个宏。

#include <bits/stdc++.h>

const int maxn = 2e5 + 10;
const int maxm = 2e6 + 10;

#define AVG(x, y) (((x) + (y)) >> 1)
#define ADDR(x, y) (((x) + (y)) | ((x) != (y)))

using namespace std;

struct SegTree {
  int id, val;
} st[maxm], ss[maxn];

int lnum[maxm], lt[maxn], rt[maxn], tot;

bool cmp(const SegTree& a, const SegTree& b) { return a.val < b.val; }

void build(int l, int r, int start) {
  int mid = AVG(l, r), p = ADDR(l, r), i, j, k = start, sum = 0;

  if (l == r) {
    st[start] = ss[l];
    return;
  }

  lt[p] = tot;
  rt[p] = tot + mid - l + 1;
  tot += r - l + 1;
  build(l, mid, lt[p]);
  build(mid + 1, r, rt[p]);

  i = lt[p];
  j = rt[p];
  while (i <= lt[p] + mid - l && j < rt[p] + r - mid) {
    if (st[i].id < st[j].id) {
      st[k] = st[i++];
      lnum[k++] = ++sum;
    } else {
      st[k] = st[j++];
      lnum[k++] = sum;
    }
  }
  while (i <= lt[p] + mid - l) {
    st[k] = st[i++];
    lnum[k++] = ++sum;
  }
  while (j < rt[p] + r - mid) {
    st[k] = st[j++];
    lnum[k++] = sum;
  }
}

int query(int l, int r, int ls, int rs, int k, int start) {
  int mid = AVG(l, r), p = ADDR(l, r);
  int i = ls > 0 ? lnum[start + ls - 1] : 0, j = lnum[start + rs];

  if (l == r) return st[start].val;
  if (j - i >= k) return query(l, mid, i, j - 1, k, lt[p]);
  return query(mid + 1, r, ls - i, rs - j, k - j + i, rt[p]);
}

Answer 1

'|'表示“按位或”和“!=”、“不等于”。因此，您的宏对 x 和 y 求和，如果它们不相等，则将总和的最低位设置为 1，否则将其设置为 0。

将 1 和 3 相加。

    (1) 0001
    (3) 0011
--> (4) 0100

评估 !=。

    (1) 0001
    (3) 0011
--> (1) 0001

'|'结果。

    (4) 0100
    (1) 0001
--> (5) 0101

因此在这个例子中表达式返回 5。