[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

Change by STINNER Victor :


--
nosy:  -vstinner

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[pmp-p]

Change by pmp-p :


--
nosy: +pmpp

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Raymond Hettinger]

Raymond Hettinger  added the comment:

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

--
resolution:  -> rejected
stage: needs patch -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Georg Brandl]

Change by Georg Brandl :


--
nosy:  -georg.brandl

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

STINNER Victor  added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Niklas Fiekas]

Change by Niklas Fiekas :


--
nosy: +niklasf

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Nitish]

Change by Nitish :


--
nosy: +nitishch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tamás Bajusz]

Change by Tamás Bajusz :


--
nosy: +gbtami

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

Any update on this?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Steven D'Aprano]

Changes by Steven D'Aprano steve+pyt...@pearwood.info:


--
nosy: +steven.daprano

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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?

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

STINNER Victor added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

Changes by STINNER Victor victor.stin...@gmail.com:


--
Removed message: http://bugs.python.org/msg228173

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

STINNER Victor added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

STINNER Victor added the comment:

I don't know what 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).

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Antoine Pitrou]

Antoine Pitrou added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

STINNER Victor added the comment:

 Sequences are not lists.

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Antoine Pitrou]

Antoine Pitrou added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Georg Brandl]

Georg Brandl added the comment:

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.

--
nosy: +georg.brandl

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

@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)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Georg Brandl]

Georg Brandl added the comment:

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 :)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Mark Dickinson]

Mark Dickinson added the comment:

 - 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`.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[HCT]

HCT added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

STINNER Victor added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

STINNER Victor added the comment:

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

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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?

--
status: open - pending

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Antoine Pitrou]

Antoine Pitrou added the comment:

@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...

--
status: pending - open

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Martin Panter]

Changes by Martin Panter vadmium...@gmail.com:


--
nosy: +vadmium

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[HCT]

HCT added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Josh Rosenberg]

Changes by Josh Rosenberg shadowran...@gmail.com:


--
nosy: +ShadowRanger

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Meador Inge]

Changes by Meador Inge mead...@gmail.com:


--
nosy: +meador.inge

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Antoine Pitrou]

Antoine Pitrou added the comment:

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.

--
nosy: +pitrou

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tim Peters]

Tim Peters added the comment:

@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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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 = bitslefthishift ? bitsleft : hishift;
mask = ((digit)1  step) - 1;
z-ob_digit[i] = (v-ob_digit[j]  loshift)  mask;
bitsleft -= step;

if (j+1  size) {
step = bitsleftloshift ? 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).);

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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 (npos)  ((1  width) - 1)
for n in [123, 777, (135)|(130)|(125)]:
for i in range(50):
for j in range(20):
self.assertEqual(n.bits_at(i, j), bits_at(n, i, j))

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tim Peters]

Tim Peters added the comment:

@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 
;-)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[HCT]

HCT added the comment:

 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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tim Peters]

Tim Peters added the comment:

@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 ;-)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tim Peters]

Tim Peters added the comment:

@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 ;-)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tim Peters]

Tim Peters added the comment:

@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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tim Peters]

Tim Peters added the comment:

[@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 ;-)

--
stage:  - needs patch

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Mark Dickinson]

Mark Dickinson added the comment:

 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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[STINNER Victor]

Changes by STINNER Victor victor.stin...@gmail.com:


--
nosy: +haypo

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

anon added the comment:

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.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Mark Dickinson]

Mark Dickinson added the comment:

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!

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[anon]

New submission from anon:

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 (in)1

However in computing the intermediate result in 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 (in)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.

--
messages: 205421
nosy: anon
priority: normal
severity: normal
status: open
title: int.bit_at(n) - Accessing a single bit in O(1)
type: enhancement
versions: Python 3.5

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Antoine Pitrou]

Changes by Antoine Pitrou pit...@free.fr:


--
nosy: +mark.dickinson, tim.peters

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tim Peters]

Tim Peters added the comment:

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!

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Raymond Hettinger]

Raymond Hettinger added the comment:

 I've often wanted this too!

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

--
nosy: +rhettinger

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Tim Peters]

Tim Peters added the comment:

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/

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[HCT]

HCT added the comment:

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

--
nosy: +hct

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue19915] int.bit_at(n) - Accessing a single bit in O(1)

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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

--
nosy: +serhiy.storchaka

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com