我在一些编码员的代码中多次遇到下面的行。
如果有人能告诉我这个宏的含义,我将不胜感激?

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

下面是包含此宏的internet代码的示例。它看起来像是一种平衡树的实现,它声称能够解决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]);
}

最佳答案

“|”表示“按位或”和“!=”,“不相等”。因此,宏将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。

关于c - ADDR宏在C编程语言中意味着什么,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/49371098/

10-10 15:37