8000 ENH: Added countbits (popcount) · ganesh-k13/numpy@23ee8e8 · GitHub
[go: up one dir, main page]
Skip to content

Commit 23ee8e8

Browse files
ganesh-k13ganesh-k13
committed
ENH: Added countbits (popcount)
ENH, DOC: Added countbits (popcount) ENH: Popcount implementation ENH: Add popcount to umath ENH: Added countbits (popcount) to umath `__all__` ENH: Refined popcount logic DOC: Added `bit_count` Co-authored-by: Eric Wieser <wieser.eric@gmail.com> MAINT: Renamed `countbits` to `bit_count` MAINT: Fixed 4 1s magic number DOC: Added `popcount` to docstring ENH: Added bit_count annotations ENH: Added GNU/CLANG popcount DOC: Added `popcount` language example ENH, BUG: Moved `bitcount` to npy_math.h as `popcount` | Fixed final right shift ENH: Enable `popcount` for signed TST: Tests for `bit_count` BUG, DOC: (BUG) Added missing typecast causing an unwanted upcast (DOC) Added more details on `popcount` implementation MAINT, BUG: (MAINT) Refined `popcount` TC to use typecode (BUG) Fixed ufunc.ntypes to include signed ints ENH: Added windows builtin support ENH: Added `popcount` implementation for big python ints natively [1/2] `popcount` object loop changes ENH: Object loop for `bit_count` [2/2] `popcount` object loop changes TST: Refined `bit_count` tests and added object type ENH: Added `bit_count` to `np.int*` DOC: Added `np.bit_count` (numpy#19355) MAINT: Various linting and minor fixes: 1. Fixed passing all args to _internals umath bitcount. Note: We use kwargs here that might hinder performance 2. Fixed linting errors. 3. Improved verbosity of logs 4. Made a generic TO_BITS_LEN macro to accomdate more length based functions in future BENCH: Added bit_count (popcount) MAINT: Style nits | Added signed case DOC, MAINT: Improved example ENH: Added annotations for bit_count TST: Added annotations tests for bit_count MAINT: Fixed linting errors MAINT: Moved Magic constants to npy_math_internal MAINT: Remove python implementation | Added 3.10 check to tests DOC: Added abs value usage to doc MAINT: Resolved merge conflicts
1 parent e42c950 commit 23ee8e8

File tree

17 files changed

+179
-7
lines changed

17 files changed

+179
-7
lines changed

‎benchmarks/benchmarks/bench_ufunc.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44

55

66
ufuncs = ['abs', 'absolute', 'add', 'arccos', 'arccosh', 'arcsin', 'arcsinh',
7-
'arctan', 'arctan2', 'arctanh', 'bitwise_and', 'bitwise_not',
7+
'arctan', 'arctan2', 'arctanh', 'bit_count', 'bitwise_and', 'bitwise_not',
88
'bitwise_or', 'bitwise_xor', 'cbrt', 'ceil', 'conj', 'conjugate',
99
'copysign', 'cos', 'cosh', 'deg2rad', 'degrees', 'divide', 'divmod',
1010
'equal', 'exp', 'exp2', 'expm1', 'fabs', 'float_power', 'floor',

‎doc/release/upcoming_changes/19355.new_feature.rst

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
`np.bit_count` to compute the number of 1-bits in an integer
2+
------------------------------------------------------------
3+
4+
This new function counts the number of 1-bits in a number.
5+
These work on all the numpy integer types, as well as the
6+
builtin arbitrary-precision `Decimal` and `long` types.
7+
8+
.. code-block:: python
9+
10+
>>> a = np.array([2**i - 1 for i in range(16)])
11+
>>> np.bit_count(a)
12+
array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])

‎doc/source/reference/routines.math.rst

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -182,3 +182,5 @@ Miscellaneous
182182
real_if_close
183183

184184
interp
185+
186+
bit_count

