Bit operations; Treating a number like an array

Question

Are there features in programming languages that allow you to directly access the $k^{th}$ bit of a number. Treating it like an integer.

I'm not talking of using bit shifting to retrieve a number. But directly access the bit at index $i$ of a number as if it were an array.

I'm looking at this feature to replace shifting to write an algorithm I was working on. If it isn't faster than shifting, then such a feature would be pointless.

I didn't ask this on stack overflow as this isn't about a specific programming language, but about whether programming languages in general have this feature.

Also are there language features for inverting the bits(a specific bit or as many as needed) of a number?

Answer 1

The answer depends on the programming language and, to some extent, on the CPU. For any practical purpose, though, extracting the $k$th bit is an $O(1)$ operation even on a "big integer" stored on several machine words, since in order to extract the $k$th bit, you can use the following algorithm:

1. Determine which word the $k$th bit is in, and which bit in the word.

2. Extract the appropriate bit from the appropriate word.

In practice it is a reasonable assumption to make that indices of bits fit into a machine word, and so all of these operations are $O(1)$.

Answer 2

Felix has a very much more general capability.

var x : 3 * 2 * 5 = (case 2 of 3, case 1 of 2, case 4 of 5);
println$ x;
var y = x :>> int;
println$ y;
var z : 2 ^ 5 = true, true, true, false, false;
println$ z, z.1;
var a = z :>> int;
println$ a;

Basically there is a concept called a compact linear type. Unit (1) is compact linear, any finite sum, product, or exponential of a compact linear type is compact linear. For example

typedef bool = 2;

is compact linear.

Values of compact linear types have a natural bijection to integers, represented above by using the type coercion operator :>>. Felix represents small compact linear types which are defined as 64 bit unsigned integers, or non-compact arrays with compact linear indices.

Felix supports projections and assignments to any component of a compact linear type individually. The primary intent is for array indices because this then gives you polyadic (rank independent) array access.

For example you can coerce between double^10^20 which is a linear array dimension 20 of linear arrays dimenion 10 to a matrix double^(10*20) which has takes a tuple index to double^200 which is a single linear array of 200 values. The arrays here are not compact linear but the exponents are.

The compiler optimises these operations to ones using addition, multiplication, division and modulo of constants, and expects the underlying C compiler to convert these to bitshifts for powers of two.

The operations are generalisations of C bitfields, which only work for powers of 2. Compact linear types are fully general, up to the 64 bit restriction. However Felix does not provide pointers to components of compact linear types although you can assign to them.