For many numeric algorithms it's useful to be able to read individual bits at a location in an integer. Currently there is no efficient way to do this. The following function is the closest to this:

def bit_at(i, n): return (i>>n)&1

However in computing the intermediate result i>>n we must spend O(b-n) time at least (where b is n.bit_length()). It should be possible to read bits in O(1) time. Adding int.bit_at(n) would complement int.bit_length().

I would suggest making the semantics of i.bit_at(n) the same as (i>>n)&1. Although the exact meaning when i is negative should be considered.

Real world uses of bit_at include binary exponentiation and bit counting algorithms.

I'd rather see `i.bits_at(pos, width=1)`, to act like

(i >> pos) & ((1 << width) - 1)

That is, extract the `width` consecutive bits at positions 2**pos through 2**(pos + width - 1) inclusive.

Because Python ints maintain the illusion of having an infinite number of sign bits, I don't think negative `pos` (or `width`) can be assigned a sensible meaning.  Python ints only have "one end".

And, yup, I've often wanted this too!

> I've often wanted this too!

My want has been for a bitarray (parallel to the existing bytearray type).

Raymond, I expect they have overlapping - but not identical - audiences.  There's seem to be a quite capable bitarray extension here:

https://pypi.python.org/pypi/bitarray/

or just allow slicing of int. otherwise function call overhead may defeat the speed up of such function.

> My want has been for a bitarray (parallel to the existing bytearray type).

Or bitview (parallel to the existing memoryview type). It should work as with int's and bytes object's (immutable), so with bytearray (mutable).

I like the i.bits_at(pos, width=1) suggestion. Unless slicing is chosen instead this seems the most future-proof idea.

I think slicing semantically "seems wrong" but it might be more elegant. It might also make catching errors harder (in the case where an int is sent to a function that does slicing and now won't fail with a TypeError).

> I'd rather see `i.bits_at(pos, width=1)`

Me too.  Extracting sign, exponent and significand fields from the binary representation of a float is at least one thing I'd use this for.

I didn't really consider floats. bit_length() is only provided to ints for example.

I think a better solution to pick apart floats would be a function similar to math.frexp, if it isn't already sufficient. float.bits_at(pos, width) seems a worse solution because the position of each bit would be arbitrary. But I have no major objection against it being extended to floats.

Sorry, I wasn't clear.  I'm not interested in applying this to floats themselves; I'm interested in applying it to the bit pattern of a float when that bit pattern is treated as an integer.

> But I have no major objection against it being extended to floats.

I do!

Then I think we're in agreement with regards to bits_at. :) What should happen next?

> Extracting sign, exponent and significand fields from the binary
> representation of a float is at least one thing I'd use this for.

You don't need special function for bit operations. Float values are short (32 
or 64 bits) and any bit operations are O(1). Special function for bit 
extracting (or modifying) is needed when you process many hundreds or 
thousands of bits. In any case >> and & for 64-bit values are faster than 
method call.

@serhiy, Mark certainly knows the proposed addition isn't _needed_ to pick apart 64-bit integers.  It's an issue there of clarity, not O() behavior.  For example, `i.bits_at(0, 52)` to get at a double's mantissa requires no thought at all to write or to read later; bit-level gibberish like

i & ~((~0) << 52)

or

i & ((1 << 52) - 1)

or ... is painful to write and to read.

[@anon]
> What should happen next?

1. Write docs.
2. Write a test suite and test a Python implementation.
3. Write C code, and reuse the test suite to test that.
4. Attach a patch for all of that to this issue (although a
   Python implementation is no longer interesting at this point).
5. After that's all ready, seek consensus on Python-Dev.

The good news:  this is too minor to require a PEP ;-)

> For example, `i.bits_at(0, 52)` to get at a double's mantissa requires no thought at all to write or to read later; bit-level gibberish like

I agree that special function or method looks more clear. But I suppose that in many cases the performance does matter. And function call has larger overhead in current Python.

Should the signature be int.bits_at(start_bit, width) or int.bits_at(start_bit, end_bit+1) ? The latter would look more lire range() and slicing.

Antoine, I don't suggest that since you commonly want a fixed number of bits.

