ビット操作メソッド三題（Ruby）

Ruby を使っているとビット操作はあまり必要なのだが、競技プログラミングをやっていたりすると時にはビット操作したくなることもある。で、Ruby をあらためて見てみると（当り前だが）ビット操作も一通り揃っているわけだ。競プロで便利だなと思うのは例えば「ビットの立っている」ものを数える、つまり整数を二進数表現に直して "1" の数を数えるというもので、Ruby では

to_s(2).chars.count { _1 == "1" }
#追記　以下でよい
to_s(2).count("1")

と簡潔に書ける。
　また、いわゆる「ビット全探索」は、Ruby ではビットを使わなくても簡単に書ける。例えば、[0, 1, 2, 3, 4]のすべての部分集合を列挙する場合は、

ary = [0, 1, 2, 3, 4]
co = 0
(0..ary.size).each do |i|
  ary.combination(i) do |sub_set|
    p [co, sub_set]
    co += 1
  end
end

などと書ける。結果は

[0, []]
[1, [0]]
[2, [1]]
[3, [2]]
[4, [3]]
[5, [4]]
[6, [0, 1]]
[7, [0, 2]]
[8, [0, 3]]
[9, [0, 4]]
[10, [1, 2]]
[11, [1, 3]]
[12, [1, 4]]
[13, [2, 3]]
[14, [2, 4]]
[15, [3, 4]]
[16, [0, 1, 2]]
[17, [0, 1, 3]]
[18, [0, 1, 4]]
[19, [0, 2, 3]]
[20, [0, 2, 4]]
[21, [0, 3, 4]]
[22, [1, 2, 3]]
[23, [1, 2, 4]]
[24, [1, 3, 4]]
[25, [2, 3, 4]]
[26, [0, 1, 2, 3]]
[27, [0, 1, 2, 4]]
[28, [0, 1, 3, 4]]
[29, [0, 2, 3, 4]]
[30, [1, 2, 3, 4]]
[31, [0, 1, 2, 3, 4]]

となって、確かにすべての部分集合が列挙されている（空集合を含む場合）。Ruby の組み込みメソッドにないのが不思議なくらいだが、これはだから

class Array
  def each_subset(empty_set=true)
    if block_given?
      n = empty_set ? 0 : 1
      (n..size).each do |i|
        combination(i) { yield _1 }
      end
    else
      to_enum(__method__, empty_set)
    end
  end
end

とでもして Array クラスに追加してやったらよい。で、上のと同じ結果を得ようと思えば

[0, 1, 2, 3, 4].each_subset.with_index do |ary, i|
  p [i, ary]
end

とでもすればよいのである。これがあったら競プロに便利だろうね。組み込みに追加されないかね。

で、以下が本題というほどでもないのだが、Ruby にビット操作メソッドを三つ追加してみた。いずれも実用性はないものと考えられ、たんなる遊び。
こんな感じである。

class Integer
  def each_bit
    if block_given?
      to_s(2).chars.reverse.map { _1 == "1" }.each { yield _1 }
      #これでよい
      #digits(2).each { yield _1 == 1 }
    else
      to_enum(__method__)
    end
  end
  
  def bit_reverse
    to_s(2).chars.reverse.join.to_i(2)
    #これでよい
    #to_s(2).reverse.to_i(2)
  end
end

class Array
  def to_i
    map { _1 ? "1" : "0" }.reverse.join.to_i(2)
  end
end

　
まず、Integer#each_bitはビットごとにブロックを実行し、ブロック変数にはビットが 1 なら true、0 なら false が入るというもの。

0b10101101.each_bit { p _1 }

を実行すると

true
false
true
true
false
true
false
true

が出力となる。下位ビットから実行されていくのに注意。だから最後は必ず true になる。

173.each_bit.map(&:itself)    #=>[true, false, true, true, false, true, false, true]
0.each_bit.map(&:itself)      #=>[false]

など。

Array#to_iはこれの反対。配列の中身で真のものを 1、偽のものを 0 として二進表現と見做し、Integer に変換する。これも配列の左から下位ビットに詰められていくのに注意。

[:a, nil, 1, -1, 1 == 0, 1.integer?, 0.1 < 0, true].to_i    #=>173
173.each_bit.map(&:itself).to_i    #=>173

　
Integer#bit_reverseはテキトーに思いついたもの。Integer のビットを左右反転させた Integer を作る。まぎらわしいが、ビット反転（否定、Integer#~）とは全然ちがうのです。

173.bit_reverse    #=>181
173.to_s(2)    #=>"10101101"
181.to_s(2)    #=>"10110101"

なお、bit_reverse.bit_reverseは必ずしも元に戻らないので注意（わかりますね？）。
　

おそまつ様でした。