Groups > comp.lang.python > #198029

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

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From	Paul Rubin <no.email@nospam.invalid>
Newsgroups	comp.lang.python
Subject	Re: ( n & -n ).bit_length() - 1 ## Really?
Date	Sat, 19 Sep 2026 14:50:20 -0700
Organization	A noiseless patient Spider
Lines	17
Message-ID	<87v780j4gz.fsf@nightsong.com> (permalink)
References	<X0ArS.155893$NMu2.109571@fx15.ams4>
MIME-Version	1.0
Content-Type	text/plain
Injection-Date	Sat, 19 Sep 2026 21:50:21 +0000 (UTC)
Injection-Info	dont-email.me; logging-data="2763297"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/5mgMZ3wlzXemjI+2U763/"; posting-host="97b5d7feda9b91c75ad571ffdb1f5385"
User-Agent	Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock	sha1:mLcgjOhu29bBeP3777iFSDAqHSo= sha1:vOIzOWnAk8lSqR5LZrHxjoNkqCk= sha256:lJYKaWA6qcWBPtaBFZ621aCNEB40peMCZZZMTNgroGE= sha1:QLoAeE87spanJ0vTt/d6fgA9sx8= sha256:yieXwbb98zmQAIkMl12zt5JYUWaMTERPgS6bIvMKUUE=
Xref	csiph.com comp.lang.python:198029

Show key headers only | 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