Groups > comp.lang.python > #198029

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

From	Paul Rubin <no.email@nospam.invalid>
Newsgroups	comp.lang.python
Subject	Re: ( n & -n ).bit_length() - 1 ## Really?
Date	2026-09-19 14:50 -0700
Organization	A noiseless patient Spider
Message-ID	<87v780j4gz.fsf@nightsong.com> (permalink)
References	<X0ArS.155893$NMu2.109571@fx15.ams4>

Show all headers | View raw

"Johann \"Myrkraverk\" Oskarsson" <johann@myrkraverk.invalid> writes:
>   ( n & -n ).bit_length() - 1

This formula is very famous.  In twos complement arithmetic, -n is (1
plus the bit complement of n_.  So first, turn all the rightmost 0's
into 1's.  The 1 immediately to the left of the rightmost 0 (call this
bit # k) turns into a 0.  All the other bits are similarly inverted.

Now add 1.  So the now-rightmost block of 1's turn back into 0.  Bit # k
turns back into 1.  And all the other bits stay inverted.

Now AND.  All the upper bits are ANDed with their complements so they
become 0.  Bit # k remains 1.  And all the bits below it are 0.  So
you've zeroed all the bits except the 1 immediately to the left of the
block of 0's that you're interested in.  The bit length is the length of
(the block you want plus the leading 1).  So subtract 1 to adjust for
the leading 1 being counted.  Done.

Back to comp.lang.python | Previous | Next — Previous 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