M.Hiroi's Home Page

Linux Programming

お気楽C++プログラミング超入門

[ PrevPage | C++ | NextPage ]

整数の論理演算とビット操作

今回はC++のビット操作について説明します。

●ビット演算子

C++のビット演算子を下表に示します。

表 : ビット演算子
演算子操作
x & y ビットごとの論理積
x | y ビットごとの論理和
x ^ y ビットごとの排他的論理和
~x ビットごとの否定
x << y x を y ビット左シフト
x >> y x を y ビット右シフト

演算子 & はビットごとの論理積を返します。

5 & 3 => 1
     0101
 AND 0011
---------
     0001

演算子 l はビットごとの論理和を返します。

5 | 3 => 7
    0101
 OR 0011
--------
    0111

演算子 ^ はビットごとの排他的論理和を返します。

5 ^ 3 => 6
     0101
 XOR 0011
---------
     0110

演算子 ~ はビットごとの論理的な否定を返します。

~1 => -2
~0 => -1

<<, >> はビットをシフトする演算子です。左シフトの場合、下位ビットには 0 が挿入されます。右シフトの場合、正の整数 (または無符号整数) では上位ビットに 0 が挿入されます。負の整数では 1 が挿入されます。これを「算術シフト」といいます。

1 << 8 => 256
1 << 16 => 65536
256 >> 8 => 1
65536 >> 8 => 256
-256 >> 8 => -1

それでは簡単な例題として、基本的なビット操作関数を作ってみましょう。次のリストを見てください。

リスト : 基本的なビット操作 (sample3001.cpp)

#include <iostream>
using namespace std;

bool test_bit(int x, int n)
{
  return x & (1 << n);
}

int set_bit(int x, int n)
{
  return x | (1 << n);
}

int clear_bit(int x, int n)
{
  return x & ~(1 << n);
}

int main()
{
  cout << test_bit(256, 7) << endl;
  cout << test_bit(256, 8) << endl;
  cout << test_bit(256, 9) << endl;
  for (int i = 0; i < 8; i++) {
    int x = set_bit(0, i);
    cout << x << endl;
    cout << clear_bit(x, i) << endl;
  }
}

関数 test_bit は整数 x の n 番目のビットが 1 ならば true を返します。最下位 (LSB) のビットが 0 番目になります。int (32 bit) の場合、n は 0 から 31 になります。1 を n ビット左シフトして、x との論理積が 0 でなければ、n 番目のビットは 1 であることがわかります。

関数 bit_set は x の n 番目のビットを 1 にセットします。1 を n ビット左シフトして、x との論理和を計算すれば、n 番目のビットを 1 にすることができます。関数 clear_bit は x の n 番目のビットを 0 にクリアします。これは n 番目以外のビットを 1 に、n 番目のビットを 0 にして、それと x の論理積を計算すれば、n 番目のビットをクリアすることができます。1 を n ビット左シフトして、その否定を計算すると、n 番目のビット以外は 1 になります。

それでは実際に試してみましょう。

$ clang++ sample3001.cpp
$ ./a.out
0
1
0
1
0
2
0
4
0
8
0
16
0
32
0
64
0
128
0

●組み合わせの生成

組み合わせの生成は拙作のページ Yet Another C++ Problems で取り上げました。このほかに、n 個の中から m 個を選ぶ組み合わせは、ビットの 0, 1 で表すことができます。たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 番目 から 4 番目のビットに対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。簡単な例題として、ビットを使って組み合わせを求めてみましょう。

組み合わせを求めるプログラムは次のようになります。

リスト : 組み合わせの生成 (sample3002.cpp)

#include <iostream>
using namespace std;

void comb_sub(void (*f)(int), int n, int m, int a)
{
  if (m == 0)
    f(a);
  else if (m == n)
    f(a | ((1 << m) - 1));
  else {
    comb_sub(f, n - 1, m, a);
    comb_sub(f, n - 1, m - 1, a | (1 << (n - 1)));
  }
}

void combinations(void (*f)(int), int n, int m)
{
  comb_sub(f, n, m, 0);
}

void print_comb(int n)
{
  cout << hex << n << endl;
}

