12
$\begingroup$

I do not know of any languages that support this idea but I just thought that since numbers are just bits, why should we not be able to access those bits directly? In most languages such as C or C++, to manipulate bits, one must use bitwise logic, confusing to some people. Related Stack Overflow question.

What if numbers could be 'indexed' like arrays to access individual bits?

int x = 10; // 1010 in binary
x[0]; // 0
x[1]; // 1
x[2]; // 0
x[3]; // 1

x[2] = 1;
x; // 14

This would be much easier to use than bitwise operators such as | and &. But no languages I have heard of allow integers to just be blatantly treated as bit arrays.

I was wondering if there is a catch to implementing this. Do CPUs lack trivial instructions to manipulate bits in this manner, making this impractical to implement? What are the downsides to this feature that stopped most languages from adding them?

$\endgroup$
4
  • $\begingroup$ In Swift, large integers are Collection<Word> for hardware reasons, but I think I prefer a collection of bits conceptually. $\endgroup$
    – Bbrk24
    Commented May 18, 2023 at 0:14
  • $\begingroup$ There are certainly plenty of languages with indexable bitfield and bit array types; are you interested particularly in the idea of implicitly overloading integer values to produce them? $\endgroup$
    – Michael Homer
    Commented May 18, 2023 at 0:14
  • $\begingroup$ @MichaelHomer Basically. $\endgroup$
    – CPlus
    Commented May 18, 2023 at 0:15
  • 6
    $\begingroup$ Ruby sort of allows integers to be indexed as if they were arrays, e.g. x[i] is equivalent to x >> i & 1. You can even use slices when indexing. $\endgroup$
    – naffetS
    Commented May 18, 2023 at 0:27

6 Answers 6

13
$\begingroup$

I wouldn't store them as arrays, but you can certainly implement such a syntax efficiently. If you translate x[0] to x & 1 you'll get 0 if x=10. So you could access any bit by translating x[i] to (x >> i) & 1.

For the assignment, you'd go about the same, you can use bit-wise or | and bit-wise and & to manipulate x, so x[i] = 1 would become x = x | (1 << i) and x[i] = 0 would become x = x & ~(1 << i).

I think it would certainly be interesting if a language would allow any type to be indexed like an array

$\endgroup$
2
  • 2
    $\begingroup$ Assignment is a bit trickier: you can to do x |= 1 << i to set it, but x &= ~(1 << i) to clear it. $\endgroup$
    – Bbrk24
    Commented May 18, 2023 at 0:21
  • $\begingroup$ @Bbrk24 True! I just "coded" that off of my head, I knew there was gonna be a mistake somewhere :D $\endgroup$
    – ruarq
    Commented May 18, 2023 at 0:27
8
$\begingroup$

It would encourage inefficient code

90% of the time when you're doing individual bit lookups on an int, you're doing something "wrong". E.g., this would encourage those who don't feel comfortable with bitwise OR to write something like this:

function nor(x, y) {
    int z = 0;

    for (int i = 0; i < 64; i++) {
        z[i] = 1 - (x[i] || y[i]);
    }
}

This takes potentially hundreds of times longer than a simple bitwise OR and NOT. Something this extreme would most likely be rare, but operations which can be implemented with a chain of a few bitwise operations, such as implementing checksum algorithms or splitting apart packets into fields, might appear to be good places to use bit indexing to a bitwise novice, discouraging learning how to "do it right" and encouraging dramatically slower code.

