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

Groups > comp.lang.python > #198024

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

Show all headers | View raw

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.

-- 
Everything I fight for leaves a bitter taste
Everything I cry for laughs into my face
Everything I scream for barely knows my name
Everything I'd die for will die just the same

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