[ruby-dev:52248] [Ruby Feature#22399] Iterator Methods for String Bit Operations

7 Oct 2026

      Issue #22399 has been updated by matz (Yukihiro Matsumoto).

I looked at this together with #22405. Seven methods with 37 call forms is more than I want to add now, so let me step back.

As far as I can tell, the performance gain in both proposals comes from one thing: skipping bytes while searching for the next bit of a given value. A single search method, something like `bit_index(bit, offset = 0, lsb_first: true)` (name tentative), would be as fast for the sparse and long-run cases in your use cases, and `bit_offsets`, `bit_runs` and `bit_run_length` can be written on top of it in a few lines.

About the rest:

* `each_bit` and `bits`: a loop over `bit_get` already runs without allocation, and an Array of 0/1 takes 8 bytes per bit. In your examples the Array is immediately folded into an Integer or indexed, so what is really needed there may be reading a bit field as an Integer.
* `bit_runs`: one Array per run is heavy when runs are short.

Could you reconsider the proposal along these lines? I would also like to see measurements on mruby or PicoRuby, since microcontrollers are the main motivation.

Matz.

----------------------------------------
Feature #22399: Iterator Methods for String Bit Operations
https://bugs.ruby-lang.org/issues/22399#change-119340

* Author: hasumikin (hitoshi hasumi)
* Status: Open
----------------------------------------
PR URL: https://github.com/ruby/ruby/pull/19161

### What this adds

The original proposal (#22082) listed this iterator group. Matz asked for a minimal subset in #22082#note-13, and the proposal deferred the group in #22082#note-14. The methods build on the single-bit methods of #22118 and on the region arguments of #22279:

```
String#each_bit(lsb_first: true) {|bit| ... }                 -> self
String#each_bit(offset, length, lsb_first: true) {|bit| ... } -> self
String#each_bit(range, lsb_first: true) {|bit| ... }          -> self
String#each_bit(lsb_first: true)                              -> Enumerator
String#each_bit(offset, length, lsb_first: true)              -> Enumerator
String#each_bit(range, lsb_first: true)                       -> Enumerator

String#bits(lsb_first: true)                                  -> Array
String#bits(offset, length, lsb_first: true)                  -> Array
String#bits(range, lsb_first: true)                           -> Array
String#bits(lsb_first: true) {|bit| ... }                     -> self
String#bits(offset, length, lsb_first: true) {|bit| ... }     -> self
String#bits(range, lsb_first: true) {|bit| ... }              -> self

String#each_bit_offset(bit, lsb_first: true) {|offset| ... }                 -> self
String#each_bit_offset(bit, offset, length, lsb_first: true) {|offset| ... } -> self
String#each_bit_offset(bit, range, lsb_first: true) {|offset| ... }          -> self
String#each_bit_offset(bit, lsb_first: true)                                 -> Enumerator
String#each_bit_offset(bit, offset, length, lsb_first: true)                 -> Enumerator
String#each_bit_offset(bit, range, lsb_first: true)                          -> Enumerator

String#bit_offsets(bit, lsb_first: true)                                 -> Array
String#bit_offsets(bit, offset, length, lsb_first: true)                 -> Array
String#bit_offsets(bit, range, lsb_first: true)                          -> Array
String#bit_offsets(bit, lsb_first: true) {|offset| ... }                 -> self
String#bit_offsets(bit, offset, length, lsb_first: true) {|offset| ... } -> self
String#bit_offsets(bit, range, lsb_first: true) {|offset| ... }          -> self
```

`each_bit` and `bits` visit every bit of the region. They give each bit as `0` or `1`. `each_bit_offset` and `bit_offsets` visit the offsets of the bits that are equal to `bit`. The `bit` argument is `0`, `1`, `true` or `false`. The offsets come in increasing order.

```ruby
data = "\xAA\xCC".b
data.bits(8, 4)                        # => [0, 0, 1, 1]
data.bit_offsets(1)                    # => [1, 3, 5, 7, 10, 11, 14, 15]
data.bit_offsets(0, 8..)               # => [8, 9, 12, 13]
data.bit_offsets(1, lsb_first: false)  # => [0, 2, 4, 6, 8, 9, 12, 13]
data.each_bit_offset(1).size           # => 8
```

The pairing follows `each_byte` / `bytes`. The `each_*` form returns `self` with a block. Without a block, it returns an Enumerator. The Array form returns an Array. Like `bytes`, the Array form also accepts a block. With a block, it behaves like the `each_*` form.

### Use cases

#### Columnar data (LSB-first)

Apache Arrow stores validity bitmaps and boolean columns as LSB-first packed bitmaps. Arrow pads a bitmap buffer to a multiple of 64 bytes. The padding bits have no defined value, so a read must stop at the column length. The region forms express this limit directly. The typical read patterns are:

- **Null positions:** `bit_offsets(0, 0, length)` gives the indexes of the null elements of a column. A Ruby loop over `bit_set?` is not necessary. Without the region, the result includes the padding bits as nulls.

  ```ruby
  validity = "\xFD\x03".b         # 10 elements, element 1 is null, bits 10..15 are padding
  validity.bit_offsets(0)         # => [1, 10, 11, 12, 13, 14, 15]
  validity.bit_offsets(0, 0, 10)  # => [1]
  ```

- **Boolean columns:** `bits(0, length)` converts a packed column into an Array of `0` and `1` values.
- **Slices:** The region forms scan only the chunk of a bitmap that a batch covers. The offsets stay absolute. Thus they work with `bit_set?` and the mutation methods without adjustment.

#### Microcontrollers and wire formats

The `each_*` forms walk a buffer and do not allocate an Array. The region forms (with `offset..` or `(offset, length)`) continue from any bit offset. They do not unpack the whole buffer. On CRuby this matters for large buffers. `bits` on a 1 MiB buffer builds an Array of 8 million elements. `each_bit` with a block allocates nothing in the method itself.

The same property helps implementations for microcontrollers (mruby, PicoRuby). These implementations take the core API as their specification. On such devices, a String is often the only buffer a program has.

- **Protocol headers:** RFC protocol diagrams number bits MSB-first. `bits(offset, length, lsb_first: false)` returns a header field in wire order. A decoder can follow the diagram directly and does not reverse bits.

  ```ruby
  hdr = "\x12\x34\x81\x80".b                 # DNS header: ID, then the 16 flag bits
  flags = hdr.bits(16, 16, lsb_first: false)
  qr, rd, ra = flags[0], flags[7], flags[8]  # => 1, 1, 1
  ```

- **Huffman and other prefix codes:** A decoder reads a code stream one bit at a time and descends a tree. `each_bit` with a region reads the packed codes in the order the encoder wrote them. The decoder allocates nothing per bit. Bit-serial formats differ in packing order. JPEG entropy-coded segments and CCITT fax pack MSB-first, so they need `lsb_first: false`. DEFLATE packs LSB-first and reads with the default.

  ```ruby
  tree = ["a", ["b", ["c", "d"]]]  # 0 => a, 10 => b, 110 => c, 111 => d
  stream = "\x5B\x80".b            # 0 10 110 111 = "abcd", 9 bits
  node = tree
  out = +""
  stream.each_bit(0, 9, lsb_first: false) do |bit|
    node = node[bit]
    if node.is_a?(String)
      out << node
      node = tree
    end
  end
  out # => "abcd"
  ```

- **Bit-banged buses:** A shift-register chain receives a multi-byte frame MSB-first. `each_bit(lsb_first: false)` over the frame gives one GPIO write per bit. The program does not split the frame into Integers first.

- **1 bpp frame buffers:** A display such as the SSD1306 stores a page as one byte per column. Bit 0 is the top pixel. With the bitwise methods of #22118, `bit_offsets(1)` turns a pixel test into a coordinate list. `bitwise_and` of a sprite and the background keeps only the overlapping pixels. `bit_offsets(1)` yields their positions. `i / 8` is the column and `i % 8` is the row within the page.

  ```ruby
  sprite     = "\x00\x3C\x3C\x00".b
  background = "\x00\x00\x30\xFF".b
  hits = sprite.bitwise_and(background)
  hits.bit_offsets(1).map { |i| [i / 8, i % 8] } # => [[2, 4], [2, 5]]
  ```

#### Why not String#unpack?

`unpack1("b*")` and `unpack1("B*")` already give the bits as a `"0"`/`"1"` String. That form has four limits:

- It allocates a String eight times the size of the receiver.
- It moves only by whole bytes with `@`.
- It cannot list the offsets of the set or cleared bits.
- It returns characters, where `bit_get` returns Integers.

The iterators read in place. They take bit regions. They list offsets directly. Their results compose with the rest of the bit API.

### API Contracts

1. **Region arguments** are the same as for `bit_count`: no argument (the whole string), `(offset, length)`, or a Range, plus `lsb_first:`. A lone `offset` raises `ArgumentError`, as for `bit_count`.
2. **Reads clamp.** The methods cut a region that extends past the end of the string down to the bits that exist. A region that begins at or beyond the end yields nothing. An empty or inverted region yields nothing. `bit_count`, the other read-only region method, has the same behavior.
3. **Offsets are absolute.** `each_bit_offset` and `bit_offsets` yield offsets relative to the start of the string, in the numbering that `lsb_first:` selects. Thus `data.bit_set?(i, lsb_first: x)` is true for every `i` that `data.each_bit_offset(1, lsb_first: x)` yields.
4. **The `bit` argument** accepts `0`, `1`, `true` or `false`. The method converts any other object with `to_int`, as for an index, with the same exceptions. An Integer other than `0` or `1` raises `ArgumentError`. An object without `to_int` raises `TypeError`.
5. **Errors are raised without a block.** The method validates the arguments before it creates the Enumerator. Thus `"".each_bit(-1, 4)` raises `IndexError` immediately, not on the first `each`. The Enumerator validates the arguments again when it iterates or computes its size. Thus `to_int` conversions can run more than once.
6. **Enumerator#size** is the number of bits in the region for `each_bit`. For `each_bit_offset`, it is the number of matching bits. The Enumerator computes the size on demand from the current contents of the receiver.
7. **The block can modify the receiver.** The iteration reads the string again for every bit. It stops at the current end of the string. A longer receiver does not extend the iteration beyond the original region.
8. **Out-of-range arguments** follow #22279. A negative offset raises `IndexError`. A negative length raises `ArgumentError`. A position or length beyond `2**64 - 1` raises `ArgumentError`.
9. **Frozen receivers** work, because all four methods only read.
10. **Encoding** has no effect. The methods treat the receiver as a byte sequence, as in #22118.
11. **`lsb_first` changes only the bit numbering within each byte.** The byte order does not change, as in #22118 and #22279. The value must be `true` or `false`. Any other value raises `ArgumentError`, as in #22118.

### Performance

The script below gives the times. Each time is the median of 5 calls on a 1 MiB buffer. The machine is an AMD Ryzen 5 5600X with Ruby 4.1.0dev (master at 2db3072cfb) and this patch, gcc 13.3.0 `-O3`, YJIT off.

{{collapse(Benchmark script)
```ruby
sparse = "\x00".b * (1 << 20)                       # 1 MiB, 1,000 set bits
1000.times { sparse.bit_set(it * 8388) }
dense = "\xAA".b * (1 << 20)                        # 1 MiB, every other bit set
N = 1 << 23

# The alternatives give the same result as the new methods.
def offsets_by_loop(s) = (0...N).select { s.bit_set?(it) }
def bits_by_loop(s)    = Array.new(N) { s.bit_get(it) }
def each_by_loop(s)    = N.times { s.bit_get(it) }

def offsets_by_unpack(s)
  b = s.unpack1("b*")
  offsets = []
  i = -1
  offsets << i while (i = b.index("1", i + 1))
  offsets
end
def bits_by_unpack(s) = s.unpack1("b*").bytes.map { it - 48 }
def each_by_unpack(s) = s.unpack1("b*").each_byte { it - 48 }

def median(n = 5)
  Array.new(n) {
    t = Process.clock_gettime(Process::CLOCK_MONOTONIC)
    yield
    Process.clock_gettime(Process::CLOCK_MONOTONIC) - t
  }.sort[n / 2]
end

{ sparse:, dense: }.each do |name, s|
  raise unless offsets_by_loop(s) == s.bit_offsets(1) && offsets_by_unpack(s) == s.bit_offsets(1)
  printf "%-6s offsets loop   %.4f\n", name, median { offsets_by_loop(s) }
  printf "%-6s offsets unpack %.4f\n", name, median { offsets_by_unpack(s) }
  printf "%-6s bit_offsets    %.4f\n", name, median { s.bit_offsets(1) }
end
raise unless bits_by_loop(dense) == dense.bits && bits_by_unpack(dense) == dense.bits
printf "bits loop      %.4f\n", median { bits_by_loop(dense) }
printf "bits unpack    %.4f\n", median { bits_by_unpack(dense) }
printf "bits           %.4f\n", median { dense.bits }
printf "each loop      %.4f\n", median { each_by_loop(dense) }
printf "each unpack    %.4f\n", median { each_by_unpack(dense) }
printf "each_bit       %.4f\n", median { dense.each_bit { } }
```
}}

|                           | Sparse | Dense  |
|---------------------------|-------:|-------:|
| `bit_set?` loop           | 445 ms | 485 ms |
| `unpack1("b*")` + `index` | 8.9 ms | 321 ms |
| `bit_offsets(1)`          | 1.2 ms |  41 ms |

| Dense                                  | Array  | Block  |
|----------------------------------------|-------:|-------:|
| `bit_get` loop                         | 419 ms | 354 ms |
| `unpack1("b*")` + `bytes`/`each_byte`  | 374 ms | 244 ms |
| `bits` / `each_bit { }`                |  71 ms | 223 ms |

`bit_offsets` skips a byte with no matching bit in one step. The block forms gain little, because the block call dominates. Their benefit is that the method allocates nothing.

-- 
https://bugs.ruby-lang.org/