Path: csiph.com!weretis.net!feeder8.news.weretis.net!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: portable way to get highest bit set? Date: Thu, 12 Oct 2023 08:05:40 -0700 Organization: A noiseless patient Spider Lines: 65 Message-ID: <86v8bbanjv.fsf@linuxsc.com> References: <20231011102714.44a870af4dfe68f756974953@g{oogle}mail.com> <86h6mxawqq.fsf@linuxsc.com> <20231012111100.272c96b3209baad26a150e55@g{oogle}mail.com> <86cyxkb2ka.fsf@linuxsc.com> <20231012141719.99f5a10ec921db3ee6f7d948@g{oogle}mail.com> <864jiwaqic.fsf@linuxsc.com> <20231012173021.0000149c@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: dont-email.me; posting-host="8a29b169449756014084ae3fe2a46ca6"; logging-data="2694084"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18+jr3vh7P7jlfvQHrGAI1IFnlYE4hqnHw=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:Ub2bNXzxAtVFV+EHu0kx3eJrTvk= sha1:S9AYgHMT8jCmmy25dqBltRqddJM= Xref: csiph.com comp.lang.c:237875 Michael S writes: > On Thu, 12 Oct 2023 07:01:47 -0700 > Tim Rentsch wrote: > >> Anton Shepelev writes: >> >>> Tim Rentsch: >>> >>>> 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. >>> >>> Well, I could use macros, or the largest integer type, or: >> >> Neither necessary nor sufficient. The code should work for >> the type T being __uint128_t, which is larger than uintmax_t. >> >>> #include >>> #include >>> >>> [..examine value character-by-character, including >>> determining if little-endian encoding is used..] >> >> You're making things more complicated than they need to be. >> Looking at character values rather than just values of the type >> involved is almost guaranteed to have potential representation >> issues. For example, little endian and big endian are not the >> only choices possible for endianness. >> >> Below is a proposed solution that mostly works. What problems >> does it have, and how can they be fixed? And can we find >> something better? >> >> /* The type T has been supplied somewhere upstream. It */ >> /* is an unsigned type, and possibly outside the realm */ >> /* of 'integer types' as defined by the C standard, as */ >> /* for example __uint128_t. */ >> >> T >> highest_bit_set( T u ){ >> T r = 1; >> while( u>>1 > r ) r <<= 1; >> return r; >> } > > That code does not look like working. Yes, deliberately so. I didn't want to give working code yet, so other people could work on the problem. > That is: > > T > highest_bit_set1( T u ){ > T r = 0; > while (u > r) r = r*2+1; > return r ^ (r>>1); > } As expected, this works. I like the way it naturally accommodates a zero input. Can you find a different solution that works in logarithmic time rather than linear time?