Working with Ruby
Hi, I am Jan. This is my old Ruby blog. I still post about Ruby, but I now do it on idiosyncratic-ruby.com. You should also install Irbtools to improve your IRB.

Storing an array of indices in an integer

August 2009, ruby · ruby1-9 · hints

Sometimes you have an array of indices. These might, for example, act as flags, whether some specific options are set or not. A nice way to store this list is, to store it in one single number.

This can be achieved by treating each index as an exponent of 2, so you can build a binary representation out of them. This binary representation (also known as bitset) can be displayed as a single decimal number – and vice versa.

An example
Let’s assume that our array is: [3,6,9]

Now we can treat it as 2 3 + 2 6 + 2 9, which equals 584. In this number, all the information is still present and can be converted back to [3,6,9]

The following snippet is a ruby implementation of this.

simple_bitset 
 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# binary representation: store an array of indices in one decimal number

class Array
  # Generates an integer representing all the set bits
  def to_bri # to binary representation integer
    self.inject(0){ |ret, cur| ret + 2**cur }
  end
end

class Integer
  # Generates an array showing the set bit indexes
  def to_bra # to binary representation array
    ret = []
    i = 0
    while self >= x = x ? x*2 : 1
      ret << i if 0 < self[i] # ruby sugar: bit is set?
      i+=1
    end

    ret
  end

=begin other versions

  # oldest one
  def to_bra
    # convert the decimal integer to binary form with to_s and base 2 and then
    # check each char to add the current index to the array, if it is set
    self.to_s(2).reverse.chars.each_with_index do |ele,index|
      ret << index if ele == '1'
    end
  end

  # cool one... but uses float :/
  def to_bra
    (0..Math.log(self)/Math.log(2)).select{ |e| 0<self & 2**e }
  end

  # same again (without float)
  def to_bra
    ret = []
    i = 0
    while self >= x = x ? x*2 : 1
      ret << i if 0 < self & x
      i+=1
    end

    ret
  end

  # faster, uses 1.9
  def to_bra
    self.to_s(2).reverse.bytes.each_with_index.select{|e,_|e == 49}.map &:pop
  end

=end
end
Creative Commons License

Anonymous | August 03, 2009

I looks a lil bit COMPLEX for such a easy thing, which should know every developer - espially these one developing in ruby ^^

J-_-L | August 03, 2009

I agree with you, that every developer should know this. Although the snippet might look a little bit complex, it provides the functionality in a 'nice to use'-way - in my opinion ;)

payload | August 04, 2009

i think to_bra is a little bit heavy. you do string operations, but you could do the same with integer operations. divide by two and look at the rest. if it's 0 there must be a one and you can append the index into the list

J-_-L | August 04, 2009

Yes, it lets do the conversion by (probably slow) ruby-functions. I don't know, how much slower it is, but I think, I'll do a little benchmark about this on one of the next days