@pitrou, I think usability is a lot more valuable than cross-feature "formal consistency" here.  I've been extracting bit fields for decades, and always think of them in terms of "least-significant bit and number of bits".  Perhaps the underlying difference is that nobody ever thinks of bit positions as being _between_ bits - instead we always think of "bit i" as being the bit with binary value 2**i.  It's more of a math concept than an indexing concept.

For a bit _array_ I'd agree slicing semantics would make more sense.  But Python ints have infinite width, and "index 0" is at the rightmost position (not the leftmost position - there is no leftmost position).

I'd also like to avoid the nuisance of having to implement all the goofy slicing possibilities, like non-unit strides and negative strides.  Not that they're "goofy" in general - they're goofy in the context of extracting bits from an integer.  Again a bit array is a different kind of beast.

Here is my very rough attempt at bits_at. It doesn't handle negative numbers and I am not sure it's safe. This was my first time using Python internals.

Objects/longobject.c:



static PyObject *
long_bits_at(PyLongObject *v, PyObject *args)
{
    PyLongObject *z = NULL;
    
    if(Py_SIZE(v) < 0)
    {
        PyLongObject *a1, *a2;
        Py_RETURN_NOTIMPLEMENTED;
        a1 = (PyLongObject *)long_invert(v);
        //Handle the case where a1 == NULL
        a2 = (PyLongObject *)long_bits_at(a1, args);
        //Handle the case where a2 == NULL
        Py_DECREF(a1);
        Py_DECREF(a2);
        //return a2 ^ ((1 << width) - 1)
    }
    else
    {
        PyObject *at_ = NULL;
        PyObject *width_ = NULL;
        ssize_t at, width, i, j, bitsleft, step;
        ssize_t wordshift, size, newsize, loshift, hishift;
        digit mask;
        
        if (!PyArg_UnpackTuple(args, "bits_at", 1, 2, &at_, &width_))
            return NULL;
        
        at = PyLong_AsSsize_t((PyObject *)at_);
        if (at == -1L && PyErr_Occurred())
            return NULL;
        if (at < 0) {
            PyErr_SetString(PyExc_ValueError, "negative index");
            return NULL;
        }
        
        if (width_ == NULL)
            width = 1;
        else {
            width = PyLong_AsSsize_t((PyObject *)width_);
            if (width == -1L && PyErr_Occurred())
                return NULL;
            if (width < 0) {
                PyErr_SetString(PyExc_ValueError, "negative bit count");
                return NULL;
            }
        }
        
        wordshift = at / PyLong_SHIFT;
        size = ABS(Py_SIZE(v));
        newsize = (width-1) / PyLong_SHIFT + 1;
        if (newsize > size-wordshift)
            newsize = size-wordshift;
        if (newsize <= 0)
            return PyLong_FromLong(0L);
        
        loshift = at % PyLong_SHIFT;
        hishift = PyLong_SHIFT - loshift;
        bitsleft = width;
        z = _PyLong_New(newsize);
        if (z == NULL)
            return NULL;
        
        for (i = 0, j = wordshift; i < newsize; i++, j++) {
            step = bitsleft<hishift ? bitsleft : hishift;
            mask = ((digit)1 << step) - 1;
            z->ob_digit[i] = (v->ob_digit[j] >> loshift) & mask;
            bitsleft -= step;
            
            if (j+1 < size) {
                step = bitsleft<loshift ? bitsleft : loshift;
                mask = ((digit)1 << step) - 1;
                z->ob_digit[i] |= ((v->ob_digit[j+1] & mask) << hishift);
                bitsleft -= step;
            }
        }
        z = long_normalize(z);
    }
    
    return (PyObject *)z;
}

PyDoc_STRVAR(long_bits_at_doc,
"int.bits_at(pos, width=1) -> int\n\
\n\
Equivalent to (int >> pos) & ((1 << width) - 1).");

Here are some inadequate tests to add to Lib/test/test_long.py



    def test_bits_at(self):
        def bits_at(n, pos, width=1):
            return (n>>pos) & ((1 << width) - 1)
        for n in [123, 7777777, (1<<35)|(1<<30)|(1<<25)]:
            for i in range(50):
                for j in range(20):
                    self.assertEqual(n.bits_at(i, j), bits_at(n, i, j))

