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

Groups > comp.lang.c > #252666 > unrolled thread

Re: portable way to get highest bit set?

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#252666 — Re: portable way to get highest bit set?

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?

[toc] | [next] | [standalone]

#252816

Tim Rentsch:

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

I was bothered by the unaligned braces in K&R and by the
too-sparse look of the opening brace on a line of its own.
When a friend of mine was working on a coding style
guide[1], he researched exising indentaion styles and told
me about them, including Horstmann:

   <https://en.wikipedia.org/wiki/Indentation_style#Horstmann_style>

whence I took the main idea of placing braces.  My has
decided upon a different indetation, but I forget which and
I have not his guide at hand, but his Pascal indentation can
be seen in his showcase of programming fonts:

   <http://inversed.ru/Articles/Fonts_Comparison.png>

____________________
1. of which lack of bias and prejudice is an imoprtant
   advantage, because before that my friend use no style
   all, that is writing everything flat!

P.S.: reflecting on my solution later I decided that a
      direct comparison of the analysed value with a power
      of two might be better, especially because it is
      already in the form required for the return value.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  www.asciiribbon.org   -- against proprietary attachments

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web