‎numpy/__init__.pyi

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2511,6 +2511,17 @@ class ndarray(_ArrayOrScalarCommon, Generic[_ShapeType, _DType_co]):
25112511
def __dlpack__(self: NDArray[number[Any]], *, stream: None = ...) -> _PyCapsule: ...
25122512
def __dlpack_device__(self) -> tuple[int, L[0]]: ...
25132513

2514+
def bit_count(
2515+
self,
2516+
out: None | NDArray[Any] = ...,
2517+
*,
2518+
where: _ArrayLikeBool_co = ...,
2519+
casting: _CastingKind = ...,
2520+
order: _OrderKACF = ...,
2521+
dtype: DTypeLike = ...,
2522+
subok: bool = ...,
2523+
) -> NDArray[Any]: ...
2524+
25142525
# Keep `dtype` at the bottom to avoid name conflicts with `np.dtype`
25152526
@property
25162527
def dtype(self) -> _DType_co: ...
@@ -2654,6 +2665,17 @@ class generic(_ArrayOrScalarCommon):
26542665
self: _ScalarType, *shape: SupportsIndex, order: _OrderACF = ...
26552666
) -> ndarray[Any, _dtype[_ScalarType]]: ...
26562667

2668+
def bit_count(
2669+
self,
2670+
out: None | NDArray[Any] = ...,
2671+
*,
2672+
where: _ArrayLikeBool_co = ...,
2673+
casting: _CastingKind = ...,
2674+
order: _OrderKACF = ...,
2675+
dtype: DTypeLike = ...,
2676+
subok: bool = ...,
2677+
) -> Any: ...
2678+
26572679
def squeeze(
26582680
self: _ScalarType, axis: None | L[0] | tuple[()] = ...
26592681
) -> _ScalarType: ...
@@ -3217,6 +3239,7 @@ arcsinh: _UFunc_Nin1_Nout1[L['arcsinh'], L[8], None]
32173239
arctan2: _UFunc_Nin2_Nout1[L['arctan2'], L[5], None]
32183240
arctan: _UFunc_Nin1_Nout1[L['arctan'], L[8], None]
32193241
arctanh: _UFunc_Nin1_Nout1[L['arctanh'], L[8], None]
3242+
bit_count: _UFunc_Nin1_Nout1[L['bit_count'], L[11], None]
32203243
bitwise_and: _UFunc_Nin2_Nout1[L['bitwise_and'], L[12], L[-1]]
32213244
bitwise_not: _UFunc_Nin1_Nout1[L['invert'], L[12], None]
32223245
bitwise_or: _UFunc_Nin2_Nout1[L['bitwise_or'], L[12], L[0]]

‎numpy/core/_methods.py

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
umr_minimum = um.minimum.reduce
2121
umr_sum = um.add.reduce
2222
umr_prod = um.multiply.reduce
23+
umr_bit_count = um.bit_count
2324
umr_any = um.logical_or.reduce
2425
umr_all = um.logical_and.reduce
2526

@@ -232,3 +233,8 @@ def _dump(self, file, protocol=2):
232233

233234
def _dumps(self, protocol=2):
234235
return pickle.dumps(self, protocol=protocol)
236+
237+
def _bit_count(a, out=None, *, where=True, casting='same_kind',
238+
order='K', dtype=None, subok=True):
239+
return umr_bit_count(a, out, where=where, casting=casting,
240+
order=order, dtype=dtype, subok=subok)

