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

Groups > comp.lang.c > #252666

Re: portable way to get highest bit set?

Show all headers | View raw

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?

Back to comp.lang.c | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-13 15:29 -0700
  Re: portable way to get highest bit set? Anton Shepelev <anton.txt@gmail.moc> - 2023-10-14 01:50 +0300

csiph-web