Path: csiph.com!weretis.net!feeder8.news.weretis.net!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: Thu, 12 Oct 2023 02:41:25 -0700
Organization: A noiseless patient Spider
Lines: 53
Message-ID: <86cyxkb2ka.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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="8a29b169449756014084ae3fe2a46ca6"; logging-data="2560063"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX185rh8UDkgyKWMicT8iBexYINHejVm3ec4="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:M6SJag/U2cPSbeqNwsRwWnbxDSs= sha1:2S3LtOacVe7+wngz2jtb8/CudsU=
Xref: csiph.com comp.lang.c:236095

Anton Shepelev <anton.txt@g{oogle}mail.com> writes:

> Tim Rentsch:
>
>> I've coded up a dozen[*] different solutions.
>> Here is my current avorite[**]:
>>
>>     typedef union {
>>         long double d;
>>         struct { unsigned long long s; unsigned e:15;} b;
>>     } X;
>>
>>     unsigned long long
>>     high_bit_set( unsigned long long u ){
>>         return  1ULL << (X){ .d = u }.b.e - 16383  & u;
>>     }
>
> And mine is quite anticlimactic.  It accepts a byte, because
> I wrote it yesterday, before learning that the OP needs a
> more generic solution:
>
>    unsigned char highest_bit( unsigned char byte )
>    {    int           i            ;
>         unsigned char mask = 1 << 7;
>         for( i = 0; i <= 8; i += 1 )
>         {    if( byte & mask )
>              {    break;  }
>              mask >>= 1;
>         }
>         return mask;
>    }
>
> It is the most straight-forward method that I could think
> of, and extensible to larger sizes of the variable.

But the approach you are using requires knowing the size
of the type involved.  The challenge is to write code
that works without having to know the size in advance.
So something like the following, with type T being an
unknown unsigned integer type:

    T
    highest_bit_set( T u ){
        T r;
        /* set r to the highest bit set in u */
        return  r;
    }

I have written code for this form of the problem, but
won't be posting it before the weekend.  Try it!

P.S. My earlier "solution" was just for fun, not a serious
attempt to solve the problem.