Thanks for the review @seberg

Did we decide what the output dtype is? The default integer, the same integer?

For the scalar version we decided to always output an 8 bit (uint8_t). Although here it might be the case, will need to change it.

There could be an argument of where

This brings a very good point on if we can create a np.bits namespace of sorts and club the bits stuff there, what do you think?

This PR seems so close. Anything I can do to help get this over the finish line @ganesh-k13? For certain similarity functions (like hamming distance) the bit count function is the bottleneck, and this could really unlock pure python solutions without needing to resort to something in a lower level language.

Hey @softwaredoug , we support bit_count today and was added via #19355. This PR is mainly to get a bit_count UFunc so we can operate it on arrays, etc.

Well to answer your question on moving it forward, implementation wise, perhaps the generate_umath can be made simpler. But the bigger hurdle would be convince the mailing list that this function is needed and doesn't add more to the already bloated namespace.

So in conclusion, if you feel this has a genuine use case for many in the community (the UFunc of course, the scalar version is already in), you can start a thread in the mailing list. Now I can prioritize this to completion if everyone is ok with adding this UFunc and if you want to contribute, I can help you in any way with terms of navigating this bit.

I will give my 👍 for the ufunc, but not for the method (on the array object). Feel free to announce to the mailing list that pending no substantial objects we will move forward with adding it.

The return dtype has to be resolved, but I guess it was defined as uint8 for the scalars? In which case we have prior art.

Awesome - thanks @ganesh-k13 and @seberg

Maybe this is my numpy ignorance, but is there a way to efficiently apply the scalar function to a whole array? Without something like apply_along_axis which in my mental model wouldn't be particularly fast?

No, there isn't an efficient way (maybe a JIT'er like numba can do it, not sure). You could write your own ufunc, its not actually that terribly hard, but the learning curve is just quite steep, especially if you are not used to C (ufunclab is my goto example for external ufuncs currently).

Hey @BvB93 , basic question: If we fix the return type of UFunc to one dtype, where do we make the typing changes?

Now I do get ValueError: Unexpected reveal line format: 23: error: Name "ctypes._Pointer" is not defined in numpy/typing/tests/test_typing.py, but I don't know how to interpret this. I guess we need to make some change in numpy/typing/tests/data/reveal/ufuncs.pyi?

Updated bit_count (just the UFunc) to bitwise_count. Reference to discussion regarding the same: discussions

Resolved merge conflicts (rebased with latest main).

[EDIT] Should have built locally before pushing, checking... Bad merge, fixed now

Long overdue look at the Array API standard. Two callouts:

1. elementwise_functions section does not include bitwise_count, but a note: All other functions that operates on bits use bitwise_*
2. bitwise_operators specification only talks of: Bitwise operators should be defined for arrays having integer and boolean data types., which we do follow in this change list.

Are any more changes needed here @seberg?

I have made few changes to the code to allow auto-vectorization, and here the result on x86 with avx2 enabled:

❯ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz

❯ gcc --version
gcc (GCC) 13.2.1 20230801

❯ spin bench --compare enh_16325_popcount_ufunc_before -t bitwise_count
| Change   | Before [03fc9291] <enh_16325_popcount_ufunc_before>   | After [fc6b5911] <enh_16325_popcount_ufunc>   |   Ratio | Benchmark (Parameter)                                                             |
|----------|-------------------------------------------------------|-----------------------------------------------|---------|-----------------------------------------------------------------------------------|
| -        | 253±0.1μs                                             | 170±0.1μs                                     |    0.67 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'H') |
| -        | 180±0.4μs                                             | 58.9±0.6μs                                    |    0.33 | bench_ufunc.UFunc.time_ufunc_types('bitwise_count')                               |
| -        | 353±0.8μs                                             | 117±1μs                                       |    0.33 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'h') |
| -        | 564±0.5μs                                             | 121±0.2μs                                     |    0.22 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'l') |
| -        | 566±4μs                                               | 123±0.4μs                                     |    0.22 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'q') |
| -        | 621±3μs                                               | 108±1μs                                       |    0.17 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'i') |
| -        | 562±0.5μs                                             | 79.6±0.2μs                                    |    0.14 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'L') |
| -        | 562±0.4μs                                             | 80.5±0.2μs                                    |    0.14 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'Q') |
| -        | 679±3μs                                               | 75.1±0.06μs                                   |    0.11 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'I') |
| -        | 269±1μs                                               | 11.9±0.08μs                                   |    0.04 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'B') |
| -        | 309±0.2μs                                             | 12.8±0.05μs                                   |    0.04 | bench_ufunc_strides.UnaryIntContig.time_unary(<ufunc 'bitwise_count'>, 1, 1, 'b') |

Wow! Thanks Sayed!

Wow! Thanks Sayed!

Not that good, the GCC compiler was expected to apply something similar to Harley-Seal popcount algorithm for optimized machine code generation. However, it defaulted to using the standard popcnt instruction without additional optimizations. To potentially enhance performance, we could improve the existing "fast macros" to provides better hints for the compiler maybe by manually unrolling specialized loops counting on C++ meta or/and implementing the algorithm with handwritten generic SIMD intrinsics.

@ganesh-k13 seems like nobody but me has much squirms about diverging from Python naming. Could you rebase/merge to fix the ufuncs.pyi conflict so that we can get this in?

@seberg I've resolved the conflicts and UT failures, let me know if anything else needed here.

@seberg any other changes needed here?

Sorry, do you have time to resolve the conflict, I think that was really all that was left here, just I was in and out a bit much.

@seberg it seems to pass now 👍 , good to go from my end.

Thanks, let's get it in before it diverges again.

This is probably the longest I've worked on a PR :). Now time to get hex/fromhex in 😉

This is great! One observation – the implementation does not appear to support general output dtypes:

>>> import numpy as np
>>> np.bitwise_count(2, dtype='int32')
# ---------------------------------------------------------------------------
# TypeError                                 Traceback (most recent call last)
# <ipython-input-6-f7427f7dde09> in <cell line: 2>()
#       1 import numpy as np
# ----> 2 np.bitwise_count(2, dtype='int32')

# TypeError: No loop matching the specified signature and casting was found for ufunc bitwise_count

It would be nice if we could support the dtype argument.

Probably could do something about it, but the problem is that dtype= doesn't really mean output_dtype= which can only be achieved by out=.... dtype= means more something like "operation dtype".

So to make it work, you would have to explicitly teach the ufunc that dtype=int32 should just use the int8 loop (and cast). Which is actually possible by adding a promoter.
(Or it is be possible via some slight extensions/changes, by saying that it is really an to integer loop that happens to use (u)int8.)