この記事は OUCC Advent Calendar 2024 の 14 日目の記事です。昨日は GPT/UEFI/Secure Boot 環境で無料ツールだけで Windows をクローンする方法を説明しました。本日は、AtCoder Beginners Selection の Shift only を x86 の bsf 命令で解く方法を説明します。

Shift only

まず、AtCoder Beginners Selection は

「AtCoderに登録したけど何をしていいか分からない・・・！」という人に向けて作られた、初心者向け問題集です。

と説明されている通り、極めて簡単な問題から少し捻った問題までを網羅した初心者向けの精選過去問集で、常設コンテストという形でいつでも遊べる使えるように用意されているものです。Shift only はそのうち 4 問目にあたり、AtCoder Beginner Contest 081 の問題 B を抽出してきたものです。直接サイトを見に行くのが早いと思いますが、一応問題文は以下の通りです。

黒板に N 個の正の整数 A₁,…, A_N が書かれています．

すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

• 黒板に書かれている整数すべてを，2 で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

制約は 1 ≤ N ≤ 200 かつ 1 ≤ A_i ≤ 10⁹ と、初心者向け問題らしく特に何も考慮不要な親切なものとなっています。結局のところ問題の趣旨は「与えられた数のうち、2 で割れる回数が最も少ないものは何回割れるのかを答える」という、ただそれだけです。制約も大したことないので素朴に for/while 文でひたすら 2 で割っていけば良く、公式解説もそうなっています（以下にコードを転載）。

#include <iostream>
using namespace std;

int N;
int A[210];			// 最大 200 個なので余裕を持って 210 に --- 200 以上ならなんでもよいです

int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> A[i];

	int res = 0;

	// 操作が行える限り操作を繰り返す
	while (true) {
		bool exist_odd = false;  // A[i] がすべて偶数かどうかを判定するフラグ
		for (int i = 0; i < N; ++i) {
			if (A[i] % 2 != 0) exist_odd = true;  // 奇数があったらフラグを立てる
		}

		if (exist_odd) break;  // 奇数があったら break

		// 操作を行えるなら操作を実際に行う
		for (int i = 0; i < N; ++i) {
			A[i] /= 2;
		}
		++res;  // 操作回数をインクリメント
	}

	cout << res << endl;
}

しかし、「2 で割る」「Shift only」… 何か、ありそうな気がしませんか？

コンピュータの数値表現

現在のコンピュータでは、全てのデータを 0 と 1 の 2 通りの状態をもつ「ビット」の組み合わせにより表現しています。プログラム上で数値を扱うときには特に何も気にせず 10 進数で書きますが、内部では処理系や入出力関数が全て 2 進数のビット列に変換しています。

ここで、「2 で割る」というのは 2 進数において極めて単純な計算になります。簡単な話で、10 進数において「4536274000000 は 10 で何回割れる？」と聞かれれば、誰でも「6 回！」と即答するでしょう。これは、単に末尾の 0 の個数を数えるだけで分かるからです。なぜそれで分かるのかと言われれば、「10 で割れば一番右の 0 が 1 つ消える」ということを知っているからでしょう。これは、2 進数でも同じことです。「1101011000000₍₂₎ は 10₍₂₎ で何回割れる？」の答えは、10 進数のときと同じように 6 回です。そして、10₍₂₎ = 2 です。つまり、n 進数表現において「10_(n)」となる値、すなわち n で割る操作は必ず末端の 0 を 1 つ消す操作になり、n で割れる回数は末尾の 0 の数に一致します（逆に 10 を掛ける操作は必ず末尾に 0 を追加する操作になります）。

ここまでこれば、問題文の「Shift only」の意味が理解できたのではないでしょうか。つまり、この問題は数値のビット表現を左右にずらすシフト演算でも解くことができます（尤も、コンパイラによる最適化で普通に割り算で書いても内部的にはそうなっているはずですが）。しかし、それでも愚直な実装に変わりはありません。数値のビット列の末尾の 0 の個数を数えて最小のものを出力するだけ。こんなにコンピュータにとって都合のいい問題を、もっとサクっと解く方法はないものでしょうか。

popcnt 命令との出会い

そんなある日、こんなニュースを見つけました。

「Windows 11 バージョン 24H2」はPOPCNT命令を備えたCPUが必須？　化石レベルでは起動せず／もっとも、これで困る人はごくわずか【やじうまの杜】

　「やじうまの杜」では、ニュース・レビューにこだわらない幅広い話題をお伝えします。

https://forest.watch.impress.co.jp/docs/serial/yajiuma/1568276.html

どうやら、Windows 11 24H2 以降では popcnt 命令とやらが必須化されるそうです。尤も、これは Windows 11 の最低要件を 10 年近く下回る極めて古い CPU で諸々のチェックをバイパスして無理矢理 Windows 11 をブチ込んでいた人だけが影響を受けるもので、大半の人にとってはどうでもいいニュースです。そもそも、そんな古い CPU で現在の激重クソ Windows 11 を動かすのは性能的にかなり無理があります。