int main()
{
  combinations(print_comb, 5, 3);
}

関数 combinations は n 個の中から m 個を選ぶ組み合わせを生成して、引数の関数 f に渡します。実際の処理は関数 comb_sub で行います。組み合わせは引数 a にセットします。m が 0 になったら、組み合わせがひとつできたので f(a) を呼び出します。n が m と等しくなったならば、残り m 個を全て選びます。(1 << m) - 1 で m 個のビットをオンにして関数 f を呼び出します。

あとは comb_sub を再帰呼び出しします。最初の呼び出しは n 番目の数字を選ばない場合です。n - 1 個の中から m 個を選びます。次の呼び出しが n 番目の数字を選ぶ場合で、a の n - 1 番目のビットをオンにします。そして、n - 1 個の中から m - 1 個を選びます。

それでは 5 個の中から 3 個を選ぶ combinations(5, 3) の実行例を示します。

$ clang++ sample3002.cpp
$ ./a.out
7
b
d
e
13
15
16
19
1a
1c

この場合、最小値は 0x07 (111) で最大値は 0x1c (11100) になります。このように、combinations は組み合わせを表す数を昇順で出力します。

●組み合わせに番号を付ける方法

次は、N 通りある組み合わせに 0 から N - 1 までの番号を付ける方法を紹介しましょう。たとえば、6 個の中から 3 個を選ぶ組み合わせは 20 通りありますが、この組み合わせに 0 から 19 までの番号を付けることができます。1 1 1 0 0 0 を例題に考えてみましょう。次の図を見てください。


    図 : 6C3 の組み合わせ

最初に 5 をチェックします。5 を選ばない場合は \({}_5 \mathrm{C}_3\) = 10 通りありますね。この組み合わせに 0 から 9 までの番号を割り当てることにすると、5 を選ぶ組み合わせの番号は 10 から 19 までとなります。

次に、4 をチェックします。4 を選ばない場合は、\({}_4 \mathrm{C}_2\) = 6 通りあります。したがって、5 を選んで 4 を選ばない組み合わせに 10 から 15 までの番号を割り当てることにすると、5 と 4 を選ぶ組み合わせには 16 から 19 までの番号となります。

最後に、3 をチェックします。同様に 3 を選ばない場合は 3 通りあるので、これに 16 から 18 までの番号を割り当て、5, 4, 3 を選ぶ組み合わせには 19 を割り当てます。これで組み合わせ 1 1 1 0 0 0 の番号を求めることができました。

では、0 0 0 1 1 1 はどうなるのでしょうか。左から順番にチェックしていくと、最初の 1 が見つかった時点で、その数字を選ばない組み合わせは存在しません。つまり、残りの数字をすべて選ぶしかないわけです。したがって、これが 0 番目となります。このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができます。

●組み合わせを番号に変換

組み合わせを番号に変換するプログラムは次のようになります。

リスト : 組み合わせを番号に変換

// 組み合わせの数
int comb_num(int n, int r)
{
  if (n == r || r == 0)
    return 1;
  else
    return comb_num(n, r - 1) * (n - r + 1) / r;
}

// 組み合わせを番号に変換
int comb_to_num_sub(int c, int n, int r, int value)
{
  if (r == 0 || n == r)
    return value;
  else if (test_bit(c, n - 1))
    return comb_to_num_sub(c, n - 1, r - 1, value + comb_num(n - 1, r));
  else
    return comb_to_num_sub(c, n - 1, r, value);
}

int comb_to_num(int c, int n, int r)
{
  return comb_to_num_sub(c, n, r, 0);
}

関数 comb_num は組み合わせの数を求めます。comb_to_num の引数 c はビットのオンオフで表した組み合わせ、引数 n と r は \({}_n \mathrm{C}_r\) の n と r を表しています。実際の処理は comb_to_num_sub で行います。引数 value は求める番号を表します。n と r の値が同じになるか、もしくは r が 0 になれば、組み合わせの番号を計算できたので value を返します。

そうでない場合、c の n - 1 ビットの値を調べます。ビットがオンであれば、value に comb_num(n - 1, r) の値を足し算し、r を -1 して comb_to_num_sub を再帰呼び出しします。そうでなければ、value と r の値はそのままで comb_to_num_sub を再帰呼び出しします。

