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?

  • $\begingroup$ I suggest looking at union for C++. You can write a union of a byte like char c and then write another type of bits b1:1 and so on. I am not sure about the speed and other things. And this is more programming question, not computer science which deals with algorithms and not language capabilities. $\endgroup$ – Eugene Dec 29 '16 at 8:23
  • $\begingroup$ Yours is a bad title; please pick one that more accurately describes your question. $\endgroup$ – Raphael Dec 29 '16 at 12:45
  • $\begingroup$ In its current form, this question is too broad: you are asking if something like this exists anywhere. Are you really asking for an algorithm? If so, on which model? $\endgroup$ – Raphael Dec 29 '16 at 12:47
  • $\begingroup$ I was writing an algorithm. Then I realised my algorithm would be faster if I could access a number bit by bit, invert the bit, etc. If you're curious, I'm trying to develop arithmetic algorithms that are hopefully faster than some of the existing ones. $\endgroup$ – Tobi Alafin Dec 29 '16 at 12:50
  • $\begingroup$ @TobiAlafin On most real machines, any "bit index" operation is ultimately going to be implemented by shifting and masking. However, both practically and theoretically, you should be going the opposite direction. You should be exploiting the word-level (aka bit-level) parallelism to perform many operations at once, word at a time. $\endgroup$ – Derek Elkins left SE Dec 30 '16 at 2:28

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)$.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.