BitArray on Ruby (prototype)

bitarray_performance.rb

require 'benchmark'

class BitArray
  def initialize(capacity = 32 * 1024)
    @array = Array.new(capacity, 0)
  end

  def set(i)
    quotient, modulus = i.divmod(32)
    @array[quotient] |= 1 << modulus
  end

  def count
    result = 0

    for i in @array
      c =  ((i & 0xfff) * 0x1001001001001 & 0x84210842108421) % 0x1f
      c += (((i & 0xfff000) >> 12) * 0x1001001001001 & 0x84210842108421) % 0x1f
      c += ((i >> 24) * 0x1001001001001 & 0x84210842108421) % 0x1f

      result += c
    end

    result
  end

  def substract(bitarray)
    result = BitArray.new

    i = 0
    array_size = @array.size
    while i < array_size
      result[i] = @array[i] & ~bitarray[i]
      i += 1
    end

    result
  end

  def intersection(bitarray)
    result = BitArray.new

    i = 0
    array_size = @array.size
    while i < array_size
      result[i] = @array[i] & bitarray[i]
      i += 1
    end

    result
  end

  protected

  def [](i)
    @array[i]
  end

  def []=(i, v)
    @array[i] = v
  end

end

bitarray = BitArray.new

puts Benchmark.measure {
  1_000_000.times do |i|
    bitarray.set(i)
  end
}

puts Benchmark.measure {
  bitarray.count
}

puts Benchmark.measure {
  bitarray.intersection(BitArray.new)
}

puts Benchmark.measure {
  bitarray.substract(BitArray.new)
}