‎numpy/core/code_generators/generate_umath.py

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1099,6 +1099,13 @@ def english_upper(s):
10991099
TD(ints),
11001100
TD('O', f='npy_ObjectLCM'),
11011101
),
1102+
'bit_count':
1103+
Ufunc(1, 1, None,
1104+
docstrings.get('numpy.core.umath.bit_count'),
1105+
None,
1106+
TD(ints),
1107+
TD('O', f='npy_ObjectPopCount'),
1108+
),
11021109
'matmul' :
11031110
Ufunc(2, 1, None,
11041111
docstrings.get('numpy.core.umath.matmul'),

‎numpy/core/code_generators/ufunc_docstrings.py

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4214,3 +4214,37 @@ def add_newdoc(place, name, doc):
42144214
array([ 0, 20, 20, 60, 20, 20])
42154215
42164216
""")
4217+
4218+
add_newdoc('numpy.core.umath', 'bit_count',
4219+
"""
4220+
Computes the number of 1-bits in the absolute value of ``x``.
4221+
Analogous to the builtin `int.bit_count` or ``popcount`` in C++.
4222+
4223+
Parameters
4224+
----------
4225+
x : array_like, unsigned int
4226+
Input array.
4227+
$PARAMS
4228+
4229+
Returns
4230+
-------
4231+
y : ndarray
4232+
The corresponding number of 1-bits in the input.
4233+
$OUT_SCALAR_1
4234+
4235+
References
4236+
----------
4237+
.. [1] https://stackoverflow.com/a/109025/5671364
4238+
4239+
.. [2] Wikipedia, "Hamming weight",
4240+
https://en.wikipedia.org/wiki/Hamming_weight
4241+
4242+
Examples
4243+
--------
4244+
>>> np.bit_count(1023)
4245+
10
4246+
>>> a = np.array([2**i - 1 for i in range(16)])
4247+
>>> np.bit_count(a)
4248+
array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
4249+
4250+
""")

‎numpy/core/src/multiarray/methods.c

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -355,6 +355,12 @@ array_ptp(PyArrayObject *self, PyObject *args, PyObject *kwds)
355355
NPY_FORWARD_NDARRAY_METHOD("_ptp");
356356
}
357357

358+
static PyObject *
359+
array_bit_count(PyArrayObject *self, PyObject *args, PyObject *kwds)
360+
{
361+
NPY_FORWARD_NDARRAY_METHOD("_bit_count");
362+
}
363+
358364

359365
static PyObject *
360366
array_swapaxes(PyArrayObject *self, PyObject *args)
@@ -3082,9 +3088,11 @@ NPY_NO_EXPORT PyMethodDef array_methods[] = {
30823088
{"__dlpack__",
30833089
(PyCFunction)array_dlpack,
30843090
METH_FASTCALL | METH_KEYWORDS, NULL},
3085-
30863091
{"__dlpack_device__",
30873092
(PyCFunction)array_dlpack_device,
30883093
METH_NOARGS, NULL},
3094+
{"bit_count",
3095+
(PyCFunction)array_bit_count,
3096+
METH_VARARGS | METH_KEYWORDS, NULL},
30893097
{NULL, NULL, 0, NULL} /* sentinel */
30903098
};

‎numpy/core/src/multiarray/scalartypes.c.src

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1574,7 +1574,7 @@ gentype_byteswap(PyObject *self, PyObject *args, PyObject *kwds)
15741574
* std, var, sum, cumsum, prod, cumprod, compress, sort, argsort,
15751575
* round, argmax, argmin, max, min, ptp, any, all, astype, resize,
15761576
* reshape, choose, tostring, tobytes, copy, searchsorted, view,
1577-
* flatten, ravel, squeeze#
1577+
* flatten, ravel, squeeze, bit_count#
15781578
*/
15791579
static PyObject *
15801580
gentype_@name@(PyObject *self, PyObject *args, PyObject *kwds)
@@ -2185,6 +2185,9 @@ static PyMethodDef gentype_methods[] = {
21852185
{"sum",
21862186
(PyCFunction)gentype_sum,
21872187
METH_VARARGS | METH_KEYWORDS, NULL},
2188+
{"bit_count",
2189+
(PyCFunction)gentype_bit_count,
2190+
METH_VARARGS | METH_KEYWORDS, NULL},
21882191
{"cumsum",
21892192
(PyCFunction)gentype_cumsum,
21902193
METH_VARARGS | METH_KEYWORDS, NULL},

‎numpy/core/src/npymath/npy_math_internal.h.src

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -678,7 +678,6 @@ npy_rshift@u@@c@(npy_@u@@type@ a, npy_@u@@type@ b)
678678
/**end repeat1**/
679679
/**end repeat**/
680680

681-
682681
#define __popcnt32 __popcnt
683682
/**begin repeat
684683
*

0 commit comments

Comments
 (0)
0