Rubyでのビット操作に便利なメソッド

Rubyでバリバリビット操作をしているのですが、ふと調べてみると、標準メソッドのほうがすっきり高速に書けることがちょくちょくありました。

Rubyの整数とビット単位の処理

Rubyの整数にはシフトやビット単位のAND/OR/NOT/XORというような演算も整っていて、ビット列として使うことももちろんできます。そして、大きな数は自動でBignumに突入してくれるので、桁あふれでマイナスになってしまう心配もありません。

（なお、これ以降、「○ビット目」という場合、最下位ビットを「0ビット目」として数えます）

ビット位置のチェック

「整数numのposビット目が立っているかどうか」をチェックしようとした時に、ある程度心得があれば、(num & (1 << pos)) != 0なんて書いてしまうかと思いますが、実はIntegerの側で、ビット位置をチェックするための[]メソッドが用意してあって（ビットが立っていれば1、なければ0を返します）、num[pos] != 0と書けます。そして、この2つの速度を比較してみたところ、1 << posやANDした結果を生成しなくていいということもあって、num[pos] != 0のほうが数倍高速でした。

なお、Integerはimmutableなので、[]=メソッドはありません。

何ビット目かの取得

たとえば「200ビット目だけが1になった数」なら1 << 200で簡単に作れますが、その逆変換、つまり「4096で立っているのは何ビット目か」数えることが必要となりました。

いちばんシンプルな方法としては、事前にHashでテーブルを用意しておくという方法を思いつきました。単純とはいえ、テーブルを無限に用意するわけにもいかないので、使える値に限度が出ます。

次に、この「最上位だけ1が立った数」から1を引いてみると、「もともと立っていたビット以下がすべて1」の数となります。あとは少し前に作ったpopcountルーチンで数えれば、ビット位置を計算できます。

…なんてやっていたのですが、Ruby 2.1以降では、Integer標準で、「全体を表すビット数」を返すbit_lengthメソッドが登場していました。1ビットだけ立ったものの場合、bit_lengthから1を引くだけで、欲しい値となります。

これまたベンチマークを取ってみると、bit_length版が最速でした。桁数が増えれば速度の差は100倍以上となっていました。

ベンチマークのコード

require 'benchmark'
require 'bit_counter'

# ビット位置判定のベンチマーク

val = (1 << 2000) -1
pos = 1000
times = 1_000_000
Benchmark.bm 10 do |r|
  r.report 'shift' do
    times.times do
      (val & (1 << pos)) != 0
    end
  end
  r.report '[]' do
    times.times do
      val[pos] != 0
    end
  end
end


# table
table = {}
65536.times { |i| table [1 << i] = i }

# ビット位置への変換のベンチマーク
(4..15).each do |b|
  bits = 1 << b
  puts
  puts "#{bits} bits:"
  key = 1 << bits
  Benchmark.bm 10 do |r|
    r.report 'popcnt' do
      times.times { BitCounter.count(key-1) }
    end
    r.report 'index' do
      times.times { table[key] }
    end
    break unless 1.respond_to?(:bit_length)
    r.report 'bit_length' do
      times.times { key.bit_length-1 }
    end
  end
end