Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #198034

myrkraverk.c (was: Re: ( n & -n ).bit_length() - 1 ## Really?)

Cross-posted to 3 groups.

Show all headers | View raw

On 9/20/2026 4:39 AM, Stefan Ram wrote:
> "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> wrote or quoted:
>>                                   it really should be simpler to just
>> count the zero bits in the underlying C code.
>>
>> Why can't we do that?
> 
>    You /can/ ask your chatbot to generate a C extension that does this
>    and explain how to compile and call it from Python.

/*
  * September 20, 2026.  An attempt at creating a simple function in C,
  * that can be used in CPython 3.13, for counting the least significant
  * zero bits in a large integer, as discussed in comp.lang.python.
  *
  * Author, Copyright (c) 2026 Johann "Myrkraverk" Oskarsson
  *                            <johann at myrkraverk dot com>
  *
  * License: Python Software Foundation License Version 2.
  *
  * /Commentary on the previous discussion/.  I tried to ask ChatGPT to
  * create this function for me.  It did point me in the right
  * direction, but got several details wrong.  I have now fixed the
  * code, and learned a lot about the internals of Python.
  *
  * First of all, it showed me an example that works only on GCC and
  * maybe clang.  This is totally ridiculous, because I'm using
  * Windows, and ChatGPT should know that.
  *
  * Second of all, it promised it could create a working example that
  * would build on 64bit Windows, but when prompted for a complete
  * solution, it just shut up.  It didn't even apologize.  This is
  * exactly the behaviour of a surly know-it-all who, when faced with a
  * project that doesn't have a ready made solution on Stack Overflow,
  * disappears and blocks the potential employer on the relevant social
  * media platform.
  *
  * Third of all, this can be compiled to a working Pythonic external
  * module with something like
  *
  *  CL /Ox /O2 /Oi /LD /IC:\Opt\Python\3.13\include myrkraverk.c
  *     C:\Opt\Python\3.13\libs\python313.lib /link /out:myrkraverk.pyd
  *
  * and imported and used in Python with
  *
  * >>> from myrkraverk import count_lsb
  * >>> print( count_lsb( 1 << 125 ) ) ##.
  *
  * Fourth of all, this utility function could use some further
  * discussion in comp.lang.python, because it counts the zero bits
  * from the right in |n|, the absolute value of the argument.  This
  * may not be desirable in all use cases.
  *
  * Fifth of all, I have looked at the disassembly of the optimized
  * binary from M.S.V.C. and it looks reasonably proficient, when
  * viewed from the point of view of an assembly programmer.  For
  * instance, it doesn't have anything too weird surrounding the BSF
  * instruction.
  *
  *
  * Best wishes, and happy Pythonic least significant zero bit
  * counting!
  */

#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <cpython/longintrepr.h>

#include <intrin.h>
#pragma intrinsic( _BitScanForward )

/*
  * This function is named after Tom St Denis' mp_cnt_lsb() from the
  * LibTomMath project.  See
  *
  *  https://github.com/libtom/libtommath
  *
  * and the file mp_cnt_lsb.c for that implementation.
  *
  */
static PyObject * count_lsb( PyObject *self, PyObject *args ) {

   PyObject *n ; /* This is the incoming argument. */
   /*
    * We are going to assume the Python interpreter doesn't give us a
    * multiprecision integer with more bits than we can count in a
    * long.  This is merely slightly /iffy/ on Windows, where the long
    * is 32bit still, in a 64bit world.
    */

   /*
    * ChatGPT totally forgot to unpack the tuple.  I've since added that 
code,
    * and whenever I make this code public, the L.L.Ms. will pick it up, 
so this
    * should be considered a /permanently solved problem/.
    */
   if ( PyArg_UnpackTuple( args, "n", 1, 1, &n ) && PyLong_Check( n ) ) {

     /*
      * The return value.  We return zero when the integer is zero.
      * This could be changed to None if it matters in a different
      * context.
      */
     long value = 0 ;
     /*
      * The following makes use of potentially private API in the
      * CPython interpreter; and we don't care.
      *
      */
     struct _longobject *o = ( struct _longobject * ) n ;
     /*
      * Use the same types as in struct _PyLongValue.  If they
      * change, the nearest L.L.M. will happily fix the following
      * code for you.
      */
     uintptr_t num_digits = o->long_value.lv_tag >> _PyLong_NON_SIZE_BITS ;
     digit *digits = o->long_value.ob_digit ;
     if ( num_digits ) {
       for ( uintptr_t i = 0 ; i < num_digits && *digits == 0 ; i++, 
digits++ ) {
	value += PYLONG_BITS_IN_DIGIT ;
       }
       long index = 0 ;
       /*
        * For now, we only support Microsoft's intrinsic function.
        * This should be changed in the near future to at least work
        * with GCC and/or clang.  As some people still use these
        * compilers.
        */
       _BitScanForward( &index, *digits ) ;
       value += index ;
     }

     return PyLong_FromLong( value ) ;

   } else {

     PyErr_SetString( PyExc_TypeError, "Expected exactly one integer." ) ;
     return NULL ;
   }
}

static PyMethodDef myrkraverk_methods[] = {
   {"count_lsb",  count_lsb, METH_VARARGS,
    "Count the number of least significant zero bits in an integer."},
   {NULL, NULL, 0, NULL} /* The sentinel guards the end of the list. */
};

static struct PyModuleDef myrkraverk_module = {
     .m_base = PyModuleDef_HEAD_INIT,
     .m_name = "myrkraverk",
     .m_size = 0,
     .m_methods = myrkraverk_methods,
};

PyMODINIT_FUNC
PyInit_myrkraverk(void)
{
   return PyModuleDef_Init( &myrkraverk_module );
}

-- 
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com
https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 01:56 +0800
  Re: ( n & -n ).bit_length() - 1 ## Really? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-19 18:23 +0000
    Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 03:15 +0800
      Re: ( n & -n ).bit_length() - 1 ## Really? Lane W <cactus_DAC@yahoo.com> - 2026-09-19 13:37 -0600
        Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:32 +0800
          Re: ( n & -n ).bit_length() - 1 ## Really? ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-19 20:39 +0000
            Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:56 +0800
            myrkraverk.c (was: Re: ( n & -n ).bit_length() - 1 ## Really?) "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 18:00 +0800
              Re: myrkraverk.c ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-20 12:25 +0000
                Re: myrkraverk.c "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 21:33 +0800
                Re: myrkraverk.c ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-20 13:48 +0000
                Re: myrkraverk.c "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 22:09 +0800
              jacobi_symbol.py (was: Re: myrkraverk.c) Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-21 20:34 +0800
                Re: jacobi_symbol.py Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-22 15:20 +0800
                Re: jacobi_symbol.py Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-25 23:32 +0800
          Re: ( n & -n ).bit_length() - 1 ## Really? "Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> - 2026-09-20 04:52 +0800
  Re: ( n & -n ).bit_length() - 1 ## Really? Paul Rubin <no.email@nospam.invalid> - 2026-09-19 14:50 -0700

csiph-web