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

Groups > comp.lang.c > #300553

Re: portable way to get highest bit set?

Show key headers only | View raw

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

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

csiph-web