Three Bit Manipulation Methods (Ruby)

It's not about orthodox bit manipulation.

Bit manipulation is necessary when using Ruby, but sometimes when doing competitive programming, you may want to bit manipulation. So, if you take a look at Ruby again, you can see that it has all the bit operations (which is natural). What I find useful in competition pros is, for example, counting "bits", that is, converting integers to binary notation and counting the number of "1" Ruby.

``````to_s(2).chars.count { _1 == "1" }
``````

Can be written concisely. Also, so-called "bit full search" can be easily written in Ruby without using bits. Subset enumeration is often used in "bit full search". For example, when enumerating all subsets of `[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
``````

And so on. Result is

``````[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]]
``````

And certainly all subsets are listed (if it contains an empty set). It's strange that it's not in Ruby's built-in methods, but that's why

``````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
``````

Anyway, you can add it to the Array class. So if you want to get the same result as above

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

You can do it anyway. It would be convenient for competition professionals if there was this. Will it be added to the built-in?

Something like the main subject

So, although the following is not the main subject, I added three bit manipulation methods to Ruby. Neither is considered to be practical, so it's just a play. It looks like this.

``````class Integer
def each_bit
if block_given?
to_s(2).chars.reverse.map { _1 == "1" }.each { yield _1 }
else
to_enum(__method__)
end
end

def bit_reverse
to_s(2).chars.reverse.join.to_i(2)
end
end

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

First, `Integer # each_bit` executes a block bit by bit, and the block variable contains` true` if the bit is 1, and `false` if the bit is 0.

``````0b10101101.each_bit { p _1 }
``````

When you run

``````true
false
true
true
false
true
false
true
``````

Is the output. Note that it is executed from the lower bits. So at the end it will always be `true`.

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

173.to_s(2)    #=>"10101101"
``````

Such.

`Array # to_i` is the opposite of this. Consider the true contents of the array as 1 and the false ones as 0 as binary representations, and convert them to Integer. Note that this is also packed in the lower bits from the left of the array.

``````[true, false, true, true, false, true, false, true].to_i    #=>173
[: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` is what I came up with in Texto. Create an Integer by inverting the bits of the Integer. It's confusing, but it's completely different from bit inversion (negative, `Integer # ~`).

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

Note that `bit_reverse.bit_reverse` is not always restored (you know?).

It was Mr. Osomatsu.