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,791
  • 5
  • 63
  • 82

4 Answers4

7

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.

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]
Stefan
  • 109,145
  • 14
  • 143
  • 218
  • 2
    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
  • 2
    @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 `<<`. Best so far, imo. I was looking through `Fixnum` methods for what I now see is `bit_length`. I don't know how I missed it, as there aren't that many. In any event, I'm glad to know of it. – Cary Swoveland Aug 14 '15 at 07:46
  • 1
    @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
  • Such a performing solution. For large Numbers, converting to string and back is MUCH slower. I only need the first step (without `<<` or `reject` and it's even faster than iterating over the array with `result[i += 1] = input % 2 == 1; input /= 2;` – Cadoiz Nov 18 '22 at 07:34
  • Stefan, upon returning to this question to respond to a comment on my answer I began re-reading your answer. When I got to `map { |n| i[n] << n }.reject(&:zero?)` I thought I might suggested you mention the since-introduced method `filter_map` then saw you'd done that earlier today (and understand why). – Cary Swoveland Nov 18 '22 at 20:45
  • @CarySwoveland what a coincidence :-) I sometimes revise my (old) answers when getting comments and / or votes. – Stefan Nov 18 '22 at 21:05
  • Me too, often after wondering what I was thinking, but to be fair, sometimes I was just a crazy kid when I wrote my original answer. – Cary Swoveland Nov 19 '22 at 08:19
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
  • 106,649
  • 6
  • 63
  • 100
  • `98.to_s(2).size` is long and slow for `98.bit_length` – Cadoiz Nov 18 '22 at 08:46
  • @Cadoiz, are you sure `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. – Cary Swoveland Nov 18 '22 at 20:34
  • Not slow in terms of absolute time, that should be some micro- or even nanoseconds. Slow in relative time, which means slower by a factor. `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`. – Cadoiz Nov 21 '22 at 07:49
  • Fun-Fact: For some reason, `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](https://www.rubyguides.com/2019/05/ruby-ascii-unicode/), the comment above was getting too long. – Cadoiz Nov 21 '22 at 07:53
  • Your reply to my comment above makes sense. – Cary Swoveland Nov 21 '22 at 20:31
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
  • 26,512
  • 6
  • 76
  • 94
  • '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
  • 2
    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,127
  • 7
  • 21