1

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!

mahatmanich
  • 10,276
  • 5
  • 57
  • 79

4 Answers4

6

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" bit
  • Fixnum#[n] returns the integer's nth bit, i.e. 0 or 1
  • Fixnum#<< shifts the bit to the left. 1 << n is equivalent to 2n

Step 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.

Stefan
  • 102,972
  • 12
  • 132
  • 203
  • 1
    It would not only work, but it is much cleaner than going via `String` like other examples so far. – Neil Slater Aug 14 '15 at 07:21
  • undefined method `bit_length' for 98:Fixnum I am not on the latest Ruby version so this does not seem to work ruby 2.0.0p353 – mahatmanich Aug 14 '15 at 07:25
  • I thought so :/ Ruby is amazing! Is there another non-string way without using bit_length? – mahatmanich Aug 14 '15 at 07:30
  • 1
    @mahatmanich there's a Ruby implementation for `bit_length`: https://github.com/marcandre/backports/blob/master/lib/backports/2.1.0/fixnum/bit_length.rb Otherwise, you could use a fixed value, depending on your numbers. – Stefan Aug 14 '15 at 07:32
  • Very elegant!. Nice use of `bit_length`, `[]` and `< – Cary Swoveland Aug 14 '15 at 07:46
  • @Stefan 'Otherwise, you could use a fixed value, depending on your numbers' What do you mean by that? – mahatmanich Aug 14 '15 at 08:05
  • @mahatmanich a fixed value of `64` would cover all integers up to `2 ** 64`, maybe that's enough. Otherwise, you could use `i.size << 3` – Stefan Aug 14 '15 at 08:11
  • @Stefan I have never seen &:zero? What does &: do? ```zero?``` is the fixnum method returning true/false, but &: is unclear, some sort of shorthand? – mahatmanich Aug 14 '15 at 08:40
  • @Stefan ok I found it :-) http://stackoverflow.com/questions/1217088/what-does-mapname-mean-in-ruby – mahatmanich Aug 14 '15 at 08:42
2

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]
Cary Swoveland
  • 101,330
  • 6
  • 60
  • 95
2
(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

Neil Slater
  • 25,812
  • 6
  • 73
  • 91
  • 'The .map converts "1" characters to their value 2 ** i and "0" to nil so it can be removed' Can you elaborate on that? what does 2 ** i do? – mahatmanich Aug 14 '15 at 07:03
  • 1
    It is just exponentiation, i.e. `x ** y` is "x to the power of y". – Neil Slater Aug 14 '15 at 07:05
  • Phew! Why is the first reversal needed? – mahatmanich Aug 14 '15 at 07:11
  • 1
    Because `.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) – Neil Slater Aug 14 '15 at 07:14
2

Reverse 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.

Borsunho
  • 1,107
  • 7
  • 21