Bit Array in Ruby using integer as a storage

My 2nd question on this site concerned bitmasks, actually. As @tokland correctly pointed out back then, bitmasks are really a pretty low-level technique that doesn't quite belong in a high-level language. Yes, it has its uses, but a hash or an array of symbols would solve the same kinds of problems in a more high-level, more expressive, and more readable manner.

In fact, trying to do this in a high-level language like Ruby presents some oddities, since you're using strings and integers to work with bits. And strings and integers are objects in Ruby, so you've got all these really high-level concepts and constructs involved in trying to do something with the lowest-level aspect of computing. It works, but it's like packing something tiny in a giant padded box.

Still, code's code, so:

• Your #test_iterate doesn't quite test what you think. You're just printing to stdout. What the assertion is actually testing is the value of @field.to_s(2)[1..-1].split("") - it doesn't really test that anything is being iterated. This implementation would also pass your test, even though it never iterates anything:

  def each(&block)
    # block argument ignored, no iteration; passes tests anyway
    @field.to_s(2)[1..-1].split("")
  end
  

  With your current code, I'd write the test like:

  expected = [1, 1, 0]
  BitArray.new(3).set([1,2]).each do |bit|
    assert_equal expected.shift, bit
  end
  assert expected.empty? # check that we looped the expected number of times
  

• You test for #get is also kinda strange. In all cases you check for 0 - how about a test where you expect to get 1 back? There really are only two possible return values, so you should probably check both.

• Why on Earth is your class using a 1-based indexing scheme? It's an array of a sort, so why not use a zero-based index like, well, like an array would do? I know this confused me greatly.

• Your #get method could perhaps just return a boolean. That's the closest you'll get to returning a raw bit.

  Update: I wasn't aware of this, but Fixnum actually has subscripting access to bits already. So #get can be written as simply:

  def get position
    @field[position]
  end
  

• Your #set and #clear methods should probably just use splats - it'd let you skip the array-boxing if just a single integer's passed in:

  def set *positions # use a splat
    positions.each { |position| @field |= 1 << (@size - position) } 
    self
  end
  

• unset might be a better name than clear - I'd expect clear to reset the entire array.

• You're going out of your way to always calculating @size - (some position) to make sure that you fill your array "from the left". I.e. position 1 is the left-most bit, rather than the (more natural) right-most bit. However, there's really no need. Inside your class, you can do whatever you want. Your current tests mostly check the string representation, so you can just flip that, rather than flip everything else.

• Filling from the right would also let you skip the size argument entirely; as you say, Ruby will catch overflows anyway, but you never actually check (or test) trying to get or set a bit outside the size.

• It's also just simpler to find and flip bits if you go from the right, and use a zero-based index, since any bit is given as simply 2**position. For instance:

  def set *positions
    positions.each { |position| @field |= 2**position } 
    self
  end
  

• You're including Enumerable, so use it. Your #count method could be written as just

  def count
    inject(0, :+)
  end
  

  since it'll use each, and each will yield either 1 or 0.

Again, this is all academic, as you're no doubt better off just using regular arrays or hashes. Still, here's a refactored version, because why not? Slightly different output for #to_s since I'm not using a size argument. And I'm using 0-based indices. But otherwise it's the same.

class BitArray
  include Enumerable

  def initialize
    @bits = 0
  end

  def set *positions
    positions.each { |position| @bits |= 2**position } 
    self
  end

  def unset *positions
    positions.each { |position| @bits ^= 2**position } 
    self
  end  

  def get position
    @bits[position]
  end

  def each(&block)
    bits = @bits
    until bits == 0
      yield bits & 1
      bits = bits >> 1
    end
  end

  def to_s
    @bits.to_s(2).reverse
  end

  def count
    inject(0, :+)
  end
end

require 'minitest/autorun'

class BitArrayTest < MiniTest::Test
  def test_equal
    assert_equal "0", BitArray.new.to_s
  end 

  def test_set
    assert_equal "0001", BitArray.new.set(3).to_s
    assert_equal "1011", BitArray.new.set(0, 2, 3).to_s
    assert_equal "0100000000101", BitArray.new.set(1, 10, 12).to_s
  end

  def test_unset
    assert_equal "101", BitArray.new.set(0, 1, 2).unset(1).to_s
  end

  def test_get
    assert_equal 1, BitArray.new.set(1, 2).get(2)
    assert_equal 0, BitArray.new.set(12).get(11)
    assert_equal 1, BitArray.new.set(12).get(12)
  end

  def test_count
    assert_equal 3, BitArray.new.set(1, 2, 5).count
  end

  def test_iterate
    expected = [1, 1, 0, 1]
    BitArray.new.set(0, 1, 3).each do |bit|
      assert_equal expected.shift, bit
    end
    assert expected.empty?
  end
end

Note that this version and its tests still don't deal with the issue of passing, say, negative indices or non-numeric indices.