Both segments of code are public domain. It would be great if someone could review them, improve them and produce a proper patch. I didn't handle the negative case, which I hope someone else can add.

Some of the code may be under Python's license though. So I should clarify that only MY parts of the two samples of code are public domain.

@anon, sorry, but we can't accept any code from you unless you have a real name and fill out a contributor agreement:

   http://www.python.org/psf/contrib/

This is legal crud, and I'm not a lawyer.  But, in particular, lawyers have told me that - in the USA - an individual cannot meaningfully put anything in "the public domain".  That's what I used to do - until a lawyer strongly advised me to stop that and use an actual license.

In any case, it's most likely that Python developers won't even look at your code in the absence of a contributor agreement.  If we did, the slight chance of Bad Consequences (e.g., someone we only knew as "anon" sues us for stealing their ideas) outweighs the slight benefit we might get from stealing your ideas ;-)

> I think slicing semantically "seems wrong" but it might be more elegant. It might also make catching errors harder (in the case where an int is sent to a function that does slicing and now won't fail with a TypeError).

not sure what's semantically "seems wrong" with it. not sure why TypeError or any other error catching should come into play for this.

calling a function is way more expensive than doing bit shift and/or AND operation. as a function, you've only hide your code into Python binaries at the expense of performance

@HCT, see http://bugs.python.org/issue19915#msg205713 for what's "semantically wrong".  Ints are not arrays - slicing is unnatural.

The point about error checking is that if this were supported via slicing notation, then the _helpful_ exceptions of the form, e.g.,

    TypeError: 'int' object has no attribute '__getitem__'

would no longer occur for code like

    myarray[1:12]

where `myarray` is mistakenly bound to an integer.  We always lose something when assigning a meaning to an operation that formerly raised an exception.

About:

> calling a function is way more expensive than doing
> bit shift and/or AND operation

read the very first message in this issue.  There is no upper bound on how expensive bit shifts and logical operations can be on Python integers:  they can take time proportional to the number of bits.  But a function to extract a bit can be written internally to require small constant time, independent of the number of bits in the integer.  At least that's true for CPython ints >= 0; it may well take longer for negative CPython ints in some cases.

If speed on small ints is your primary concern, by all means continue to fiddle the bits by hand ;-)

Tim, I'm sorry to hear you can't accept my patch. I am afraid I want to stay anonymous.

You have my word that I wrote the two code segments above (based on code already in CPython) and that I put them in the public domain. But I appreciate that the word of `anon` may be worth nothing to you. For what it is worth I could have used a fake name anyway.

If you can't accept them, may I request someone else implement the proposal? This may be for the best anyway since I am unfamiliar with CPython internals.

@anon, not to worry:  someone else will write the code.  Maybe even me ;-)

BTW, "public domain" is not a license.  It's the absence of a license.  Our lawyers would not accept that even if you had a real name ;-)

Thank you! I will try to help in ways that I can such as testing.

then I guess it's either a new function to int or a new type of int for this type of operations. similar to bytearray/ctypes and memoryview

From what I can tell it's fairly easy to just add bits_at to int.

Indeed something like a mutable int type might be nice but that's really outside the scope of this. And adding bits_at to int would still be desirable anyway.

I think the case where i is negative can be handled by

bits_at(i, pos, width) = bits_at(~i, pos, width) ^ ((1 << width) - 1)

I noticed feature freeze for 3.5 is in May 2015 which is actually only 7-8 months. It'd be really awesome if this feature could make it. Is there anyone who can get this into 3.5?

@anon: if there is a patch, any committer here can get it into 3.5. You'll recognize them as they have a nice Python logo next to their usernames ;-) If you want to try your hand at a patch, see https://docs.python.org/devguide/

By the way, I think it would be extra cool to implement this as a ".bits" pseudo-sequence, e.g.

>>> x = 255
>>> x.bits[0]
1
>>> x.bits[1:3]
7

However, it might not be so easy to do it in C...

Above I included a first attempt however I don't think my code is good and I couldn't figure out the case for negative integers. There's some discussion above about its inclusion.

I like your x.bits suggestion actually, assuming x.bits returns an IntBitsView object without copying x in any way. That would suggest that we could do len(x.bits) and probably depreciate x.bit_length(). Any consensus on this?