●番号を組み合わせに変換

逆に、番号から組み合わせを求めるプログラムも簡単に作ることができます。次のリストを見てください。

リスト : 番号を組み合わせに変換

// 番号を組み合わせに変換
int num_to_comb_sub(int value, int n, int r, int c)
{
  if (r == 0)
    return c;
  else if (n == r)
    return c | ((1 << n) - 1);
  else {
    int k = comb_num(n - 1, r);
    if (value >= k)
      return num_to_comb_sub(value - k, n - 1, r - 1, set_bit(c, n - 1));
    else
      return num_to_comb_sub(value, n - 1, r, c);
  }
}

int num_to_comb(int value, int n, int r)
{
  return num_to_comb_sub(value, n, r, 0);
}

引数 value が番号で、引数 n と r は \({}_n \mathrm{C}_r\) の n と r を表しています。実際の処理は num_to_comb_sub で行います。引数 c が求める組み合わせです。たとえば、n = 5, r = 3 の場合、ビットが 1 になるのは \({}_4 \mathrm{C}_2\) = 6 通りあり、0 になるのは \({}_4 \mathrm{C}_3\) = 4 通りあります。したがって、数値が 0 - 3 の場合はビットを 0 にし、4 - 9 の場合はビットを 1 にすればいいわけです。

ビットを 0 にした場合、残りは \({}_4 \mathrm{C}_3\) = 4 通りになるので、同様に次のビットを決定します。ビットを 1 にした場合、残りは \({}_4 \mathrm{C}_2\) = 6 通りになるので、value から 4 を引いて num_to_comb_sub を再帰呼び出しして次のビットを決定します。

r が 0 の場合は、組み合わせが完成したので c を返します。n と r が等しい場合は、残りのビットをすべて 1 にセットしてから c を返します。それ以外の場合は、\({}_{n-1} \mathrm{C}_r\) の値を comb_num(n - 1, r) で求めて変数 k にセットします。value が k 以上であれば変数 c のビットを 1 にセットし、value から k を引き算して num_to_comb_sub を再帰呼び出しします。そうでなければ、num_to_comb_sub を再帰呼び出しするだけです。

それでは、n = 5, r = 3 の場合の実行例を示します。

リスト : 簡単なテスト (sample3003.cpp)

int main()
{
  for (int i = 0; i < 10; i++) {
    int a = num_to_comb(i, 5, 3);
    cout << i << " -> " << a << " -> " << comb_to_num(a, 5, 3) << endl;
  }
}
$ clang++ sample3003.cpp
$ ./a.out
0 -> 7 -> 0
1 -> 11 -> 1
2 -> 13 -> 2
3 -> 14 -> 3
4 -> 19 -> 4
5 -> 21 -> 5
6 -> 22 -> 6
7 -> 25 -> 7
8 -> 26 -> 8
9 -> 28 -> 9

正常に動作していますね。この方法を使うと、n 個ある組み合わせの中の i 番目 (0 <= i < n) の組み合わせを簡単に求めることができます。

●ちょっと便利なビット操作

最も右側 (LSB 側) にある 1 を 0 にクリアする、逆に最も右側にある 0 を 1 にセットすることは簡単にできます。

(1) 右側にある 1 をクリア => x & (- x)

x     : 1 1 1 1
x - 1 : 1 1 1 0
----------------
 AND  : 1 1 1 0

x     : 1 0 0 0
x - 1 : 0 1 1 1
----------------
 AND  : 0 0 0 0

(2) 右側にある 0 を 1 にセット => x | (x + 1)

x     : 0 0 0 0
x + 1 : 0 0 0 1
----------------
  OR  : 0 0 0 1

x     : 0 1 1 1
x - 1 : 1 0 0 0
----------------
  OR  : 1 1 1 1

