Feature #22118: Introduce Basic Bit Operations into String

• Status: Open
• Assignee: -
• Target version: -

[hasumikin (hitoshi hasumi)]

This PR implements basic bit operations into String, incorporating revisions made following the discussion (esp. #note-5)

PR URL: https://github.com/ruby/ruby/pull/17353

Single-bit read and mutation

• String#bit_get(offset, lsb_first: true) -> 1 | 0 | nil
• String#bit_set?(offset, lsb_first: true) -> true | false | nil
• String#bit_set(offset, lsb_first: true) -> self
• String#bit_clear(offset, lsb_first: true) -> self
• String#bit_flip(offset, lsb_first: true) -> self

Note for bit_set/bit_clear/bit_flip: As these methods are destructive-only (they have no non-destructive counterpart), no ! is added. The ! suffix is meant to distinguish the dangerous member of a destructive/non-destructive pair, following the setbyte precedent.

Bitwise operators

• String#bitwise_not -> String
• String#bitwise_not! -> self
• String#bitwise_and(other) -> String
• String#bitwise_and!(other) -> self
• String#bitwise_or(other) -> String
• String#bitwise_or!(other) -> self
• String#bitwise_xor(other) -> String
• String#bitwise_xor!(other) -> self

Popcount

• String#bit_count -> Integer

---

API Contracts

1. Bit-order keyword

lsb_first: true (default)

Within each byte, offset = 0 is the LSB. Numbering proceeds upward through byte[0] and then continues at the LSB of byte[1]:

        byte[0]                    byte[1]
offset: 7  6  5  4  3  2  1  0     15 14 13 12 11 10 9  8
bit:    b7 b6 b5 b4 b3 b2 b1 b0    b7 b6 b5 b4 b3 b2 b1 b0
                             ^                          ^
                             LSB                        LSB

offset = byte_index * 8 + bit_in_byte

lsb_first: false for MSB-first

Byte order is preserved (byte[0] is still first), but within each byte numbering starts at the MSB:

        byte[0]                    byte[1]
offset: 0  1  2  3  4  5  6  7     8  9  10 11 12 13 14 15
bit:    b7 b6 b5 b4 b3 b2 b1 b0    b7 b6 b5 b4 b3 b2 b1 b0
        ^                          ^
        MSB                        MSB

offset = byte_index * 8 + (7 - bit_in_byte)

The keyword only controls bit numbering within each byte. Byte order itself is unchanged.

LSB-first is the more common convention for general in-memory bitmap use, including formats and APIs such as Apache Arrow validity bitmaps, ext4 block bitmaps, Roaring bitmaps, Linux/BSD bitmap APIs, and hardware register descriptions.
MSB-first is also needed for domains such as RFC-style network protocol diagrams, PNG low-bit-depth scanlines, BitTorrent bitfields, and some compressed bit streams.
This is the reason that we define lsb_first: true as the default.

The bit-order keyword must be accepted by all bit_* methods with the same default; a getter and a setter disagreeing on bit addressing would be disastrous.

One temporary exception: Since the bit_count introduced in this version counts the population of the entire string without taking arguments, it does not accept a bit-order keyword. If arguments for specifying a range are introduced in the future, the bit-order keyword should be introduced at that time.

2. Out-of-range behavior

Read methods: String#bit_get and String#bit_set? return nil when the bit offset is out of range.

On the other hand, mutating methods such as String#bit_set, String#bit_clear, and String#bit_flip raise IndexError for an out-of-range bit offset. This follows the same general distinction as read-like access versus write-like access: reading a missing position can return nil, but mutating a missing position should not silently do nothing.

If the bit offset is too large to be represented internally, all of these methods raise ArgumentError before applying the read/write out-of-range rule. This bound is specified explicitly because the representable offset range may differ between Ruby implementations.

3. Negative bit offsets

Negative bit offsets are rejected with IndexError.

Although Ruby often uses negative indices to count from the end, combining negative bit offsets with the lsb_first: true/false mechanism would make the numbering rule harder to explain and reason about. The API keeps bit offsets as non-negative flat positions from the beginning of the string.

4. Length mismatch for binary bitwise operations

String#bitwise_and, String#bitwise_or, String#bitwise_xor, and their ! variants require both operands to have the same byte size. If the byte sizes differ, they raise ArgumentError.

This avoids implicit truncation or zero-padding. Since these methods operate on strings as fixed-size bitmaps, requiring equal sizes makes the operation explicit and predictable.

Silent zero-extension would let corrupted results flow downstream in the typical use cases (checksums, masks); callers who want padding can ljust explicitly.

5. Encoding

All bit operations treat the receiver as a byte sequence. For non-destructive methods that return a String, the return value's encoding is set to Encoding::BINARY. Destructive methods do not alter the receiver's encoding, consistent with setbyte, which likewise lets a byte-level mutation produce an encoding-invalid string without changing the encoding.

[hasumikin (hitoshi hasumi)]

• Description updated (diff)

[hasumikin (hitoshi hasumi)]

Memorandom.
I had a face-to-face conversation with Matz and Shugo yesterday.

Matz: each_bit should yield 0/1, not false/true
Me: (Oh, still, acceptable to me)
Matz: I don't like the keyword lsb_first:.
Shugo: How about using encoding or some internal flag?
Me: (Yes, that's what I wanted)
Matz: Hmmm...

(Matz didn't reject it at least)

If it is realized, Pretty-Print could make something like this:

data = "\x01\x02\x03\x04\x05\x06"
data.bit!(false) # Set the encoding (or internal flag) as BITS with MSB-first
p data.bit_at(7)
=> 1 # Position 7 of 00000001 numbering from MSB
pp data
=> 00000001 00000010 00000011 00000100
   00000101 00000110

[Dan0042 (Daniel DeLorme)]

Introducing efficient bit operations is a great idea, but looking at the proposed methods, having to pass lsb_first: repeatedly across multiple bit-related methods suggests that the bit-endianness is a cross-cutting concern.

I believe it would result in cleaner code to specify that configuration once at initialization of a dedicated BitSet class (perhaps as String::BitSet or a stdlib class)

bitmap = BitSet.new(backing_string, lsb_first: true)
bitmap.bit_at(offset)

It could allocate its own backing string if omitted, similar to StringIO.

[kou (Kouhei Sutou)]

It's just an idea...

How about removing lsb_first: and always processing offset as LSB first offset? But we'll also provide Integer#to_msb_offset.

data = "\x01"
p data.bit_at(0.to_msb_offset) # => 1 # (0.to_msb_offset => 7)

We can reuse Integer#to_msb_offset for Integer#[] that processes offset as LSB first offset because X >> offset always processes offset as LSB first offset.

p 0b10000000[7]               # => 1
p 0b10000000[0.to_msb_offset] # => 1 

[matz (Yukihiro Matsumoto)]

I largely accept this proposal. Byte buffer manipulation is a real need, both for embedded Ruby and for CRuby where String already serves as the de facto byte container. Here are my decisions on the details.

Naming: the vocabulary shall be bit_get, bit_set, bit_clear, bit_flip, bit_count (see #20163), and bitwise_not/and/or/xor with their ! variants. The bit_* / bitwise_* distinction (single-bit inspection vs whole-buffer operation) is a good one.

bit_get shall return 0 | 1 | nil, consistent with Integer#[] and useful for arithmetic and copying bits between buffers. I understand the desire to write if str.bit_get(index), but a boolean return would silently conflate a clear bit with an out-of-range offset, hiding off-by-one bugs. For the conditional use case, add a predicate bit_set?(offset, ...) returning true/false (nil for out of range); it pairs with the bit_set writer and matches Integer's bit predicates (allbits? etc.).

bit_set/bit_clear/bit_flip being destructive-only is fine; a non-destructive variant that copies the whole buffer for one bit has little use, and str.dup.bit_set(i) is available. No ! suffix, following the setbyte precedent: ! marks the dangerous one of a pair, and there is no pair here.

Please also specify the following explicitly in the ticket, not just in the PR:

• Length mismatch in binary bitwise_* operations raises ArgumentError. Silent zero-extension would let corrupted results flow downstream in the typical use cases (checksums, masks); callers who want padding can ljust explicitly.
• Encoding: the operations treat the receiver as bytes and the result encoding shall be specified (I suggest BINARY for non-destructive results).
• The bit-order keyword must be accepted by all bit_* methods with the same default; a getter and a setter disagreeing on bit addressing would be disastrous.
• Out-of-range offset: bit_get returns nil (like getbyte), the writers raise IndexError (like setbyte). Reads are lenient, writes are strict.

Matz.

[hasumikin (hitoshi hasumi)]

• Description updated (diff)

Thank you, Matz. Based on your decisions in #note-5, I've updated the Description to serve as the finalized specification. Summary:

• Renamed bit_at to bit_get, returning 1 | 0 | nil.
• Added the method bit_set?, returning true | false | nil (nil for out of range).
• bit_set/bit_clear/bit_flip remain destructive-only with no ! variant, following the setbyte precedent.
• Out-of-range: reads (bit_get, bit_set?) return nil; writes (bit_set/bit_clear/bit_flip) raise IndexError.
• bitwise_and, bitwise_or, bitwise_xor, and their ! variants raise ArgumentError on byte-size mismatch (no implicit zero-extension).
• Encoding: all operations treat the receiver as bytes; non-destructive String results are Encoding::BINARY.

Two points I'd like to confirm:

1. bit_count and the bit-order keyword. In this PR, bit_count takes no arguments and therefore accepts no bit-order keyword, which is the one exception to "all bit_* methods accept the keyword with the same default." I intend to add the keyword together with range arguments in a future extension. I hope this temporary asymmetry is acceptable.

2. Very large bit offsets. For an offset too large to be represented internally, all single-bit methods raise ArgumentError before the read/write out-of-range rule (nil vs IndexError) is applied. This is not merely a CRuby implementation detail: the internally representable offset range can differ between implementations (e.g. mruby and mruby/c), so I'd like to keep this bound explicit and consistent across implementations rather than tie it to a single interpreter's internal width. I've documented it in the Description accordingly.

---

Note: the GitHub PR has not been updated to match this specification yet. I'll post another comment here once the PR is updated.

[mame (Yusuke Endoh)]

There's no writer that takes the bit value as an argument. Is it really OK?
We need to write str.send(val == 1 ? :bit_set : :bit_clear, offset) to do so, which is clearly painful.

Could we have something like bit_put(offset, value)?

(If bit_put is available, we don't need bit_set, bit_clear, and bit_flip, IMO.)

[mame (Yusuke Endoh)]

• Related to Feature #22082: Introduce Bit Operations into String added

[hasumikin (hitoshi hasumi)]

#note-7

I do not oppose bit_put itself, but my future plan includes introducing a range parameter like:

data.bit_set(3..19)

In the above, you can assume that the data is a header managing some resource or a serial protocol payload.
In this form, bit_set and bit_clear look more natural to me, and bit_flip wouldn't be replaced by bit_put

[hasumikin (hitoshi hasumi)]

I turned the PR ready to review: https://github.com/ruby/ruby/pull/17353
If the requirement written in the current description (and the reconfirmation in #note-6) is just enough, I believe it can go forward