大規模な整数演算やビット操作が必要なPHPアプリケーションでは、GMPライブラリの持つ強力な機能群が頼りになります。その中でも今回は、多くの開発者に見過ごされがちながら非常に有用な「gmp_scan1」関数について、その機能から実践的な活用方法まで徹底解説します。
gmp_scan1関数とは？
gmp_scan1関数は、GMP数値（大きな整数）の二進表現において、指定された位置から始めて「1」であるビットを探し、最初に見つかった「1」のビットの位置（インデックス）を返す関数です。
構文
gmp_scan1(GMP|string|int $num, int $start): int
パラメータ:
$num– 検索対象のGMP数値（GMP オブジェクト、数値、または数値文字列）$start– 検索を開始するビットのインデックス（0から始まる）
戻り値:
$start以上のインデックスで最初に「1」であるビットのインデックス- 該当するビットが存在しない場合は-1を返す
基本的な使い方
gmp_scan1の基本的な使い方を例で見てみましょう：
<?php
// 数値42を二進数で考えると「101010」
$num = gmp_init(42);
// インデックス0（最下位ビット）から検索開始
echo "最初の1ビットの位置: " . gmp_scan1($num, 0) . "\n";
// 出力: 1 （右から2番目のビットが初めての1）
// インデックス2から検索開始
echo "インデックス2以降の最初の1ビット: " . gmp_scan1($num, 2) . "\n";
// 出力: 3 （右から4番目のビットが次の1）
// インデックス6（この数値のすべてのビットを超える）から検索開始
echo "範囲外からの検索: " . gmp_scan1($num, 6) . "\n";
// 出力: -1 （1のビットが見つからない）
// 0の場合（すべてのビットが0）
echo "値が0の場合: " . gmp_scan1(0, 0) . "\n";
// 出力: -1 （1のビットが存在しない）
?>
実用的な応用例
1. 数値の最上位ビット（MSB）を見つける
数値の最上位ビット（Most Significant Bit）を特定することは、様々なアルゴリズムで重要な操作です：
<?php
/**
* 数値の最上位ビット（MSB）のインデックスを見つける
* @param GMP|string|int $number 検査する数値
* @return int 最上位ビットのインデックス、または-1（値が0の場合）
*/
function find_msb($number) {
$num = gmp_init($number);
// 値が0の場合は-1を返す
if (gmp_cmp($num, 0) == 0) {
return -1;
}
// バイナリ表現の長さを取得して効率的に検索
$bin = gmp_strval($num, 2);
$max_bit = strlen($bin) - 1;
// 最上位ビットは常に1なので、その位置を返す
return $max_bit;
}
// 使用例
$values = [0, 1, 5, 42, 127, 128, 1023];
foreach ($values as $val) {
$msb = find_msb($val);
echo "数値 $val の最上位ビット: " . ($msb >= 0 ? $msb : "なし") . "\n";
}
?>
2. 次のセットビット（1のビット）を探す反復処理
ビットマップ内のすべての「1」ビットを効率的に列挙する方法：
<?php
/**
* 数値内のすべての1のビット位置を配列として返す
* @param GMP|string|int $number 検査する数値
* @return array 1のビット位置の配列
*/
function list_all_set_bits($number) {
$num = gmp_init($number);
$positions = [];
$pos = 0;
// 数値が0になるまで繰り返し
while (gmp_cmp($num, 0) > 0) {
// 次の1ビットを見つける
$next_bit = gmp_scan1($num, $pos);
// 見つからなければ終了
if ($next_bit == -1) {
break;
}
// 位置を記録
$positions[] = $next_bit;
// 次の位置から検索を続ける
$pos = $next_bit + 1;
}
return $positions;
}
// 使用例
$val = 42; // 二進数で101010
$set_bits = list_all_set_bits($val);
echo "数値 $val（二進数: " . decbin($val) . "）のセットビット位置: ";
echo implode(", ", $set_bits) . "\n";
// 出力: 1, 3, 5
?>
3. ビットフラグの解析
複数のフラグが詰め込まれたビットフィールドからフラグを解析する実用的な例：
<?php
/**
* ビットフラグから有効なオプションを抽出する
* @param int $flags ビットフラグ
* @param array $options オプション名の配列（インデックスがビット位置と対応）
* @return array 有効なオプション名の配列
*/
function parse_bit_flags($flags, $options) {
$num = gmp_init($flags);
$active_options = [];
$bit_pos = 0;
while (true) {
// 次の有効なフラグを検索
$bit_pos = gmp_scan1($num, $bit_pos);
if ($bit_pos == -1) {
break; // これ以上フラグはない
}
// 該当するオプションがあれば追加
if (isset($options[$bit_pos])) {
$active_options[] = $options[$bit_pos];
}
// 次のビットから検索
$bit_pos++;
}
return $active_options;
}
// 使用例：ファイルパーミッション解析
$permission_flags = 0644; // rw-r--r--
$permission_options = [
0 => 'execute_others',
1 => 'write_others',
2 => 'read_others',
3 => 'execute_group',
4 => 'write_group',
5 => 'read_group',
6 => 'execute_owner',
7 => 'write_owner',
8 => 'read_owner'
];
$active_permissions = parse_bit_flags($permission_flags, $permission_options);
echo "アクティブな権限: " . implode(", ", $active_permissions) . "\n";
// 出力: read_others, read_group, write_owner, read_owner
?>
4. 整数内の1ビットの数をカウント（ポプカウント）
通常のgmp_popcountと同等の機能をgmp_scan1で実装する例：
<?php
/**
* 数値内の1のビット数をカウント（gmp_scan1ベースの実装）
* @param GMP|string|int $number カウント対象の数値
* @return int 1のビット数
*/
function custom_popcount($number) {
$num = gmp_init($number);
$count = 0;
$pos = 0;
while (true) {
$pos = gmp_scan1($num, $pos);
if ($pos == -1) {
break;
}
$count++;
$pos++;
}
return $count;
}
// gmp_popcountとの比較
$test_values = [0, 1, 7, 15, 42, 127, 255, 1023];
foreach ($test_values as $val) {
$custom = custom_popcount($val);
$builtin = gmp_popcount($val);
echo "数値 $val の1ビット数: $custom (gmp_popcount: $builtin)\n";
}
?>
5. 範囲内で指定したビットパターンを持つ値の検索
特定のビットパターンを含む数値を範囲内で効率的に検索する高度な例：
<?php
/**
* 指定範囲内で特定のビットマスクに一致する最初の数値を見つける
* @param int $start 検索範囲の開始値
* @param int $end 検索範囲の終了値
* @param int $mask 探すビットマスク
* @return int|null 見つかった最初の数値、または見つからない場合はnull
*/
function find_first_matching_pattern($start, $end, $mask) {
$g_start = gmp_init($start);
$g_end = gmp_init($end);
$g_mask = gmp_init($mask);
// マスク内の1のビット位置を特定
$one_positions = [];
$pos = 0;
while (true) {
$pos = gmp_scan1($g_mask, $pos);
if ($pos == -1) break;
$one_positions[] = $pos;
$pos++;
}
// 範囲内の各数値をチェック
$current = $g_start;
while (gmp_cmp($current, $g_end) <= 0) {
$matches = true;
// すべての必要なビットが1になっているかチェック
foreach ($one_positions as $bit_pos) {
if (gmp_testbit($current, $bit_pos) == 0) {
$matches = false;
break;
}
}
if ($matches) {
return gmp_strval($current);
}
$current = gmp_add($current, 1);
}
return null;
}
// 使用例: 10〜50の範囲で、ビット1と3が立っている最初の数値を探す
$mask = 10; // 二進数: 1010
$result = find_first_matching_pattern(10, 50, $mask);
echo "マスク " . decbin($mask) . " に一致する最初の数値: " . ($result ?? "なし") . "\n";
// 出力: 10 (二進数: 1010)
?>
gmp_scan0とgmp_scan1の組み合わせ
gmp_scan0とgmp_scan1を組み合わせることで、より高度なビット操作が可能になります：
連続する1または0の最長シーケンスを見つける
<?php
/**
* 数値内の連続するビット（0または1）の最長シーケンスを見つける
* @param GMP|string|int $number 対象の数値
* @param int $bit_type 探すビット値（0または1）
* @return array [開始位置, 長さ]
*/
function find_longest_bit_sequence($number, $bit_type = 1) {
$num = gmp_init($number);
// 検索関数を決定
$scan_func = $bit_type ? 'gmp_scan1' : 'gmp_scan0';
$opposite_func = $bit_type ? 'gmp_scan0' : 'gmp_scan1';
$max_length = 0;
$max_start = -1;
$position = 0;
$bit_length = strlen(gmp_strval($num, 2));
while ($position < $bit_length) {
// 次の目的のビット（0または1）を見つける
$start = $scan_func($num, $position);
if ($start == -1) break;
// 次の反対のビットを見つける
$end = $opposite_func($num, $start);
if ($end == -1) $end = $bit_length;
// 長さを計算
$length = $end - $start;
// より長いシーケンスがあれば記録を更新
if ($length > $max_length) {
$max_length = $length;
$max_start = $start;
}
// 次の検索位置を設定
$position = $end + 1;
}
return [$max_start, $max_length];
}
// 使用例
$test = 4623; // 二進数: 1001000001111
echo "数値: " . $test . " (二進数: " . decbin($test) . ")\n";
list($start, $length) = find_longest_bit_sequence($test, 1);
echo "最長の連続1シーケンス: 位置 $start から $length ビット\n";
list($start, $length) = find_longest_bit_sequence($test, 0);
echo "最長の連続0シーケンス: 位置 $start から $length ビット\n";
?>
高度な応用：ビットごとの操作を最適化する
スパースビットの効率的な処理
巨大な数値で1のビットが少ない（スパースな）場合、gmp_scan1を使用して効率的に処理できます：
<?php
/**
* 2つのスパースなビットパターンのAND演算を最適化して実行
* （通常のgmp_andより効率的な場合がある）
*/
function sparse_bitwise_and($a, $b) {
$gmp_a = gmp_init($a);
$gmp_b = gmp_init($b);
$result = gmp_init(0);
$pos = 0;
// 最初の数値のセットビットだけを調べる
while (true) {
$pos = gmp_scan1($gmp_a, $pos);
if ($pos == -1) break;
// もう一方の数値でも同じビットが1ならば結果にも1を設定
if (gmp_testbit($gmp_b, $pos)) {
$result = gmp_setbit($result, $pos);
}
$pos++;
}
return $result;
}
// 使用例
$a = "10000000000000000001"; // 10進数で非常に大きな値
$b = "10000000000000000101";
$result = sparse_bitwise_and($a, $b);
echo "スパースAND結果: " . gmp_strval($result) . "\n";
echo "通常のAND結果: " . gmp_strval(gmp_and($a, $b)) . "\n";
?>
ビットインデックスのイテレータ
特定のビット値を持つすべての位置を効率的に列挙するイテレータパターン：
<?php
/**
* 指定されたビット値（0または1）を持つすべての位置を列挙するイテレータクラス
*/
class BitPositionIterator implements Iterator {
private $number;
private $bit_type; // 0 or 1
private $current_pos;
private $key;
private $valid;
private $max_bits;
public function __construct($number, $bit_type = 1) {
$this->number = gmp_init($number);
$this->bit_type = $bit_type ? 1 : 0;
$this->max_bits = strlen(gmp_strval($this->number, 2));
$this->rewind();
}
public function rewind() {
$this->current_pos = -1;
$this->key = -1;
$this->next();
}
public function current() {
return $this->current_pos;
}
public function key() {
return $this->key;
}
public function next() {
$scan_func = $this->bit_type ? 'gmp_scan1' : 'gmp_scan0';
$this->current_pos = $scan_func($this->number, $this->current_pos + 1);
if ($this->current_pos == -1 || $this->current_pos >= $this->max_bits) {
$this->valid = false;
} else {
$this->valid = true;
$this->key++;
}
}
public function valid() {
return $this->valid;
}
}
// 使用例
$num = 42; // 二進数: 101010
echo "数値 $num の1ビット位置:\n";
$iterator = new BitPositionIterator($num, 1);
foreach ($iterator as $index => $position) {
echo "[$index] 位置: $position\n";
}
echo "\n数値 $num の0ビット位置:\n";
$iterator = new BitPositionIterator($num, 0);
foreach ($iterator as $index => $position) {
echo "[$index] 位置: $position\n";
}
?>
パフォーマンスの考慮点と最適化
gmp_scan1を効率的に使用するためのヒント：
- ビット数が既知の場合は範囲を限定: 数値のビット長が分かっている場合、不要な範囲の検索を避ける
- 繰り返し使用する値はキャッシュ: 同じ数値に対して複数回の操作を行う場合、GMP値を再利用する
- 大きな数値の場合はバイナリ表現をキャッシュ:
gmp_strval($num, 2)の呼び出しは、大きな数値の場合にコストが高い gmp_testbitとの組み合わせ: 特定位置のビットをテストするには、gmp_scan1の前にgmp_testbitを使用して確認する
<?php
/**
* 最適化されたビットカウント実装
*/
function optimized_bit_counting($number) {
$num = gmp_init($number);
// まず二進表現の長さを調べる（最適化のため）
$bin = gmp_strval($num, 2);
$max_bits = strlen($bin);
// 値が0なら即座に0を返す
if ($max_bits == 1 && $bin[0] == '0') {
return 0;
}
$count = 0;
$pos = 0;
// ビット範囲を限定して検索
while ($pos < $max_bits) {
$pos = gmp_scan1($num, $pos);
if ($pos == -1) break;
$count++;
$pos++;
}
return $count;
}
?>
実際のユースケース
1. ビット操作に基づくデータ圧縮
特定のパターンを圧縮するアルゴリズムでの使用例：
<?php
/**
* ランレングス圧縮のビットベース実装
* （同じビット値の連続を圧縮）
*/
function bit_run_length_encode($number) {
$num = gmp_init($number);
$encoded = [];
$bin = gmp_strval($num, 2);
$max_bits = strlen($bin);
$pos = 0;
$current_bit = null;
while ($pos < $max_bits) {
// 次の0ビットと1ビットの位置を調査
$next_zero = gmp_scan0($num, $pos);
$next_one = gmp_scan1($num, $pos);
// 範囲外のビットは最大値に設定
if ($next_zero == -1) $next_zero = $max_bits;
if ($next_one == -1) $next_one = $max_bits;
// 近い方のビットを選択
if ($next_zero <= $next_one) {
$next_pos = $next_zero;
$bit_value = 0;
} else {
$next_pos = $next_one;
$bit_value = 1;
}
// 範囲外なら終了
if ($next_pos >= $max_bits) break;
// 現在のビット値と長さを取得
if ($current_bit !== $bit_value) {
$current_bit = $bit_value;
$run_start = $next_pos;
}
// 次の異なるビットを探す
$search_func = $bit_value ? 'gmp_scan0' : 'gmp_scan1';
$run_end = $search_func($num, $next_pos);
if ($run_end == -1) $run_end = $max_bits;
// ランの長さを記録
$run_length = $run_end - $run_start;
$encoded[] = [$bit_value, $run_length];
// 位置を更新
$pos = $run_end;
}
return $encoded;
}
// 使用例
$value = 2730; // 二進数: 101010101010
$encoded = bit_run_length_encode($value);
echo "数値: $value (二進数: " . decbin($value) . ")\n";
echo "ランレングス圧縮結果:\n";
foreach ($encoded as $i => $run) {
list($bit, $length) = $run;
echo "ラン #$i: ビット値=$bit, 長さ=$length\n";
}
?>
2. ビット操作に基づくBloomフィルタの実装
スペース効率の良いデータ構造の実装例：
<?php
/**
* シンプルなBloomフィルタの実装
* （ビットベースの確率的データ構造）
*/
class SimpleBloomFilter {
private $bitmap;
private $size;
private $hash_functions;
public function __construct($size = 1024, $hash_functions = 3) {
$this->bitmap = gmp_init(0);
$this->size = $size;
$this->hash_functions = $hash_functions;
}
/**
* 要素を追加
*/
public function add($item) {
$item_str = (string)$item;
// 複数のハッシュ関数でビットを設定
for ($i = 0; $i < $this->hash_functions; $i++) {
$hash = crc32($item_str . $i) % $this->size;
$this->bitmap = gmp_setbit($this->bitmap, $hash);
}
}
/**
* 要素がフィルタ内に存在する可能性をチェック
*/
public function may_contain($item) {
$item_str = (string)$item;
// すべてのハッシュ位置でビットが設定されているか確認
for ($i = 0; $i < $this->hash_functions; $i++) {
$hash = crc32($item_str . $i) % $this->size;
if (!gmp_testbit($this->bitmap, $hash)) {
return false; // 確実に含まれていない
}
}
// 含まれている可能性がある（偽陽性の可能性あり）
return true;
}
/**
* フィルタ内のセットされたビット数を取得
*/
public function count_bits() {
$count = 0;
$pos = 0;
while (true) {
$pos = gmp_scan1($this->bitmap, $pos);
if ($pos == -1 || $pos >= $this->size) break;
$count++;
$pos++;
}
return $count;
}
}
// 使用例
$bloom = new SimpleBloomFilter(1024, 3);
$bloom->add("apple");
$bloom->add("banana");
$bloom->add("orange");
$tests = ["apple", "banana", "grape", "kiwi", "orange"];
foreach ($tests as $item) {
$result = $bloom->may_contain($item) ? "含まれている可能性あり" : "確実に含まれていない";
echo "項目 '$item': $result\n";
}
echo "設定されたビット数: " . $bloom->count_bits() . "\n";
?>
まとめ
gmp_scan1関数は、GMPライブラリが提供するビット操作機能の中でも特に便利なツールです。この関数を使いこなすことで：
- 効率的なビット検索：大きな整数値内の特定のビットパターンを効率的に見つけることができます。
- 高度なデータ構造：ビットマップ、ブルームフィルタ、圧縮データ構造など、ビットレベルの操作が必要なデータ構造を実装できます。
- 最適化されたアルゴリズム：従来の方法よりも効率的に、ビットごとの操作に基づくアルゴリズムを実装できます。
- リソース効率：巨大な数値を扱う場合でも、メモリ効率の良い方法でビット操作を行えます。
PHPでの大規模な数値計算や低レベルのビット操作が必要なシナリオでは、gmp_scan1と他のGMP関数を組み合わせることで、高性能で信頼性の高いソリューションを構築することができます。GMPライブラリの真の力を活用して、より効率的なコードを書きましょう。