上図 (1) を見てください。x から 1 を引くと、右側から連続している 0 は桁借りにより 1 になり、最初に出現する 1 が 0 になります。したがって、x & (x - 1) を計算すると、最も右側にある 1 を 0 にクリアすることができます。(2) の場合、x に 1 を足すと、右側から連続している 1 は桁上がりにより 0 になり、最初に出現する 0 が 1 になります。x | (x + 1) を計算すれば、最も右側にある 0 を 1 にセットすることができます。

また、最も右側にある 1 を取り出すことも簡単にできます。簡単な例として 4 ビットの整数値を考えてみます。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。

 0 : 0000
 1 : 0001    -1 : 1111    1 & (-1) => 0001
 2 : 0010    -2 : 1110    2 & (-2) => 0010
 3 : 0011    -3 : 1101    3 & (-3) => 0001
 4 : 0100    -4 : 1100    4 & (-4) => 0100
 5 : 0101    -5 : 1011    5 & (-5) => 0001
 6 : 0110    -6 : 1010    6 & (-6) => 0010
 7 : 0111    -7 : 1001    7 & (-7) => 0001
             -8 : 1000

        図 : 最も右側にある 1 を取り出す方法

2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。したがって、x と -x の論理積 x & (-x) は、最も右側にある 1 だけが残り、あとのビットはすべて 0 になります。

●ビットが 1 の個数を求める

次は、ビットが 1 の個数を数える処理を作ってみましょう。データ型を Int とすると、プログラムは次のようになります。

リスト : ビットカウント

int bit_count(unsigned int n)
{
  int c = 0;
  unsigned int m = n;
  while (m != 0) {
    m &= m - 1;
    c++;
  }
  return c;
}

整数 n の右側から順番に 1 をクリアしていき、0 になるまでの回数を求めます。とても簡単ですね。32 個のビットを順番に調べるよりも高速です。

int を 32 bit とする場合、次の方法で 1 の個数をもっと高速に求めることができます。

リスト : ビットカウント (2)

int bit_count1(unsigned int n)
{
  unsigned int a = (n & 0x55555555) + ((n >> 1) & 0x55555555);
  unsigned int b = (a & 0x33333333) + ((a >> 2) & 0x33333333);
  unsigned int c = (b & 0x0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f);
  unsigned int d = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff);
  return (d & 0xffff) + (d >> 16);
}

最初に、整数を 2 bit ずつに分割して、1 の個数を求めます。たとえば、整数 n を 4 bit で考えてみましょう。5 を 2 進数で表すと 0101 になり、n と論理積を計算すると 0, 2 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。同様に n を 1 ビット右シフトして論理積を計算すると、1, 3 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。あとは、それを足し算すれば 2 bit の中にある 1 の個数を求めることができます。

変数 a には 2 ビットの中の 1 の個数が格納されています。左隣の 2 ビットの値を足し算すれば、4 ビットの中の 1 の個数を求めることができます。次に、左隣の 4 ビットの値を足し算して 8 ビットの中の 1 の個数を求め、左隣の 8 ビットの値を足し算して、というように順番に値を加算していくと 32 ビットの中にある 1 の個数を求めることができます。

bit_count は 1 の個数が多くなると遅くなりますが、bit_count1 は 1 の個数に関係なく高速に動作します。興味のある方は試してみてください。

●参考 URL

ビットが 1 の個数を数える方法は フィンローダさん初級C言語Q&A(15) を参考にさせていただきました。フィンローダさんに感謝いたします。


初版 2015 年 11 月 8 日
改訂 2023 年 4 月 15 日

N Queens Problem

「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。


       図 : 8 クイーンの解答例

N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。

●単純な解法の問題点

8 クイーンは拙作のページ Yet Another Clang Problems (4) で取り上げました。回転解や鏡像解を含めると全部で 92 通りあります。このとき作成したプログラムは順列を生成して、それが 8 クイーンの解を満たすかチェックする方法でした。この場合、クイーンの個数を増やすと、プログラムの実行時間は極端に遅くなります。単純な配列を使ってプログラムを作ると、次のようになります。

リスト : N Queens Problem

const int M = 20;

// 盤面
int board[M];
bool used[M];
int count;

// 衝突の検出
bool attack(int i)
{
  int n = 1;
  int x = board[i--];
  for (; i >= 0; i--, n++) {
    int y = board[i];
    if (x == y + n || x == y - n) return true;
  }
  return false;
}

// 安全か?
bool safe(int n)
{
  while (--n > 0) {
    if (attack(n)) return false;
  }
  return true;
}

// 単純版
void queen0(int n, int m)
{
  if (n == m) {
    if (safe(m)) count++;
  } else {
    for (int i = 0; i < m; i++) {
      if (used[i]) continue;
      used[i] = true;
      board[n] = i;
      queen0(n + 1, m);
      used[i] = false;
    }
  }
}

プログラムは解を表示するのではなく、解の個数をカウントするように修正しています。実行結果は次のようになりました。

            表 : 実行結果 (時間 : 秒)

  個数 :   8   :   9   :  10   :  11   :  12
  -----+-------+-------+-------+----------------
   解  :   92  :  352  :  724  : 2680  : 14200
  時間 : 0.002 : 0.022 : 0.236 : 2.646 : 33.614

実行環境 : Ubunts 22.04 (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
最適化オプション : -O2

クイーンの個数をひとつ増やしただけでも、実行時間はとても遅くなります。実はこのプログラム、とても非効率なことをやっているのです。

●無駄を省く

実行速度が遅い理由は、失敗することがわかっている順列も生成してしまうからです。たとえば、最初 (1, 1) の位置にクイーンを置くと、次のクイーンは (2, 2) の位置に置くことはできませんね。したがって、[1, 2, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を発生させてからチェックする方法では、このような無駄を省くことができません。

そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。

リスト : N Queens Problem (改良版)

void queen1(int n, int m)
{
  if (n == m) {
    count++;
  } else {
    for (int i = 0; i < m; i++) {
      board[n] = i;
      if (used[i] || attack(n)) continue;
      used[i] = true;
      queen1(n + 1, m);
      used[i] = false;
    }
  }
}

関数 queen1 でクイーンを選択するとき、関数 attack を呼び出して選択したクイーンが衝突しないかチェックします。attack は配列 board の末尾から先頭に向かって衝突をチェックしていることに注意してください。あとは特に難しいところはないでしょう。

●実行結果 (1)

実行結果を示します。

            表 : 実行結果 (時間 : 秒)

  個数 :  10   :  11   :  12    :  13   :  14   :  15
  -----+-------+-------+-------+--------+-------+--------
   解  :  724  : 2680  : 14200  : 73712 :365596 : 2279184
   (0) : 0.236 : 2.646 : 33.614 : ----- : ----- : ------
   (1) : 0.003 : 0.015 :  0.085 : 0.469 : 2.840 : 18.404

実行時間は速くなりましたが、クイーンの個数が 15 を超えると実行時間が極端に遅くなります。これは、異なる数字(クイーンの位置)を選ぶために行う配列 used のチェックと、利き筋をチェックする関数 attack に時間がかかるからです。そこで、藤原博文さん8クイーン@勉強会のページ を参考にプログラムを改良してみましょう。

●プログラムの改良

まず、配列 used のチェックですが、配列 board に数字をひとつずつ入れておいて、選んだ数字と未使用の数字を交換していくことで改良することができます。n 列目のクイーンを選ぶ場合、確定済みのクイーンは board の 0 から n - 1 までに格納されていて、残りの n から size - 1 までが未使用のクイーンになります。これで未使用のクイーンを簡単に選ぶことができます。

斜めの利き筋のチェックは、簡単な方法で高速化できます。次の図を見てください。


            図 : 斜めの利き筋のチェック

斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になることを利用してチェックしています。attack は確定済みのクイーンと衝突していないかひとつずつチェックしていますが、斜めの利き筋を配列にセットしておけば、もっと簡単にチェックすることができます。

右斜め上の利き筋を配列 r_used, 左斜め上の利き筋を配列 l_used で表すことにすると、(x, y) にクイーンを置いた場合は次のようにセットします。

r_used[x + y] = l_used[x - y + n - 1] = true;

n は盤面の大きさ (クイーンの個数) です。バックトラックするときはリセットすることをお忘れなく。プログラムは次のようになります。

リスト : N Queens Problem (2)

// 盤面
int board[M];
bool r_used[M * 2 - 1];
bool l_used[M * 2 - 1];
int count;

//
void queen2(int n, int m)
{
  if (n == m)
    count++;
  else {
    for (int i = n; i < m; i++) {
      int x = board[i];
      // チェック
      if (r_used[x + n] || l_used[x - n + m - 1]) continue;
      r_used[x + n] = l_used[x - n + m - 1] = true;
      board[i] = board[n];
      board[n] = x;
      // 再帰する
      queen2(n + 1, m);
      // 元に戻す
      r_used[x + n] = l_used[x - n + m - 1] = false;
      board[n] = board[i];
      board[i] = x;
    }
  }
}

説明をそのままプログラムしただけなので、難しいところはないと思います。説明は割愛しますので、詳細はリストをお読みくださいませ。

●実行結果 (2)

実行結果を示します。

            表 : 実行結果 (時間 : 秒)

  個数 :  12   :  13   :  14   :   15    :   16
  -----+-------+-------+-------+---------+--------
   解  : 14200 : 73712 :365596 : 2279184 :14772512
   (1) : 0.085 : 0.469 : 2.840 : 18.404  : ------
   (2) : 0.036 : 0.199 : 1.195 :  7.456  : 50.453

改良の効果は十分に出ていますね。

●ビット演算による高速化

最後に、ビット演算を使って高速化する方法を紹介します。オリジナルは Jeff Somers さんのプログラムですが、高橋謙一郎さん が再帰を使って書き直したプログラムを Nクイーン問題(解の個数を求める) で発表されています。今回は高橋さんのプログラムを参考にさせていただきました。高橋さんに感謝します。

プログラムのポイントは二つあります。一つはクイーンの選択処理をビット演算で行うこと、もう一つは斜めの利き筋のチェックをビット演算で行うことです。

クイーンの位置をビットオンで表すことします。つまり、i 行目のクイーンは i ビットを 1 にした値になります。この場合、未選択のクイーンは整数値で表すことができます。8 クイーンの場合、まだ一つもクイーンを選択していない状態は 255 になります。残っているクイーンを表す値を n とすると、次の処理でクイーンを順番に取り出していくことができます。

リスト : クイーンの選択処理

int m = n;
while (m > 0) {
  int q = m & (-m);
    ...
  m &= m - 1;
}

while ループの最後で m &= m - 1 とすれば、右端の 1 を 0 にクリアすることができます。そして、ループの中で q = m & (- m) とすれば、右端の 1 を取り出すことができます。n から取り出した q を削除するのも簡単で、排他的論理和 n ^ q を計算するだけです。

次は斜めの利き筋のチェックを説明します。下図を見てください。

    0 1 2 3 4
  *-------------
  | . . . . . .
  | . . . -3. .  0x02
  | . . -2. . .  0x04
  | . -1. . . .  0x08 (1 bit 右シフト)
  | Q . . . . .  0x10 (Q の位置は 4)
  | . +1. . . .  0x20 (1 bit 左シフト)  
  | . . +2. . .  0x40
  | . . . +3. .  0x80
  *-------------


      図 : 斜めの利き筋のチェック

上図の場合、1 列目の右斜め上の利き筋は 3 番目 (0x08)、2 列目の右斜め上の利き筋は 2 番目 (0x04) になります。この値は 0 列目のクイーンの位置 0x10 を 1 ビットずつ右シフトすれば求めることができます。また、左斜め上の利き筋の場合、1 列目では 5 番目 (0x20) で 2 列目では 6 番目 (0x40) になるので、今度は 1 ビットずつ左シフトすれば求めることができます。

つまり、右斜め上の利き筋を right、左斜め上の利き筋を left で表すことにすると、right と left にクイーンの位置をセットしたら、隣の列を調べるときに right と left を 1 ビットシフトするだけで、斜めの利き筋を求めることができるわけです。

プログラムは次のようになります。

リスト : N Queens Problem (3)

void queen3(int n, int right, int left)
{
  if (n == 0)
    count++;
  else {
    for (int m = n; m > 0; m &= m - 1) {
      int q = m & (-m);
      if ((q & (right | left)) == 0)
        queen3(n ^ q, (right | q) << 1, (left | q) >> 1);
    }
  }
}

関数 queen3 の引数 n が未選択のクイーン、引数 right が右斜め上の利き筋、left が左斜め上の利き筋を表します。(rigth | left) のビットオンの位置が斜めの利き筋にあたります。そして、n から斜めの利き筋にあたらないクイーンを選びます。

queen3 を再帰呼び出しするときは、right と left にクイーンの位置をセットして、それを 1 ビットシフトします。right と left は局所変数なので、元の値に戻す処理は必要ありません。あとは、とくに難しいところはないでしょう。詳細はプログラムリストをお読みください。

●実行結果 (3)

実行結果を示します。

            表 : 実行結果 (時間 : 秒)

  個数 :  12   :  13   :  14   :   15    :   16
  -----+-------+-------+-------+---------+--------
   解  : 14200 : 73712 :365596 : 2279184 :14772512
   (1) : 0.085 : 0.469 : 2.840 : 18.404  : ------
   (2) : 0.036 : 0.199 : 1.195 :  7.456  : 50.453
   (3) : 0.017 : 0.098 : 0.577 :  3.551  : 23.776

ビット演算の効果はきわめて大きいですね。ここまで速くなるとは M.Hiroi も大変驚きました。


●プログラムリスト

//
// nqueen.cpp : N Queens Problem
//
//              Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <chrono>
using namespace std;

const int M = 20;

// 盤面
int board[M];
bool used[M];
bool r_used[M * 2 - 1];
bool l_used[M * 2 - 1];
int count;

// 衝突の検出
bool attack(int i)
{
  int n = 1;
  int x = board[i--];
  for (; i >= 0; i--, n++) {
    int y = board[i];
    if (x == y + n || x == y - n) return true;
  }
  return false;
}

// 安全か?
bool safe(int n)
{
  while (--n > 0) {
    if (attack(n)) return false;
  }
  return true;
}

// 単純版
void queen0(int n, int m)
{
  if (n == m) {
    if (safe(m)) count++;
  } else {
    for (int i = 0; i < m; i++) {
      if (used[i]) continue;
      used[i] = true;
      board[n] = i;
      queen0(n + 1, m);
      used[i] = false;
    }
  }
}

void queen1(int n, int m)
{
  if (n == m) {
    count++;
  } else {
    for (int i = 0; i < m; i++) {
      board[n] = i;
      if (used[i] || attack(n)) continue;
      used[i] = true;
      queen1(n + 1, m);
      used[i] = false;
    }
  }
}

void queen2(int n, int m)
{
  if (n == m)
    count++;
  else {
    for (int i = n; i < m; i++) {
      int x = board[i];
      // チェック
      if (r_used[x + n] || l_used[x - n + m - 1]) continue;
      r_used[x + n] = l_used[x - n + m - 1] = true;
      board[i] = board[n];
      board[n] = x;
      // 再帰する
      queen2(n + 1, m);
      // 元に戻す
      r_used[x + n] = l_used[x - n + m - 1] = false;
      board[n] = board[i];
      board[i] = x;
    }
  }
}

void queen3(int n, int right, int left)
{
  if (n == 0)
    count++;
  else {
    for (int m = n; m > 0; m &= m - 1) {
      int q = m & (-m);
      if ((q & (right | left)) == 0)
        queen3(n ^ q, (right | q) << 1, (left | q) >> 1);
    }
  }
}

int main()
{
  for (int n = 10; n <= 16; n++) {
    // queen2 は初期化が必要
    // for (int i = 0; i < n; i++) board[i] = i;
    count = 0;
    auto s = chrono::system_clock::now();
    // queen2(0, n);
    queen3((1 << n) - 1, 0, 0);
    auto e = chrono::system_clock::now();
    double d = chrono::duration_cast<chrono::milliseconds>(e - s).count();
    cout << n << " : " << count << " : " << d / 1000 << endl;
  }
}

初版 2015 年 11 月 8 日
改訂 2023 年 4 月 15 日

Copyright (C) 2015-2023 Makoto Hiroi
All rights reserved.

[ PrevPage | C++ | NextPage ]