[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon
report at bugs.python.org
Mon Dec 9 18:07:55 CET 2013
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 = 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).");
----------
_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue19915>
_______________________________________
More information about the Python-bugs-list
mailing list