what does ADDR macro mean in c programming language

Question

I have met the following line multiple times in some coders' code. Appreciated if anyone could tell me the meaning of this Macro?

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

The following is an example of the codes from the internet that contains this macro. It looks like an implementation of some kind of balanced tree that claimed to have the ability to solve the problem of random query on k-th element in arbitrary sub-intervals of an fixed array in O(logn).

It looks like the ADDR macro is calculating some indexes of the intervals.

Is this macro some kind of trick? I also see this macro in the codes of other problems related to trees.

#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]);
}

so, "broken sum of values" + bit 0 set if both values differ... — Liviu Chircu, Mar 19 '18 at 19:44
Where do you find such strange macro? I've never seen before. — llllllllll, Mar 19 '18 at 19:44
Yes, But the issue is, in runtime, one will not know whether the bit 0 set is because of the addition or the difference in value. — Haris, Mar 19 '18 at 19:48
@Jean-FrançoisFabre Thank you for your answer! It looks x and y stands for the endpoint of some intervals like [0, 100], [0, 15] and I don't know what does it mean. I will upload parts of the codes. — Kingsmad, Mar 19 '18 at 20:01
What I understand till now is, If the values are same, the result is always even (common thing), if they are different, the result is always odd (since in even case, bit 0 is set). — Haris, Mar 19 '18 at 20:02
@Haris nice. But it destroys the first bit information when the values are different. Hardly useful. — Jean-François Fabre, Mar 19 '18 at 20:03
it either returns the full sum, if 'x == y' or it returns sum with the lower bit always set otherwise. — Serge, Mar 19 '18 at 20:04
also note that passing stuff like `i++` or `f(i)` to the macro kills the fun since expression is evaluated twice. — Jean-François Fabre, Mar 19 '18 at 20:04
@Jean-FrançoisFabre stuff like `i++` is probably not permitted here. — Haris, Mar 19 '18 at 20:05
@Jean-FrançoisFabre Can it be a way of testing number equality? may be for some architecture where addition is cheaper then comparison.. — Haris, Mar 19 '18 at 20:12
I doubt that. Nothing short circuits here. You get the work done for addition _and_ equality. — Jean-François Fabre, Mar 19 '18 at 20:18
Anyone who ever says "Code is self-documenting" can be refuted by this code. *Why* the bitwise-or of sum and the result of the `==` comparison? `build()`? Build *what*? C++ does have a **comment** feature. What is this code used for? And yes, the code that's now posted is C++. Oh, [and `using namespace std;` is a bad idea.](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Andrew Henle, Mar 19 '18 at 20:38
@Jean-FrançoisFabre it is puzzling that the code posted has `int p = ADDR(l, r)` in function `build` but then `if (l == r) { st[start] = ss[l]; return; }` and `p` was not used. Seems to destroy the point of the inequality test in the macro, might as well just set LSB anyway. — Weather Vane, Mar 19 '18 at 21:13
maybe it's a weak & fast key generator for a tree. The code is too long. I've got an election to watch :) — Jean-François Fabre, Mar 19 '18 at 21:21

Witnessthis · Answer 1 · 2018-03-19T20:10:06.273

2

'|' means "bitwise or" and "!=", "not equal". Hence your macro sums up x and y and if they are not equal, set the lowest bit of the sum to 1, else set it to 0.

Sum 1 and 3.

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

Evaluate the !=.

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

'|' the results.

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

Hence the expression returns 5 in this example.

edited Mar 19 '18 at 20:10

answered Mar 19 '18 at 20:03

Witnessthis

136
4

what does ADDR macro mean in c programming language

1 Answers1