$\endgroup$
3
  • 1
    $\begingroup$ If an optimizer can vectorize code like this on regular numbers, would it not be able to "vectorize" bitwise math into regular operations? $\endgroup$
    – Bbrk24
    Commented May 18, 2023 at 0:19
  • 2
    $\begingroup$ @Bbrk24 Possibly, but when the complexity is higher (e.g., when multiple bitwise operations would need to be combined in a somewhat complicated way to recreate the behavior), I'm not sure how capable a compiler would be of reverse engineering it. E.g., a checksum algo implemented with a loop or two over the bits in the input. $\endgroup$ Commented May 18, 2023 at 0:22
  • $\begingroup$ @Bbrk24 Vectorizing code like this on regular numbers is very challenging, and apparently often still fails for reasons not obvious to the programmer. Compiler writer work and optimization time could be spent on turning that into a NOR, but it's going to take a lot of time on both parts, time probably better spent elsewhere. $\endgroup$
    – prosfilaes
    Commented May 21, 2023 at 22:51
6
$\begingroup$

Strictly speaking, an "array" is a specific kind of data structure where elements are stored at contiguous, equally-spaced memory addresses. The smallest addressable unit of memory is typically one byte, so from just this consideration, an integer cannot be treated exactly as an "array" of booleans, because individual bits don't have memory addresses. But this is more of a pedantic note about terminology; really you want to know the pros and cons of integers being indexable to access their individual bits. The a[i] syntax is for accessing an element from a sequence by index, and the use of this syntax doesn't imply that a is an array.

So then why don't popular languages allow indexed access to the individual bits of an integer? Here are a few good reasons:

  • Confusing error messages. It's quite common for beginners to write a[i] thinking a is an array of integers, when it is actually an integer. A compiler which reports a type error "a is an integer, not an array" directly addresses their misapprehension, where "a[i] is a boolean, not an integer" would be less helpful.

    I'd argue this reason alone is sufficient, because the intentional use of this niche feature by experienced programmers would be much less common than the accidental use by beginners.

  • Most of the time, you don't want only one bit. Yes, you can use a boolean array to represent a set of integers, but most of the set operations you want to do ─ unions, intersections, complements, subtractions, subset tests ─ depend on the whole set, not just one element. These use cases are already supported with bitwise operators: a | b, a & b, ~a, a & ~b, and (~a & b) == 0.

    The set operations which do care about individual bits are adding, removing, membership tests, and (occasionally) toggling. But these aren't that hard to write with bitwise operations: a |= 1 << i, a &= ~(1 << i), (a & (1 << i)) != 0, and a ^= 1 << i. For membership tests and removal, the a[i] syntax would be slightly simpler ─ but for adding or toggling, the bitwise operations use fewer source tokens than indexed accesses would. If your language treats non-zero integers as "truthy" values, then you can write just a & (1 << i) for set membership.

  • Names are better than numbers. When you do care about individual bits, it's often because you've assigned a specific meaning to each bit, as in a bit field. In this case the individual bits are logically more similar to the fields of an object, than the elements in an array; it's rare that you would want to access a bit dynamically by index, rather than by a statically known name.

    So in these use-cases, you could write flags[CONNECTED] to access the "connected" flag as a Boolean value, but this requires declaring CONNECTED as the appropriate constant. Instead, you could just as well write (flags & CONNECTED) != 0. Moreover, the syntax for creating the bitfield is simpler using the bitwise | operator, than indexed writes.

$\endgroup$
3
  • 1
    $\begingroup$ hmm. I'll take a[i] = 1, a[i] = 0, a[i] != 0, and a[i] ^= 1 any day over a |= 1 << i, a &= ~(1 << i), (a & (1 << i)) != 0, and a ^= 1 << i $\endgroup$ Commented Jul 26, 2023 at 23:04
  • $\begingroup$ I think that the "Confusing error messages" would be entirely addressed by requiring a slightly more intentful syntax, such as a.bits[i] = 1 $\endgroup$ Commented Jul 26, 2023 at 23:11
  • 1
    $\begingroup$ IMHO the fact that many times more than one bit is involved is probably the main reason. This could perhaps be addressed, but with more "complicated" machinery, such as indexing with masks as in C++ std::valarray. $\endgroup$
    – Pablo H
    Commented Aug 23, 2023 at 15:04
