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

Groups > comp.lang.c > #300553 > 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-19 00:14 -0700
    Re: portable way to get highest bit set? Anton Shepelev <anton.txt@gmail.moc> - 2023-10-19 12:23 +0300

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

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

> I wrote:
>
>> 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.

[a long line wrapped]

> Here it is:
>
>    unsigned long int
>    high_bit_mask( unsigned long n )
>    {  const unsigned long M = 
>                 (unsigned long)1 << (CHAR_BIT * sizeof( long ) - 1);
>             unsigned long mask = 0;
>       int l = -1,
>           r =  CHAR_BIT * sizeof( long );
>
>       while( 1 )
>       {  unsigned long C;
>          const int m = (l + r)/2;
>
>          C = M >> m;
>          if( n >= C ) { r = m; mask = C; }
>          else         { l = m;           }
>
>          if( r - l == 1 ) break;
>       }
>       return mask;
>    }

Is there some reason you are using a while(1) with a conditional
'break;' statement at the end rather than just using do...while;?
I think most people would agree that using a do...while is better
style.

> It does not work with `long long' in my environment, so I post
> the code for `long'.

It seems you still do not get the spirit of the problem.  Part of
the goal is to make the code not depend on a specific choice of
type for the values being worked on.  The code above has 'long'
and 'unsigned long' all over the place.  Rather than do that,
write the function in terms of an abstract type T, and then put a
typedef for T before the function for whatever type you think is
appropriate for your environment.  I would like to take any code
posted and incorporate it into my little test bench here so I can
test it and see how it does, but having to go through this code
and change all the 'unsigned long's and so forth makes that a big
pain in the ass.

> This is the cleanest binary search vesion that I can think of.

The following binary search code is simpler and runs faster.

    T
    hbs_binary( T u ){
        const T one = 1, v = u>>1;
        unsigned least = 0, limit = MASK_WIDTH( -one );

        do {
            const unsigned k = least+limit >> 1;
            const T bit = one << k;

            /**/ if(  bit <= v  )  least = k+1;
            else if(  bit >  u  )  limit = k;
            else                   return  bit;

        } while(  limit > 0  );

        return  0;
    }

[toc] | [next] | [standalone]

#301455

Tim Rentsch to Anton Shepelev:

> > unsigned long int
> > high_bit_mask( unsigned long n )
> > {  const unsigned long M = (unsigned long)1 << (CHAR_BIT * sizeof( long ) - 1);
> >          unsigned long mask = 0;
> >    int l = -1,
> >        r =  CHAR_BIT * sizeof( long );
> >
> >    while( 1 )
> >    {  unsigned long C;
> >       const int m = (l + r)/2;
> >
> >       C = M >> m;
> >       if( n >= C ) { r = m; mask = C; }
> >       else         { l = m;           }
> >
> >       if( r - l == 1 ) break;
> >    }
> >    return mask;
> > }
>
> Is there some reason you are using a while(1) with a
> conditional 'break;' statement at the end rather than just
> using do...while;?  I think most people would agree that
> using a do...while is better style.

None at all.  I started designing the loop in the general
form, and then failed to notice that the final version had a
single `break' at the end, in which case do..while is indeed
better.

> It seems you still do not get the spirit of the problem.
> Part of the goal is to make the code not depend on a
> specific choice of type for the values being worked on.

Since C does not have generics, I thought the actual
function must work with /some/ specific type, which can be
the largest integer type available.

> The code above has 'long' and 'unsigned long' all over the
> place.  Rather than do that, write the function in terms
> of an abstract type T, and then put a typedef for T before
> the function for whatever type you think is appropriate
> for your environment.

Using #typedef thus to emulate generics simply did not occur
to me.  A truly generic solution would be a macro that
generated a function for the type passed in the parameter,
yet nobody has written such a macro.

> I would like to take any code posted and incorporate it
> into my little test bench here so I can test it and see
> how it does, but having to go through this code and change
> all the 'unsigned long's and so forth makes that a big
> pain in the ass.

OK:

T
high_bit_mask( T n )
{  const T   M    =  (T)1 << (CHAR_BIT * sizeof( T ) - 1);
         T   mask =  0;
         int l    = -1,
             r    =  CHAR_BIT * sizeof( T );

   do
   {  const int m = (l + r)/2;
            T   C = M >> m;

      if( n >= C ) { r = m; mask = C; }
      else         { l = m;           }
   } while( r - l > 1 );

   return mask;
}

> The following binary search code is simpler and runs faster.
>
>     T
>     hbs_binary( T u ){
>         const T one = 1, v = u>>1;
>         unsigned least = 0, limit = MASK_WIDTH( -one );
>
>         do {
>             const unsigned k = least+limit >> 1;
>             const T bit = one << k;
>
>             /**/ if(  bit <= v  )  least = k+1;
>             else if(  bit >  u  )  limit = k;
>             else                   return  bit;
>
>         } while(  limit > 0  );
>
>         return  0;
>     }

I disagree about the higher simplicity of your code, because
it

  1.  has two return statements,

  2.  employs the /clever trick/ of comparing the mask to
      different values in different branches.

  3.  uses a three-way `if'.

  4.  uses conditions that are not mutually exclusive.

  5.  uses `least' and `limit' instead of intuitive `left'
      and `right' or `min' and `max'.  My version makes a
      point of giving its left and right indices the
      intuitive meaning that they have in the standard
      positional notation.

My version, however, is still not a plain-vanilla binary search.

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