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

Commit 350b27c

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 214cbea commit 350b27c

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', '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
@@ -181,3 +181,5 @@ Miscellaneous
181181
real_if_close
182182

183183
interp
184+
185+
bit_count

‎numpy/__init__.pyi

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

2470+
def bit_count(
2471+
self,
2472+
out: None | NDArray[Any] = ...,
2473+
*,
2474+
where: _ArrayLikeBool_co = ...,
2475+
casting: _CastingKind = ...,
2476+
order: _OrderKACF = ...,
2477+
dtype: DTypeLike = ...,
2478+
subok: bool = ...,
2479+
) -> NDArray[Any]: ...
2480+
24702481
# Keep `dtype` at the bottom to avoid name conflicts with `np.dtype`
24712482
@property
24722483
def dtype(self) -> _DType_co: ...
@@ -2614,6 +2625,17 @@ class generic(_ArrayOrScalarCommon):
26142625
self: _ScalarType, *shape: SupportsIndex, order: _OrderACF = ...
26152626
) -> NDArray[_ScalarType]: ...
26162627

2628+
def bit_count(
2629+
self,
2630+
out: None | NDArray[Any] = ...,
2631+
*,
2632+
where: _ArrayLikeBool_co = ...,
2633+
casting: _CastingKind = ...,
2634+
order: _OrderKACF = ...,
2635+
dtype: DTypeLike = ...,
2636+
subok: bool = ...,
2637+
) -> Any: ...
2638+
26172639
def squeeze(
26182640
self: _ScalarType, axis: None | L[0] | tuple[()] = ...
26192641
) -> _ScalarType: ...
@@ -3137,6 +3159,7 @@ arcsinh: _UFunc_Nin1_Nout1[L['arcsinh'], L[8], None]
31373159
arctan2: _UFunc_Nin2_Nout1[L['arctan2'], L[5], None]
31383160
arctan: _UFunc_Nin1_Nout1[L['arctan'], L[8], None]
31393161
arctanh: _UFunc_Nin1_Nout1[L['arctanh'], L[8], None]
3162+
bit_count: _UFunc_Nin1_Nout1[L['bit_count'], L[11], None]
31403163
bitwise_and: _UFunc_Nin2_Nout1[L['bitwise_and'], L[12], L[-1]]
31413164
bitwise_not: _UFunc_Nin1_Nout1[L['invert'], L[12], None]
31423165
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
@@ -363,6 +363,12 @@ array_min(PyArrayObject *self,
363363
NPY_FORWARD_NDARRAY_METHOD("_amin");
364364
}
365365

366+
static PyObject *
367+
array_bit_count(PyArrayObject *self, PyObject *args, PyObject *kwds)
368+
{
369+
NPY_FORWARD_NDARRAY_METHOD("_bit_count");
370+
}
371+
366372
static PyObject *
367373
array_swapaxes(PyArrayObject *self, PyObject *args)
368374
{
@@ -3011,9 +3017,11 @@ NPY_NO_EXPORT PyMethodDef array_methods[] = {
30113017
{"__dlpack__",
30123018
(PyCFunction)array_dlpack,
30133019
METH_FASTCALL | METH_KEYWORDS, NULL},
3014-
30153020
{"__dlpack_device__",
30163021
(PyCFunction)array_dlpack_device,
30173022
METH_NOARGS, NULL},
3023+
{"bit_count",
3024+
(PyCFunction)array_bit_count,
3025+
METH_VARARGS | METH_KEYWORDS, NULL},
30183026
{NULL, NULL, 0, NULL} /* sentinel */
30193027
};

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

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1806,7 +1806,7 @@ gentype_byteswap(PyObject *self, PyObject *args, PyObject *kwds)
18061806
* std, var, sum, cumsum, prod, cumprod, compress, sort, argsort,
18071807
* round, argmax, argmin, max, min, any, all, astype, resize,
18081808
* reshape, choose, tostring, tobytes, copy, searchsorted, view,
1809-
* flatten, ravel, squeeze#
1809+
* flatten, ravel, squeeze, bit_count#
18101810
*/
18111811
static PyObject *
18121812
gentype_@name@(PyObject *self, PyObject *args, PyObject *kwds)
@@ -2412,6 +2412,9 @@ static PyMethodDef gentype_methods[] = {
24122412
{"sum",
24132413
(PyCFunction)gentype_sum,
24142414
METH_VARARGS | METH_KEYWORDS, NULL},
2415+
{"bit_count",
2416+
(PyCFunction)gentype_bit_count,
2417+
METH_VARARGS | METH_KEYWORDS, NULL},
24152418
{"cumsum",
24162419
(PyCFunction)gentype_cumsum,
24172420
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