5
$\begingroup$

It privileges one form of bit access over others

Accessing a word as a bit vector can be useful in some circumstances, but even more useful is the ability to pack and unpack general bit fields. Things like the IPv4 header.

IPv4 header fields

Expressive and precise bit field manipulation goes back at least to BLISS (see section 1, "Storage"). Erlang also has native support for bit fields.

C and C++ also have bit fields, but their semantics is not specified; there is no requirement for an implementation to actually pack bit fields.

$\endgroup$
3
  • 4
    $\begingroup$ This would be a non-issue with ranged indexing: 6[1:3] could be 3. $\endgroup$
    – Bbrk24
    Commented May 18, 2023 at 1:29
  • $\begingroup$ True, but there wasn't an example of that in the question. $\endgroup$
    – Pseudonym
    Commented May 18, 2023 at 1:30
  • $\begingroup$ It also raises the question of how you would implement assignment to an array slice. I hope your CPU has a pdep instruction, or this could get inefficient. $\endgroup$
    – Pseudonym
    Commented May 19, 2023 at 1:31
2
$\begingroup$

I do not know of any languages that support this idea

Let's fix that :-)

Vyxal is a code golf language which allows indexing into an integer as if it was a collection of digits:

1010 2i

This puts our integer 1010 and the 0-based, from-the-left index 2 on the stack, then indexes the former with the latter. Try it Online!

The same goes for Thunno 2 and 05AB1E.

$\endgroup$
2
  • $\begingroup$ Same in Thunno 2 and 05AB1E $\endgroup$
    – The Thonnu
    Commented May 18, 2023 at 7:32
  • $\begingroup$ @TheThonnu Thanks. Added. $\endgroup$
    – Adám
    Commented May 18, 2023 at 8:03
2
$\begingroup$

As integers (certainly positive integers) are representable in base 2 as binary numbers, and a binary internal representation is also most common, integers arguably are bit (Boolean) arrays. So the idea is not farfetched, nor can I see any disadvantages; accessing individual bits, slices and other array operations translate very easily into other types of operations, to the point you might call it syntactical sugar. It might be practical to distinguish between an integer value, and its array interpretation, this could be done in many ways - typecasting, a function, an operator; just for fun I will use the feminine ordinal indicator "ª" as a postfix operator for this in this answer. So for an integer i, iª is a bit array view of i. By bit, btw, I mean the integers 0 and 1. So 1ª = (1). As for 0, it could be 0ª = (0), or maybe 0ª = (). I don't know which one would be most practical, probably the first, although the second has some appeal as being perhaps most "correct".

A bit of care needs to be taken with negative integers, though. The common 2-complement representation might mess things up a bit (!), especially with slices. For natural numbers i, there is a nice equality: length(iª) = ceil(log2(i+1)). But (-1)ª would be (...,1,1,1,1). So maybe it is better to restrict iª to i ≥ 0.

In 2-complement, -i = (~i)+1, where ~ is complement or bitwise negation as known in C. Now, having bit arrays, it would make sense to move bitwise operations from the integer domain over to the bit array domain. (In the past, I think languages like PL/1 and Algol 68 did this too.) Which is probably a good thing, as I think in for example C, bitwise operations have caused various errors. Having both signed and unsigned integers of various lengths, and automatic promotion among them, makes bitwise operations in C more complicated than one would have guessed.

Using bit arrays that always represent natural numbers makes this a lot simpler. So this would be a strong advantage of this idea, I'd say!

But why restrict array-fication to binary? Outside the world of computing, we usually use base 10. iºb could be used for the general case of making an array using base b, iª = iº2.

Converting bit arrays, or other digit arrays, to integers is also straightforward. Just use the arrays as vectors, and you can go from bit array a = iª back to i just by the scalar product i = a·b, where b = λn:2ⁿ, or (1, 2, 4, 8, 16, ...)

Fun exercise: How about iº1?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .