Path: csiph.com!pasdenom.info!news.gegeweb.eu!gegeweb.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: portable way to get highest bit set?
Date: Fri, 13 Oct 2023 15:29:31 -0700
Organization: A noiseless patient Spider
Lines: 37
Message-ID: <86mswm9mwk.fsf@linuxsc.com>
References: <ug5gvh$1jkar$3@dont-email.me> <20231011102714.44a870af4dfe68f756974953@g{oogle}mail.com> <ug6huc$1rvp1$1@dont-email.me> <86h6mxawqq.fsf@linuxsc.com> <20231012111100.272c96b3209baad26a150e55@g{oogle}mail.com> <86cyxkb2ka.fsf@linuxsc.com> <20231012141719.99f5a10ec921db3ee6f7d948@g{oogle}mail.com> <864jiwaqic.fsf@linuxsc.com> <20231012173021.0000149c@yahoo.com> <86v8bbanjv.fsf@linuxsc.com> <20231013021504.12623444fc7d7fdaab87f1e0@gmail.moc>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="a03fa788dc159b4dec27c6d302b8dace"; logging-data="3620535"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+8p4r0913XCJPo99VRkDVlN5DVB34nuxA="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:UAb6jrwxV3VtNC+14mh1GtXczZE= sha1:9Mk8sikrMpe+LiUaIeFvNy/GsP4=
Xref: csiph.com comp.lang.c:252666

Anton Shepelev <anton.txt@gmail.moc> writes:

> Tim Rentsch:
>
>> Can you find a different solution that works in
>> logarithmic time rather than linear time?
>
> Direct linear search comes to mind.  Instead of long long
> int below, use the widest integer type that your C
> environment supports:
>
> #define LLBM CHAR_BIT * sizeof( long long ) - 1
>
> unsigned long long int
> high_bit_mask( unsigned long long n )
> {  unsigned long long m   = ULLONG_MAX;
>    int l = 0, r = LLBM+1;
>    while( 1 )
>    {  const int ofs = (l + r) / 2;
>       const unsigned long long mn = n & (m << LLBM - ofs);
>
>            if( mn >  0 ) r = ofs;
>       else if( mn == 0 ) l = ofs + 1;
>       if( l == r ) break;
>    }
>    /* How can I avoid this condition? */
>    return l == LLBM + 1 ? 0 : 1 << LLBM-l;
> }

Before giving any comment on the algorithm, I'd like to ask a
question about layout style.  Your code follows the unusual
practice of starting controlled blocks with an open brace at the
start (possibly indented) of a line, and the first code line of
the block on the same line as the open brace.  Is this practice
something you started by yourself, or did you see it and adopt
it from somewhere else?  What kinds of reasons persuaded you
to follow it?