Path: csiph.com!news.nrbbs.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!peer05.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx12.ams4.POSTED!not-for-mail MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: ( n & -n ).bit_length() - 1 ## Really? Newsgroups: comp.lang.python,comp.lang.c,sci.math References: <118mo9b$2i0j0$1@dont-email.me> Content-Language: en-US From: "Johann \"Myrkraverk\" Oskarsson" Organization: Watcom Pro Ltd. In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Lines: 75 Message-ID: X-Complaints-To: abuse@easynews.com X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly. Date: Sun, 20 Sep 2026 04:52:22 +0800 X-Received-Bytes: 4432 Xref: csiph.com comp.lang.python:198027 comp.lang.c:402288 sci.math:647529 On 9/20/2026 4:32 AM, Johann "Myrkraverk" Oskarsson wrote: > On 9/20/2026 3:37 AM, Lane W wrote: >> Johann "Myrkraverk" Oskarsson wrote: >>> On 9/20/2026 2:23 AM, Stefan Ram wrote: >>>> "Johann \"Myrkraverk\" Oskarsson" wrote >>>> or quoted: >>>>> The above formula seems to work, given a few spot checks, but I >>>>> thought >>>>> this should be a utility function in the underlying multiprecision >>>>> lib- >>>>> rary in Python.  Is the calculation n & -n really necessary? >>>> >>>>    While "n & -n" might take some time for large Python integers, >>>>    I see no way to do it faster in Python. >>>> >>>>    In C, one might be able to access the segments of large numbers >>>>    (the "limbs") starting with the least significant one to shortcut >>>>    the operation as soon as a "1" is found. >>> >>> Yes, this is perplexing.  I'm working with /arbitrary large numbers/ in >>> Cryptohack, for cryptographic purposes, and need a utility function to >>> count the number of zero bits from the right. >>> >>> The toy implementations of the Jacobi Symbol I've seen online, in Python >>> and otherwise, all seem to use a loop to repeatedly divide by two, which >>> is presumably much slower, so I'm /sort of happy/ with this method. >>> >>> For practical applications, I resorted to the jacobi_symbol() function >>> in SymPy, since I have not finished a correct implementation myself. >>> But more on that in a later post. >> >> Negative values are stored by flipping all bits of n and adding 1. >> This is exactly why negating numbers with trailing zeros causes long >> carry chains, and negating numbers with trailing ones does not. >> > > Thank you for that exposition.  This is precisely why I am perplexed and > befuddled.  For arbitrary long integers -- in bits -- this chain of > carries over unknown machine words internally to the Python interpreter > seems completely unnecessary, and it really should be simpler to just > count the zero bits in the underlying C code. > > Why can't we do that? For instance, here is the utility function in LibTomMath, mp_cnt_lsb(), chosen because I was looking at the Jacobi Symbol algorithm in Tom St Denis' book, /BigNum Math/ when I came across this little optimization. https://github.com/libtom/libtommath/blob/develop/mp_cnt_lsb.c I presume all erudite readers of comp.lang.python already have a physi- cal copy on their shelf, but I can link the PDF in the GitHub assets if requested. Please turn to page 270, line 057 in the code listing. I have added comp.lang.c, if anyone needs the standard thumpers to explain the code in the link, and sci.math, if anyone needs an expla- nation of the mathematics. For the latter, I use /Graduate Texts in Mathematics #84/, /A Classical Introduction to Modern Number Theory/ by Kenneth Ireland, and Michael Rosen. See https://link.springer.com/series/0136 for the entire series. I do not use L.L.Ms. to grok mathematics. So, presuming this is a standard function in all multiprecision arith- metical libraries, why can't we just do this directly in Python? -- 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 ( ;; ) _:;