しかし、何となく興味があったので、この popcnt 命令とは何なのかを調べてみました。すると、Population Count の略で、「数値の 2 進数表現において 1 を数えるための命令」だと判明しました（後述の公式リファレンスでは 1629 ページ目）。これを見て確信しました。ただでさえ意味不明な謎命令が大量に実装されていることで有名な x86 において「1 を数える命令があるのに、末尾の 0 を数える命令がないわけがない」と（注：AtCoder のジャッジシステムは 64-bit モードの x86¹ で動いている）。

bsf 命令

Intel の公式リファレンス²の 717 ページ目に bsf 命令の説明があります（ここの非公式サイトならデカい PDF を扱わずに済みます）。Description を適当に訳すと以下の通りです。

演算元オペランド（第 2 オペランド）から最小の立っているビット（1 のビット）を探す。最小の 1 のビットが見つかれば、そのインデックスが演算先オペランド（第 1 オペランド）に保存される。演算元オペランドはレジスタかメモリ位置であり、演算先オペランドはレジスタである。インデックスは演算元オペランドの 0 番目のビットからの符号なしオフセットである。演算元オペランドが 0 なら演算先オペランドの内容は変更されない。

ドンピシャです。これほどまでに完璧なことがあっていいものでしょうか。入力が 0 のときの動作がイマイチですが、本問では入力は 1 以上であることが保証されているので考慮不要です（bsf 命令を使って欲しいとしか思えない完璧な制約条件）。

そんなわけで、早速使っていきましょう。C/C++ ではインラインアセンブラが使えるので、機械語命令の直書きもお手のものです。以下は C 言語のつもりですが C++ でもコンパイルできます。GCC でも Clang でも OK です。当然ながら Arm な環境では動かないので、AtCoder のジャッジシステムやコードテストで試してください。

#include <stdio.h>

int main(void) {
  int N, ans = 100;
  scanf("%d", &N);
  
  for (int i = 0; i < N; ++i) {
    int num, ctz;
    scanf("%d", &num);
    asm("bsf %1, %0" : "=r" (ctz) : "r" (num));
    ans = ans > ctz ? ctz : ans;
  }
  
  printf("%d\n", ans);
  return 0;
}

内容は以下の通りです。コンパイラにより差がありますが GCC/Clang ではこの形です。出力オペランド以降で書いた変数に、その順番でアセンブリテンプレートから %0, %1, %2,… として参照できます。注意点として、GCC/Clang ではデフォルトで AT&T 記法になるので、AtCoder 上でも AT&T 記法になります。だから何かというと、オペランドの記載順が先述の Intel のドキュメントと逆になります。他にも数多の違いがありますが、今回は単純なので差分はこれくらいです。

• "bsf %1, %0": アセンブリテンプレート
  • %1 から最小の立っているビットを探し、そのインデックスを %0 に格納する（%1 の 2 進数表現の末尾の 0 の個数が %0 に入る）
• "=r" (ctz): 出力オペランド
  • 変数 ctz を %0 レジスタにマップする
  • 制約文字 r でコンパイラに適切なレジスタを選ばせて、制約修飾子 = で書き込み専用として設定する
• "r" (num): 入力オペランド
  • 変数 num を %1 レジスタにマップする
  • 制約文字 r でコンパイラに適切なレジスタを選ばせる（制約修飾子がないので読み込み専用）

普通にひたすら割っていったりひたすら右シフトしていったりするよりも、はるかに単純な実装になりました。インラインアセンブラで手動最適化すると普通コードは複雑になるものですが、CPU 命令を使ってコードを簡略化できるのは不思議な感じですね。実際にこれで AC を取れます。CPU 命令なだけあって爆速です。

その他の方法

実は bsf 命令はインラインアセンブラを使わなくても、コンパイラの組み込み関数で呼び出すことができます。以下のコードは共に C/C++ どちらでも、GCC/Clang どちらでも通ることを確認しています。

ビルトイン関数 __builtin_ctz() を使う場合：

#include <stdio.h>

int main(void) {
  int N, ans = 100;
  scanf("%d", &N);
  
  for (int i = 0; i < N; ++i) {
    int num, ctz;
    scanf("%d", &num);
    ctz = __builtin_ctz(num);
    ans = ans > ctz ? ctz : ans;
  }
  
  printf("%d\n", ans);
  return 0;
}

x86intrin.h の __bsfd() を使う場合（d は Double Word で 32-bit 版という意味）：

#include <stdio.h>
#include <x86intrin.h>

int main(void) {
  int N, ans = 100;
  scanf("%d", &N);
  
  for (int i = 0; i < N; ++i) {
    int num, ctz;
    scanf("%d", &num);
    ctz = __bsfd(num);
    ans = ans > ctz ? ctz : ans;
  }
  
  printf("%d\n", ans);
  return 0;
}

0 ms と 1 ms がありますが、何度か提出してみると変わるので測定誤差だと思います。

おわりに

本日は、AtCoder Beginners Selection の Shift only を x86 の bsf 命令で解く方法を説明しました。私は競技プログラミングを引退してもう 4 年半になりますが、それでもいろいろな遊び方があって面白いですね。この記事がアセンブラや CPU 命令への誘いになれば幸いです。