Q. 条件分岐や算術演算を使わずに、max(a,b) を計算するプログラムを書けますか？

「if文（条件分岐）を使わず、max(a, b) を計算 別解 | 津田の開発な日記」に関連した話です。リンク先のブログ記事では、条件分岐を使わずにmax(a,b)を実装する方法が議論されています。

では、更に条件を厳しくして、「条件分岐も算術演算も使わずに」max(a,b)を実装することはできるでしょうか？

も
ち
ろ
ん
可
能
で
す


回
答
例
は
以
下
に
あ
り
ま
す

なぜ、「もちろん」なのか。CPUは、ANDやOR、NOTのようなデジタルな論理回路から構成されています。であれば、当然、ビット演算（ビットシフトと&, |, ^）を使って、max(a, b)を実装することも可能なわけです。こんな感じ。

#include <stdio.h>

#define BIT(n, pos) (((n) >> (pos)) & 1)

static int mymax(int a, int b)
{
  int islt = BIT(a, 31) & (BIT(b, 31) ^ 1);
  int iseq = BIT(a, 31) ^ BIT(b, 31) ^ 1;

#define CHECK_BIT(pos) do { \
  islt |= iseq & (BIT(a, pos) ^ 1) & BIT(b, pos); \
  iseq &= BIT(a, pos) ^ BIT(b, pos) ^ 1; \
} while (0)

  CHECK_BIT(30); CHECK_BIT(29); CHECK_BIT(28);
  CHECK_BIT(27); CHECK_BIT(26); CHECK_BIT(25); CHECK_BIT(24);
  CHECK_BIT(23); CHECK_BIT(22); CHECK_BIT(21); CHECK_BIT(20);
  CHECK_BIT(19); CHECK_BIT(18); CHECK_BIT(17); CHECK_BIT(16);
  CHECK_BIT(15); CHECK_BIT(14); CHECK_BIT(13); CHECK_BIT(12);
  CHECK_BIT(11); CHECK_BIT(10); CHECK_BIT(9); CHECK_BIT(8);
  CHECK_BIT(7); CHECK_BIT(6); CHECK_BIT(5); CHECK_BIT(4);
  CHECK_BIT(3); CHECK_BIT(2); CHECK_BIT(1); CHECK_BIT(0);

#undef CHECK_BIT

  /* extend flag to 32-bit mask */
  islt <<= 31;
  islt >>= 31;

  return (a & (islt ^ 0xffffffff)) | (b & islt);
}

int main(int argc, char **argv)
{
  int a, b;

  if (argc != 3) {
    fprintf(stderr, "Usage: %s a b\n", argv[0]);
    return 1;
  }
  if (sscanf(argv[1], "%d", &a) != 1) {
    fprintf(stderr, "%s is not a number\n", argv[1]);
    return 1;
  }
  if (sscanf(argv[2], "%d", &b) != 1) {
    fprintf(stderr, "%s is not a number\n", argv[2]);
    return 0;
  }

  printf("max(%d,%d) is %d\n", a, b, mymax(a, b));

  return 0;
}