Lets say I have an integer 98. The binary representation of this string would be:
(98).to_s(2) # 1100010
Now I want to convert this binary string to an integer array of all the bits that are set. This would give me:
[64,32,2]
How would I go about this?
Update: The conversion of int to int array does not necessarily need to involve String, it is just what I knew. I assume non String operations would also be faster.
Ruby is amazing seeing all these different ways to handle this!
This would work:
i = 98
(0...i.bit_length).map { |n| i[n] << n }.reject(&:zero?)
#=> [2, 32, 64]
Fixnum#bit_length returns the position of the highest "1" bitFixnum#[n] returns the integer's nth bit, i.e. 0 or 1Fixnum#<< shifts the bit to the left. 1 << n is equivalent to 2nStep by step:
(0...i.bit_length).map { |n| i[n] }
#=> [0, 1, 0, 0, 0, 1, 1]
(0...i.bit_length).map { |n| i[n] << n }
#=> [0, 2, 0, 0, 0, 32, 64]
(0...i.bit_length).map { |n| i[n] << n }.reject(&:zero?)
#=> [2, 32, 64]
You might want to reverse the result.
In newer versions of Ruby (2.7+) you could also utilize filter_map and nonzero? to remove all 0 values:
(0...i.bit_length).filter_map { |n| (i[n] << n).nonzero? }
#=> [2, 32, 64]
String like other examples so far.
bit_length: github.com/marcandre/backports/blob/master/lib/backports/2.1.0/… Otherwise, you could use a fixed value, depending on your numbers.64 would cover all integers up to 2 ** 64, maybe that's enough. Otherwise, you could use i.size << 3Reverse the string, map it to binary code values of each digit, reject zeros. Optionally reverse it again.
s.reverse.chars.map.with_index{ |c, i| c.to_i * 2**i }.reject{ |b| b == 0 }.reverse
Or you could push the values to array with each_with_index
a = []
s.reverse.each_with_index do |c, i|
a.unshift c.to_i * 2**i
end
what is probably faster and more readable, but less idiomatic.
.map on a String here? It's not in core Ruby.with_index modifier.
(98).to_s(2).reverse.chars.each_with_index.
map {|x,i| x=="1" ? 2**i : nil }.compact.reverse
Phew! Let's break that down:
First get the binary String as your example (98).to_s(2)
We will need to start 0-index from right hand side, hence .reverse
.chars.each_with_index gives us pairs such as [ '1', 4 ] for character at bit position
The .map converts "1" characters to their value 2 ** i (i.e. 2 to the power of current bit position) and "0" to nil so it can be removed
.compact to discard the nil values that you don't want
.reverse to have descending powers of 2 as your example
x ** y is "x to the power of y"..to_s outputs with least-significant digit on the right, and we want to associate that with bit-position 0 when calculating which power of 2 to use. You can also solve that problem by subtracting position in the string off of the length of the string (Cary's first example does that)Here are a couple of ways:
#1
s = (98).to_s(2)
sz = s.size-1
s.each_char.with_index.with_object([]) { |(c,i),a| a << 2**(sz-i) if c == '1' }
# => [64, 32, 2]
#2
n = 2**(98.to_s(2).size-1)
arr = []
while n > 0
arr << n if 90[n]==1
n /= 2
end
arr
#=> [64, 32, 2]
98.to_s(2).size is long and slow for 98.bit_length
98.to_s(n) is slow when n = 2? Were I writing Integer#to_s I'd first check if the argument were 2 and if so, compute the result by just examining the bits. Similarly, I would expect 2**n and n / 2 are computed intelligently.to_s(n) does a conversion to base n. As the computer already saves the Integer that way, I would expect no conversion here. But it does convert the number to String which means that every binary digit gets converted to Char. That's 8 bit at best, you can check with 98.to_s(2).encoding, as Ruby allows Unicode since 1.9. After that, an additional method .size() is called, which should be about as fast as .bit_length.n /= 2 is even faster than n >>= 1 on my system. My Intuition based on C-ish languages expected the opposite. Here's more info on Char/String encodings (Unicode) in Ruby, the comment above was getting too long.