8000 ENH: Added countbits (popcount) · softwaredoug/numpy@0266428 · GitHub
[go: up one dir, main page]
Skip to content

Commit 0266428

Browse files
ganesh-k13softwaredoug
ganesh-k13
authored and
softwaredoug
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 104addf commit 0266428

File tree

17 files changed

+173
-7
lines changed

17 files changed

+173
-7
lines changed

‎benchmarks/benchmarks/bench_ufunc.py

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

88

99
ufuncs = ['abs&# 8000 39;, 'absolute', 'add', 'arccos', 'arccosh', 'arcsin', 'arcsinh',
10-
'arctan', 'arctan2', 'arctanh', 'bitwise_and', 'bitwise_not',
10+
'arctan', 'arctan2', 'arctanh', 'bit_count', 'bitwise_and', 'bitwise_not',
1111
'bitwise_or', 'bitwise_xor', 'cbrt', 'ceil', 'conj', 'conjugate',
1212
'copysign', 'cos', 'cosh', 'deg2rad', 'degrees', 'divide', 'divmod',
1313
'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
@@ -2517,6 +2517,17 @@ class ndarray(_ArrayOrScalarCommon, Generic[_ShapeType, _DType_co]):
25172517
def __dlpack__(self: NDArray[number[Any]], *, stream: None = ...) -> _PyCapsule: ...
25182518
def __dlpack_device__(self) -> tuple[int, L[0]]: ...
25192519

2520+
def bit_count(
2521+
self,
2522+
out: None | NDArray[Any] = ...,
2523+
*,
2524+
where: _ArrayLikeBool_co = ...,
2525+
casting: _CastingKind = ...,
2526+
order: _OrderKACF = ...,
2527+
dtype: DTypeLike = ...,
2528+
subok: bool = ...,
2529+
) -> NDArray[Any]: ...
2530+
25202531
# Keep `dtype` at the bottom to avoid name conflicts with `np.dtype`
25212532
@property
25222533
def dtype(self) -> _DType_co: ...
@@ -2660,6 +2671,17 @@ class generic(_ArrayOrScalarCommon):
26602671
self: _ScalarType, *shape: SupportsIndex, order: _OrderACF = ...
26612672
) -> ndarray[Any, _dtype[_ScalarType]]: ...
26622673

2674+
def bit_count(
2675+
self,
2676+
out: None | NDArray[Any] = ...,
2677+
*,
2678+
where: _ArrayLikeBool_co = ...,
2679+
casting: _CastingKind = ...,
2680+
order: _OrderKACF = ...,
2681+
dtype: DTypeLike = ...,
2682+
subok: bool = ...,
2683+
) -> Any: ...
2684+
26632685
def squeeze(
26642686
self: _ScalarType, axis: None | L[0] | tuple[()] = ...
26652687
) -> _ScalarType: ...
@@ -3207,6 +3229,7 @@ arcsinh: _UFunc_Nin1_Nout1[L['arcsinh'], L[8], None]
32073229
arctan2: _UFunc_Nin2_Nout1[L['arctan2'], L[5], None]
32083230
arctan: _UFunc_Nin1_Nout1[L['arctan'], L[8], None]
32093231
arctanh: _UFunc_Nin1_Nout1[L['arctanh'], L[8], None]
3232+
bit_count: _UFunc_Nin1_Nout1[L['bit_count'], L[11], None]
32103233
bitwise_and: _UFunc_Nin2_Nout1[L['bitwise_and'], L[12], L[-1]]
32113234
bitwise_not: _UFunc_Nin1_Nout1[L['invert'], L[12], None]
32123235
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
@@ -21,6 +21,7 @@
2121
umr_minimum = um.minimum.reduce
2222
umr_sum = um.add.reduce
2323
umr_prod = um.multiply.reduce
24+
umr_bit_count = um.bit_count
2425
umr_any = um.logical_or.reduce
2526
umr_all = um.logical_and.reduce
2627

@@ -236,3 +237,8 @@ def _dump(self, file, protocol=2):
236237

237238
def _dumps(self, protocol=2):
238239
return pickle.dumps(self, protocol=protocol)
240+
241+
def _bit_count(a, out=None, *, where=True, casting='same_kind',
242+
order='K', dtype=None, subok=True):
243+
return umr_bit_count(a, out, where=where, casting=casting,
244+
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
@@ -1122,6 +1122,13 @@ def english_upper(s):
11221122
TD(ints),
11231123
TD('O', f='npy_ObjectLCM'),
11241124
),
1125+
'bit_count':
1126+
Ufunc(1, 1, None,
1127+
docstrings.get('numpy.core.umath.bit_count'),
1128+
None,
1129+
TD(ints),
1130+
TD('O', f='npy_ObjectPopCount'),
1131+
),
11251132
'matmul' :
11261133
Ufunc(2, 1, None,
11271134
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
@@ -370,6 +370,12 @@ array_ptp(PyArrayObject *self,
370370
NPY_FORWARD_NDARRAY_METHOD("_ptp");
371371
}
372372

373+
static PyObject *
374+
array_bit_count(PyArrayObject *self, PyObject *args, PyObject *kwds)
375+
{
376+
NPY_FORWARD_NDARRAY_METHOD("_bit_count");
377+
}
378+
373379

374380
static PyObject *
375381
array_swapaxes(PyArrayObject *self, PyObject *args)
@@ -3131,9 +3137,11 @@ NPY_NO_EXPORT PyMethodDef array_methods[] = {
31313137
{"__dlpack__",
31323138
(PyCFunction)array_dlpack,
31333139
METH_FASTCALL | METH_KEYWORDS, NULL},
3134-
31353140
{"__dlpack_device__",
31363141
(PyCFunction)array_dlpack_device,
31373142
METH_NOARGS, NULL},
3143+
{"bit_count",
3144+
(PyCFunction)array_bit_count,
3145+
METH_VARARGS | METH_KEYWORDS, NULL},
31383146
{NULL, NULL, 0, NULL} /* sentinel */
31393147
};

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

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1777,7 +1777,7 @@ gentype_byteswap(PyObject *self, PyObject *args, PyObject *kwds)
17771777
* std, var, sum, cumsum, prod, cumprod, compress, sort, argsort,
17781778
* round, argmax, argmin, max, min, ptp, any, all, astype, resize,
17791779
* reshape, choose, tostring, tobytes, copy, searchsorted, view,
1780-
* flatten, ravel, squeeze#
1780+
* flatten, ravel, squeeze, bit_count#
17811781
*/
17821782
static PyObject *
17831783
gentype_@name@(PyObject *self, PyObject *args, PyObject *kwds)
@@ -2390,6 +2390,9 @@ static PyMethodDef gentype_methods[] = {
23902390
{"sum",
23912391
(PyCFunction)gentype_sum,
23922392
METH_VARARGS | METH_KEYWORDS, NULL},
2393+
{"bit_count",
2394+
(PyCFunction)gentype_bit_count,
2395+
METH_VARARGS | METH_KEYWORDS, NULL},
23932396
{"cumsum",
23942397
(PyCFunction)gentype_cumsum,
23952398
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