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?

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.

Recommended Posts