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

Groups > comp.lang.python > #198025

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

Show all headers | View raw

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" <johann@myrkraverk.invalid> 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?
-- 
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