指定した値未満となるAND・OR・XOR演算の最大値を求めるCプログラム

2つの整数 k と n が与えられたとします。この課題では、1から n までの数値のすべてのペアに対して、ビット単位のAND（論理積）、OR（論理和）、XOR（排他的論理和）の3種類の演算を実行し、その結果が与えられた値 k よりも小さくなるようなペアの中から、各演算の最大値を求めます。

例えば、入力が n = 5、k = 5 の場合、出力は 4 3 4 となります。

これは、5以下の数値ペア間で行われるAND、OR、XOR演算のうち、k 未満となる結果の最大値がそれぞれ 4、3、4 であることを意味します。実際に確認してみると、AND の最大値は 4 & 5 = 4、OR の最大値は 1 | 2 = 3、XOR の最大値は 1 ^ 5 = 4 となり、いずれも与えられた値 k（=5）より小さいことがわかります。

解決のための手順

この問題を解くためには、以下の手順に従います。

• andMax := 0、orMax := 0、xorMax := 0 として初期化する
• value1 := 0、value2 := 0、value3 := 0 として初期化する
• i を 1 から n まで繰り返す：
  • j を i + 1 から n まで繰り返す：
    • value1 := i AND j
    • value2 := i OR j
    • value3 := i XOR j
    • もし value1 > andMax かつ value1 < k ならば、andMax := value1 と更新する
    • もし value2 > orMax かつ value2 < k ならば、orMax := value2 と更新する
    • もし value3 > xorMax かつ value3 < k ならば、xorMax := value3 と更新する
• 最後に andMax、orMax、xorMax の順に出力する

ポイントは、同じ数同士のペア（i = j）を除外するため、内側のループを j = i + 1 から始めることです。計算量は全ペアを調べるため O(n²) となります。

実装例

理解を深めるために、以下のC言語による実装例を見てみましょう。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void solve(int n, int k) {
   int andMax = 0, orMax = 0, xorMax = 0;
   int value1 = 0, value2 = 0, value3 = 0;
   for (int i = 1; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
         value1 = i & j;
         value2 = i | j;
         value3 = i ^ j;
         if (value1 > andMax && value1 < k)
            andMax = value1;
         if (value2 > orMax && value2 < k)
            orMax = value2;
         if (value3 > xorMax && value3 < k)
            xorMax = value3;
      }
   }
   printf("%d %d %d ", andMax, orMax, xorMax);
}

int main() {
   solve(5, 5);
   return 0;
}

入力

5, 5

出力

4 3 4

このように、二重ループですべてのペアを走査しながら、条件「k 未満」を満たす最大値だけを各演算ごとに記録していくことで、シンプルかつ確実に答えを求めることができます。