for https://github.com/herumi/misc/blob/master/codec-calc.cpp

codec-calc.cc

// https://twitter.com/herumi/status/983496460753821696

int calc_mine(int a, int b, int s) {
  return a >> (32 - __builtin_clz(a ^ b));
  // return (a & b) >> (32 - __builtin_clz(a ^ b));
}

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

// https://github.com/herumi/misc/blob/master/codec-calc.cpp
int calc(int a, int b, int s) {
  const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
  assert(0 <= s && s <= 16 && b < a && a < Q * 4);
  int n = 0;
  for (;;) {
    if (a < Q2) {
      n = n * 2;
    } else if (b >= Q2) {
      n = n * 2 + 1;
      b -= Q2;
      a -= Q2;
    } else if (b >= Q && a < Q3) {
      b -= Q;
      a -= Q;
    } else {
      break;
    }
    b = b * 2;
    a = a * 2 + 1;
  }
  return n;
}

// b\a 0 1 2 3
// 0   A A D D
// 1   N A C D
// 2   N N B B
// 3   N N N B
int calc_mine1(int a, int b, int s) {
  const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3;
  assert(0 <= s && s <= 16 && b < a && a < Q * 4);
  int n = 0;
  for (;;) {
    int an = a >> s;
    int bn = b >> s;
    int ab = an >> 1;
    int bb = bn >> 1;

    if (an - bn >= 2)
      break;

    n <<= ab ^ bb ^ 1;
    n |= bb;
    int sub = (Q << bb) * ab;
    b -= sub;
    a -= sub;
    b = b * 2;
    a = a * 2 + 1;
  }
  return n;
}

int calc_mine2(int a, int b, int s) {
  const int QM = (1 << s + 1) - 1;
  int n = 0;
  for (;;) {
    int ab = a >> s + 1;
    int bb = b >> s + 1;
    if (ab ^ bb)
      break;

    n <<= 1;
    n |= bb;
    b &= QM;
    a &= QM;
    b = b << 1;
    a = a << 1 | 1;
  }
  return n;
}

int main() {
  int s = 3;
  for (int a = 1; a < (1 << s) * 4; a++) {
    printf("a=%2d ", a);
    for (int b = 0; b < a; b++) {
      printf("%2d ", calc(a, b, s));
    }
    printf("\n");
  }

  bool ok = true;
  for (int s = 0; s <= 10; s++) {
    for (int a = 1; a < (1 << s) * 4; a++) {
      for (int b = 0; b < a; b++) {
        int expected = calc(a, b, s);
        int actual = calc_mine(a, b, s);
        if (expected != actual) {
          printf("expected=%d actual=%d for a=%d b=%d s=%d\n",
                 expected, actual, a, b, s);
          ok = false;
        }
      }
    }
  }

  for (int s = 11; s <= 16; s++) {
    for (int i = 0; i < 10000; i++) {
      int a = rand() % ((1 << s) * 4 - 1) + 1;
      int b = rand() % a;
      int expected = calc(a, b, s);
      int actual = calc_mine(a, b, s);
      if (expected != actual) {
        printf("expected=%d actual=%d for a=%d b=%d s=%d\n",
               expected, actual, a, b, s);
        ok = false;
      }
    }
  }

  if (ok)
    puts("OK");
}

a & b じゃなくて単に a でいいだろって思った