Path: csiph.com!1.us.feeder.erje.net!3.eu.feeder.erje.net!feeder.erje.net!news.szaf.org!gandalf.srv.welterde.de!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, 19 Oct 2023 00:14:06 -0700 Organization: A noiseless patient Spider Lines: 76 Message-ID: <86o7gv5bk1.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> <86v8bbanjv.fsf@linuxsc.com> <20231013021504.12623444fc7d7fdaab87f1e0@gmail.moc> <86mswm9mwk.fsf@linuxsc.com> <20231014015035.a51cbb621de8eea5ac6a8651@gmail.moc> <20231017183345.26e2afd8641d5c63f8e8e630@gmail.moc> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: dont-email.me; posting-host="c39f9e0eb637dc2d4d061ce94725fd35"; logging-data="235262"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19iUj46CGF5yRl5h3tJhVnT8iDrPj6+5dE=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:OLLAuMdhWs5FBTaw13viKDdjv8A= sha1:oNRsEAzyKZ5l1Q299YcrBaqWZrs= Xref: csiph.com comp.lang.c:300553 Anton Shepelev 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; }