この記事はスマートキャンプ株式会社のアドベントカレンダー 2025 の16日目の記事です！
はじめに
こんにちは、りゅうです！
先日、会社の先輩方と参加した「逆リファクタリングバトル」で、ビット演算を使った剰余（余り）計算の実装に挑戦しました！イベント当日は時間内に完成しなかったのですが、その後完成させることができたので、今回はその内容を紹介します。
Rubyの%演算子が抽象化している計算処理を、あえてコンピュータアーキテクチャレベルの算術演算で実装してみました。正直、実用性はゼロですが、コンピュータの仕組みを理解する良い勉強になりました！
参考にした本：
パターソン＆ヘネシー『コンピュータの構成と設計』第5版 上巻
→ コンピュータアーキテクチャの世界で最も有名な教科書です
逆リファクタリングバトルについての記事はこちら！
Rubyでbitを扱うには？
まず、Rubyでビット演算を扱う基本的な方法を紹介します。
基本的なビット演算子
Rubyには以下のビット演算子があります：
# AND演算（&）
5 & 3 # => 1
# 0101 & 0011 = 0001
# OR演算（|）
5 | 3 # => 7
# 0101 | 0011 = 0111
# XOR演算（^）
5 ^ 3 # => 6
# 0101 ^ 0011 = 0110
# NOT演算（~）
~5 # => -6
# ビット反転
# 左シフト（<<）
5 << 1 # => 10
# 0101 << 1 = 1010
# 右シフト（>>）
5 >> 1 # => 2
# 0101 >> 1 = 0010
ビット表現の確認方法
Rubyで数値を2進数表現で確認するには、to_s(2)メソッドを使います：
10.to_s(2) # => "1010"
15.to_s(2) # => "1111"
ビットの取得と設定
特定のビットを取得したり設定したりする方法：
# n番目のビットを取得（0始まり）
def get_bit(num, n)
(num >> n) & 1
end
# n番目のビットを1に設定
def set_bit(num, n)
num | (1 << n)
end
# n番目のビットを0にクリア
def clear_bit(num, n)
num & ~(1 << n)
end
# 使用例
num = 5 # 0101
get_bit(num, 2) # => 1
set_bit(num, 1) # => 7 (0111)
clear_bit(num, 2) # => 1 (0001)
これらの基本操作を組み合わせて、除算アルゴリズムを実装していきます！
そもそもコンピュータはどうやって除算を行うのか？
プログラミング言語で10 / 3と書けば簡単に除算ができますが、コンピュータは実際にどうやって計算しているのでしょうか？
除算の基本原理
コンピュータの除算は、基本的に引き算とシフト演算の繰り返しで実現されます。小学校で習った筆算の方法に似ています！
3 ← 商（quotient）
----
3 | 10 ← 被除数（dividend）/ 除数（divisor）
9 ← 3 × 3
---
1 ← 余り（remainder）
ビット演算による除算アルゴリズム（パタヘネ方式）
パターソン＆ヘネシーの教科書で紹介されている、コンピュータアーキテクチャレベルのアルゴリズムは以下の手順です：
-
初期化
- 被除数を64bitの下位32bitに配置
- 除数を64bitの上位32bitに配置（左シフト32bit）
- 商を0に設定
-
繰り返し処理（33回のループ）
- 2の補数を使った引き算で被除数から除数を引く
- 結果の符号ビット（第63ビット）をチェック：
- 0（非負）なら：引けた → 商のビットを1にする、結果を保持
- 1（負）なら：引けない → 商のビットを0にする、元に戻す
- 除数を右に1ビットシフト
-
終了
- 被除数の下位32bitが余り
- 商も計算できる（今回は余りのみ使用）
重要な技法：2の補数
コンピュータは引き算を、2の補数を使った足し算で実現します：
x - y = x + (-y) = x + (~y + 1)
例：5 - 3 を計算
5 の2進数: 0101
3 の2進数: 0011
~3 (NOT): 1100
~3 + 1: 1101 (これが-3の2の補数表現)
0101 + 1101 = 10010
↑ 5bit目は桁あふれで無視
結果: 0010 = 2
この方法なら、引き算専用の回路が不要で、加算器だけで実現できます！
具体例：10 % 3
被除数: 10 (00001010)
除数: 3 (00000011)
初期配置（64bit表現）:
bit_x: 0...0001010 (下位32bitに10)
bit_y: 0...0011|0000...0000 (上位32bitに3)
↑ 32bit目
ステップ1: bit_y = 0011_00000000...
引き算試行 → 負 → 引けない
ステップ2: bit_y = 0001_10000000...
引き算試行 → 負 → 引けない
...（省略）
ステップ30: bit_y = 0...00000011
引き算試行 → 正 → 引けた！
10 - 3 = 7
ステップ31: bit_y = 0...00000001
引き算試行 → 正 → 引けた！
7 - 3 = 4
ステップ32: bit_y = 0...00000001
引き算試行 → 正 → 引けた！
4 - 3 = 1
ステップ33: bit_y = 0...00000000
引き算試行 → 正 → 引けた！
1 - 0 = 1
結果: 余り = 1
除数を右シフトしながら33回試行することで、剰余が求まります！
実際に仕上げたコード
それでは、実際に実装したRubyコードを紹介します。
完成版のコード
# 符号なし64bitマスク
MASK64 = 0xFFFFFFFFFFFFFFFF
MASK32 = 0xFFFFFFFF
def bit_warizan(x, y)
# 符号なし64bitとして扱う
# bit_x: 被除数（下位32bitに配置）
# bit_y: 除数（上位32bitに配置）
bit_x = x & MASK64
bit_y = ((y & MASK32) << 32) & MASK64
bit_result = 0 & MASK32
for i in 0..32
# 2の補数を使った引き算（bit_x - bit_y）
bit_x = bit_x + ((~bit_y + 1)) & MASK64
if (bit_x >> 63) == 0 # 符号なし64bitで最上位ビットが0なら非負
bit_result = (bit_result << 1) + 1
else
# 引けなかった場合は戻す
bit_x = (bit_x + bit_y) & MASK64
bit_result = (bit_result << 1)
end
# 除数を右シフト
bit_y = (bit_y >> 1) & MASK64
end
# 余りを返す（下位32bitが余り）
bit_x & MASK32
end
# 使用例
puts "10 % 3 = #{bit_warizan(10, 3)}" # => 1
puts "20 % 4 = #{bit_warizan(20, 4)}" # => 0
puts "15 % 7 = #{bit_warizan(15, 7)}" # => 1
コードの解説
このコードは、剰余（余り）のみを返す実装です。パターソン＆ヘネシーの教科書に基づいた、コンピュータアーキテクチャレベルの除算アルゴリズムを忠実に再現しています。
1. ビットマスクの定義
MASK64 = 0xFFFFFFFFFFFFFFFF # 64bit全体
MASK32 = 0xFFFFFFFF # 32bit全体
符号なし整数として扱うためのマスクです。Rubyは任意精度整数なので、明示的にビット幅を制限します。
2. 初期配置
bit_x = x & MASK64 # 被除数を下位32bitに
bit_y = ((y & MASK32) << 32) & MASK64 # 除数を上位32bitに
bit_result = 0 & MASK32 # 商（今回は使わない）
除数を上位32bitに配置することで、右シフトしながら処理できるようにします。これが筆算と同じ要領です！
3. 2の補数を使った引き算
bit_x = bit_x + ((~bit_y + 1)) & MASK64
ここがポイント！コンピュータは引き算を「2の補数を使った足し算」で実現します：
-
~bit_y：ビット反転（NOT演算） -
~bit_y + 1：2の補数（負の数を表現） -
bit_x + (~bit_y + 1)：実質的にbit_x - bit_y
4. 結果の判定
if (bit_x >> 63) == 0 # 最上位ビットが0なら非負
bit_result = (bit_result << 1) + 1
else
bit_x = (bit_x + bit_y) & MASK64 # 引けなかったので戻す
bit_result = (bit_result << 1)
end
64bitの最上位ビット（第63ビット）が符号ビットです。0なら非負（引けた）、1なら負（引けなかった）と判定します。
5. 除数を右シフト
bit_y = (bit_y >> 1) & MASK64
33回のループで、除数を右シフトしながら処理していきます。これが筆算で桁を下げていく動作に相当します。
6. 余りを返す
bit_x & MASK32
最終的にbit_xの下位32bitが余りになります。
果たして実行速度は速くなるのか？
さて、気になるのは「ビット演算で実装したら、Rubyの標準の%演算子より速いのか？」という点です。
結論から言うと、全く速くなりません。むしろ圧倒的に遅いです。
詳細なベンチマーク測定
実際に50回実行して平均を取ってみました：
実装したベンチマークコードはこちら：
実行結果：
================================================================================
ベンチマーク結果（50回の平均）
================================================================================
実行日時: 2025-11-25 14:51:03
テストケース数: 100000
実行回数: 50回
正確性: 100000/100000 (100.0%)
bit_warizan:
平均: 2.486004秒 (2486.00ms)
最小: 1.676137秒 (1676.14ms)
最大: 5.266926秒 (5266.93ms)
x % y:
平均: 0.011589秒 (11.59ms)
最小: 0.000000秒 (0.00ms)
最大: 0.091007秒 (91.01ms)
速度比（平均）: 214.52倍 (通常演算子の方が214.52倍速い)
================================================================================
なんと約215倍遅い！！
実装したコードはこちら：
なぜこんなに遅いのか？
いくつか理由があります：
-
Rubyはインタープリタ言語
- ビット演算のループ処理がRubyレベルで実行される
- 標準の
%演算子はC言語レベルで最適化されている - 毎回のループでインタープリタのオーバーヘッドが発生
-
CPUの除算命令
- 現代のCPUには高速な除算命令（DIV命令）がある
- ハードウェアレベルで1クロックサイクルで実行
- ビット演算の実装は何十回もループする
-
変数代入とビット操作のコスト
- 変数への代入処理
- ビット列への変換処理
- メソッド呼び出しのオーバーヘッド
- Rubyの動的型チェック
-
デジタル回路とプログラムの違い
- デジタル回路では並列処理が可能
- プログラムは逐次処理
- 抽象化のレイヤーが異なる
それでもやる意味はあるのか？
実用性はゼロですが、以下のような学習効果がありました：
-
コンピュータの仕組みの理解
- CPUがどうやって計算しているかを体感できた
- 抽象化の有り難みを実感
-
ビット演算の練習
- シフト演算やマスク演算の理解が深まった
- 低レイヤーのプログラミング感覚が身についた
-
アルゴリズムの理解
- 筆算のアルゴリズムをコードに落とし込む練習
- 手続き的思考の訓練
-
抽象化レイヤーの違いを実感
- デジタル回路上では確かに高速
- プログラム上では提供されている演算子が最強
- 適切なレイヤーで適切な方法を使うことの重要性
実用性より、知的好奇心と学習体験が価値だったと思います！
結論：プログラムでは標準演算子を使おう
今回の実験で分かったこと：
デジタル回路レベルでは速い → ハードウェアの並列処理が活きる
プログラムレベルでは遅い → インタープリタやループのオーバーヘッドが大きい
つまり、プログラミングでは素直に言語が提供している演算子を使うのが正解です！（当たり前すぎますねw）
低レイヤーの最適化をプログラムで再現しても、抽象化のレイヤーが違うので意味がありません。むしろ、言語やライブラリが提供する高レベルな機能を使う方が、可読性も保守性もパフォーマンスも良くなります。
これが「適切な抽象化レベルで開発する」ということですね！？
最後に
今回は、Rubyでビット演算を使った除算を実装してみました。
逆リファクタリングバトルで時間内には完成しなかったコードを、後日完成させることができて達成感がありました！さらにベンチマークを50回も実行して、215倍遅いという衝撃の結果も得られました（笑）
プログラミング言語が抽象化してくれている部分をあえて低レイヤーで実装することで、普段意識しないコンピュータの仕組みを学ぶ良い機会になりました。
今回の学び：
- ビット演算の基本操作
- 除算アルゴリズムの仕組み
- 抽象化のありがたみ
- パフォーマンスは実測しないと分からない
- デジタル回路とプログラムは別物
- 適切な抽象化レベルで開発することの重要性
実用性はゼロですが、こういう「無駄」な挑戦も、たまには面白いですよね！むしろ、こういう実験をすることで、普段使っている機能のありがたみを実感できます。
プログラミングの本質を理解するためには、こうした低レイヤーの知識も大切だと感じました。皆さんも興味があれば、ぜひ試してみてください！
実装したコードは以下のリポジトリで公開しています：
参考
Discussion