I don't like the idea of the array-view int.bits[a:b]: it's harder to implement and the proposed behaviour is different than a list. Example:

>>> x=list("abcdef")
>>> x[2]
'c'
>>> x[2:4]
['c', 'd']

x[2:4] returns a subset of the list, so a new list. It doesn't return "cd". I would expect int.bits[a:b] to return a list of integers in range 0..1.

I prefer int.bits(bit, nbits=1), because it's more obvious that it returns an integer (and not a list) for nbits > 1.

I don't know where "at" of "bits_at()" comes from. It's rarely used in Python:

Lib/asynchat.py:def find_prefix_at_end(haystack, needle):
Lib/asyncio/test_utils.py:    def call_at(self, when, callback, *args):
Lib/asyncio/base_events.py:    def call_at(self, when, callback, *args):
Lib/asyncio/events.py:    def call_at(self, when, callback, *args):
Lib/ctypes/__init__.py:def string_at(ptr, size=-1):
Lib/ctypes/__init__.py:    def wstring_at(ptr, size=-1):
Lib/idlelib/EditorWindow.py:    def move_at_edge_if_selection(self, edge_index):
Lib/idlelib/EditorWindow.py:        def move_at_edge(event):

I prefer just "bits": int.bits(bit, nbits=1).

> I don't like the idea of the array-view int.bits[a:b]: it's harder to 
> implement and the proposed behaviour is different than a list.

Sequences are not lists.

> Sequences are not lists.

Are there other object types for which obj[a:b] does not return a new sequence?

> Are there other object types for which obj[a:b] does not return a new sequence?

That's a good question :-) I can't think of any.

Pros for x.bits being a view:
- seems slightly cleaner (in my opinion)
- can potentially abstract slicing bits without copying the underlying int (e.g. x.bits[2:][4:])

Pros for x.bits being a function:
- Victor's point
- no need to depreciate x.bit_length
- no need to create a View object and probably faster?
- easier to implement

Giving it more thought: to get the int we'd need something like int(x.bits[2:][4:]) which seems quite annoying for the general case of int(x.bits[0:52]). So actually I'm not sure that views would add any more abstraction for their extra complexity without becoming a bit unwieldy.

While everybody is throwing ideas around: what about the opposite?

If extracting bit ranges from bitfields is common enough to warrant this addition, updating bitfields with a bit range is probably just as common.

This'd need something like

i.with_bits(value, pos, width=1)

No preference if it should raise an exception if value is wider than "width".

@Georg: I don't think it would be as common but do agree it'd be useful.

I think it can be implemented "efficiently" in pure Python currently.

def with_bits(i, value, pos, width=1):
  width = min(width, value.bit_length())
  mask = ((1 << width) - 1)
  v = value & mask
  i = i & ~(mask << pos)
  return i | (v << pos)

This is why I proposed it (and also because I had to write that quite a few times already).  Efficient maybe, but very hard to get right on the first try :)

> - no need to depreciate x.bit_length

No matter how this issue progresses, deprecating `int.bit_length` should be out of the question.  Much better to have (somewhat) duplicated functionality than to gratuitously break code that's already using `int.bit_length`.

All I had meant by depreciating was changing the x.bit_length documentation to point towards len(x.bits).

maybe someone should start a PEP with all of the thoughts organized?

Yes, it's a good idea to start a PEP to modify most important builtin
types like int and str.

That's something that a Python comitter would have to do isn't it?

> That's something that a Python comitter would have to do isn't it?

Python is open. Anyone can propose an enhancement (a PEP).

Since I'm not familiar with the process I'd request someone creates the PEP. But if really necessary I can try.

I just really want to see this in Python 3.5 - it's really essential to a number of scientific methods. I know several open source projects that would benefit from it.

I'm struggling to get time for this. I hope someone else can take responsibility. Sorry :-(

Any update on this?

> Any update on this?

Since nobody proposed a PEP, no, there is no progress on this issue.

I suggest to close it because of the lack of interest to move on on this issue.

If someone does develop an interest in this, feel free to re-open. 
 
Personally, I'm sure that I would use int.bit_at() but only once every five years ;-)   Also, it would be only half a solution unless accompanied by int.replace_bit_at().