我在一些编码员的代码中多次遇到下面的行。
如果有人能告诉我这个宏的含义,我将不胜感激?
#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/