Bitz

A pure Ruby, JIT-friendly dynamic bitset implementation

Features

  • Dynamic resizing: Automatically grows buffer as needed when setting bits
  • Memory efficient: Uses packed byte arrays for optimal memory usage
  • Ruby-idiomatic: Standard operators (&, |, !) and method chaining support
  • 0-indexed: Bit positions start from 0, following standard conventions

Installation

Add this line to your application's Gemfile:

gem 'bitz'

And then execute:

$ bundle install

Or install it yourself as:

$ gem install bitz

Usage

Basic Operations

require 'bitz'

# Create a new bitset with default capacity (64 bits)
bitset = Bitz::Set.new

# Set individual bits
bitset.set(5)
bitset.set(10)
bitset.set(15)

# Check if bits are set
bitset.set?(5)   # => true
bitset.set?(3)   # => false
bitset.set?(100) # => nil (position doesn't exist yet)

# Unset bits
bitset.unset(10)
bitset.set?(10)  # => false

# Count set bits
bitset.count     # => 2 (bits 5 and 15 are set)

# Get total capacity
bitset.capacity  # => 64

Bulk Operations

# Set all bits to 1
bitset.set_all
bitset.count     # => 64

# Set all bits to 0
bitset.unset_all
bitset.count     # => 0

Custom Initialization

# Create bitset with specific capacity
large_bitset = Bitz::Set.new(256)

# Create bitset with all bits initially set
filled_bitset = Bitz::Set.new(64, fill: true)
filled_bitset.count  # => 64

Set Operations

Mutating Operations

set1 = Bitz::Set.new
set1.set(1)
set1.set(2)

set2 = Bitz::Set.new
set2.set(2)
set2.set(3)

# Union (modifies set1)
set1.set_union(set2)
# set1 now contains bits 1, 2, 3

set1 = Bitz::Set.new
set1.set(1)
set1.set(2)

# Intersection (modifies set1)
set1.set_intersection(set2)
# set1 now contains only bit 2

Non-mutating Operations

set1 = Bitz::Set.new
set1.set(1)
set1.set(2)

set2 = Bitz::Set.new  
set2.set(2)
set2.set(3)

# Union (creates new bitset)
union_result = set1 | set2
# union_result contains bits 1, 2, 3
# set1 and set2 are unchanged

# Intersection (creates new bitset)
intersection_result = set1 & set2
# intersection_result contains only bit 2
# set1 and set2 are unchanged

# Complement/NOT (creates new bitset with all bits flipped)
complement_result = !set1
# complement_result has all bits flipped - bits 0, 3, 4, 5, ..., 63 are set
# set1 is unchanged

Copying

original = Bitz::Set.new
original.set(5)

# Create independent copy
copy = original.dup
copy.set(10)

original.set?(10)  # => false (original unchanged)
copy.set?(5)       # => true (copy has original's bits)

API Reference

Constructor

  • Bitz::Set.new(bits = 64, fill: false) - Create bitset with initial capacity

Bit Manipulation

  • set(bit) - Set bit at position to 1
  • unset(bit) - Set bit at position to 0
  • set?(bit) - Check if bit is set (returns true/false/nil)

Bulk Operations

  • set_all - Set all bits to 1
  • unset_all - Set all bits to 0
  • count - Count number of set bits
  • capacity - Get total bit capacity

Set Operations (Mutating)

  • set_union(other) - Union with another bitset (modifies self)
  • set_intersection(other) - Intersection with another bitset (modifies self)

Set Operations (Non-mutating)

  • |(other) - Union operator (returns new bitset)
  • &(other) - Intersection operator (returns new bitset)
  • ! - Complement/NOT operator (returns new bitset with all bits flipped)

Copying

  • dup - Create independent copy of bitset

Error Handling

Operations between bitsets with different capacities will raise ArgumentError:

set1 = Bitz::Set.new(64)
set2 = Bitz::Set.new(128)

set1 | set2  # => ArgumentError: Cannot union bitsets with different capacities: 64 != 128

Development

After checking out the repo, run tests with:

rake test

This will run the full test suite including:

  • Basic bit manipulation tests
  • Set operation tests
  • Error condition tests
  • Performance validation tests

Contributing

Bug reports and pull requests are welcome on GitHub.

License

The gem is available as open source under the terms of the Apache 2.0.