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>
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

"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.