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

> Tim Rentsch:
>
>> Can you find a different solution that works in
>> logarithmic time rather than linear time?
>
> Direct linear search comes to mind. Instead of long long
> int below, use the widest integer type that your C
> environment supports:
>
> #define LLBM CHAR_BIT * sizeof( long long ) - 1

The challenge is to write code that works without having to
know what that type is. The code you give relies on the type
directly by using ULLONG_MAX, and also indirectly by using the
above macro to calculate the number of bits in the type.
However the size of the type is not guaranteed to reflect
accurately how many value bits are available. If type T is an
unsigned type, we can get a value with all one bits easily:

T ones = -1;

To get the width of this value, let's postulate the existence
of a function (or macro) that calculates the width of such
values (that is, values that are one less than a power of two):

unsigned width = MASK_WIDTH( ones );

We could of course write a function that would compute such a
result, but we would like not to have to make a function call
at runtime. For the moment let's just assume we can do this.

> unsigned long long int
> high_bit_mask( unsigned long long n )
> { unsigned long long m = ULLONG_MAX;
> int l = 0, r = LLBM+1;
> while( 1 )
> { const int ofs = (l + r) / 2;
> const unsigned long long mn = n & (m << LLBM - ofs);
>
> if( mn > 0 ) r = ofs;
> else if( mn == 0 ) l = ofs + 1;
> if( l == r ) break;
> }
> /* How can I avoid this condition? */
> return l == LLBM + 1 ? 0 : 1 << LLBM-l;
> }

This code works but it strikes me as very busy; it seems to be
more cumbersome or cluttered than it needs to be. Using the
same basic approach of doing a binary search, here is a cleaner
and simpler version:

T
highest_bit_set_revised( T n ){
T const ones = -1;
unsigned least = 0, limit = MASK_WIDTH( ones );

do {
unsigned k = least+limit >> 1;
if( n & ones<<k ) least = k;
else limit = k;
} while( least+1 != limit );

return n & ones<<least;
}

To me this revision is a lot easier to read and understand.
What do you think about it?

(PS: Explanation of MASK_WIDTH() macro to follow in a later
posting.)

On Mon, 16 Oct 2023 02:47:22 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Anton Shepelev <anton.txt@gmail.moc> writes:
>
> > Tim Rentsch:
> >
> >> Can you find a different solution that works in
> >> logarithmic time rather than linear time?
> >
> > Direct linear search comes to mind. Instead of long long
> > int below, use the widest integer type that your C
> > environment supports:
> >
> > #define LLBM CHAR_BIT * sizeof( long long ) - 1
>
> The challenge is to write code that works without having to
> know what that type is. The code you give relies on the type
> directly by using ULLONG_MAX, and also indirectly by using the
> above macro to calculate the number of bits in the type.
> However the size of the type is not guaranteed to reflect
> accurately how many value bits are available. If type T is an
> unsigned type, we can get a value with all one bits easily:
>
> T ones = -1;
>
> To get the width of this value, let's postulate the existence
> of a function (or macro) that calculates the width of such
> values (that is, values that are one less than a power of two):
>
> unsigned width = MASK_WIDTH( ones );
>
> We could of course write a function that would compute such a
> result, but we would like not to have to make a function call
> at runtime. For the moment let's just assume we can do this.
>
> > unsigned long long int
> > high_bit_mask( unsigned long long n )
> > { unsigned long long m = ULLONG_MAX;
> > int l = 0, r = LLBM+1;
> > while( 1 )
> > { const int ofs = (l + r) / 2;
> > const unsigned long long mn = n & (m << LLBM - ofs);
> >
> > if( mn > 0 ) r = ofs;
> > else if( mn == 0 ) l = ofs + 1;
> > if( l == r ) break;
> > }
> > /* How can I avoid this condition? */
> > return l == LLBM + 1 ? 0 : 1 << LLBM-l;
> > }
>
> This code works but it strikes me as very busy; it seems to be
> more cumbersome or cluttered than it needs to be. Using the
> same basic approach of doing a binary search, here is a cleaner
> and simpler version:
>
> T
> highest_bit_set_revised( T n ){
> T const ones = -1;
> unsigned least = 0, limit = MASK_WIDTH( ones );
>
> do {
> unsigned k = least+limit >> 1;
> if( n & ones<<k ) least = k;
> else limit = k;
> } while( least+1 != limit );
>
> return n & ones<<least;
> }
>
> To me this revision is a lot easier to read and understand.
> What do you think about it?
>
> (PS: Explanation of MASK_WIDTH() macro to follow in a later
> posting.)

It works, but...
First, you postulated that zero-run-time MASK_WIDTH() exist without
actually writing such function. That sounds like cheating.
Second, your loop is 2-3 times slower then loops based Kaz's approach.
4-5 times slower than Kaz's non-loop code.
Overall, C grade at best.

On 16/10/2023 11:47, Tim Rentsch wrote:
> Anton Shepelev <anton.txt@gmail.moc> writes:
>
>> Tim Rentsch:
>>
>>> Can you find a different solution that works in
>>> logarithmic time rather than linear time?
>>
>> Direct linear search comes to mind. Instead of long long
>> int below, use the widest integer type that your C
>> environment supports:
>>
>> #define LLBM CHAR_BIT * sizeof( long long ) - 1
>
> The challenge is to write code that works without having to
> know what that type is. The code you give relies on the type
> directly by using ULLONG_MAX, and also indirectly by using the
> above macro to calculate the number of bits in the type.
> However the size of the type is not guaranteed to reflect
> accurately how many value bits are available. If type T is an
> unsigned type, we can get a value with all one bits easily:
>
> T ones = -1;
>

A bigger challenge would be to implement this all as a macro without
knowing the type T, so that it would work with extended integer types or
"almost" extended integer types (like gcc's unsigned __int128) that are
bigger than "unsigned long long" in C99, or "unsigned long" in C90. So
when the user calls "highest_bit_set(x)", all you have is a value of the
type, "x", not the type itself. "ones" would then be something like
"0ul * (x) - 1".

(I'm not suggesting that a macro like this is an ideal solution to the
OP's problem, just an interesting challenge.)

Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:

> On Thu, 12 Oct 2023 23:35:08 +0000, Lew Pitcher wrote:
>
>> On Wed, 11 Oct 2023 14:54:32 +0000, Lew Pitcher wrote:
>>
>>> On Wed, 11 Oct 2023 01:56:49 -0500, candycanearter07 wrote:
>>>
>>>> What is the best/most portable way to get the highest bit set?
>>>>
>>>> ie. 011010001 to 010000000
>>>
>>> What have you tried?
>>>
>>> I can think of one way, but it may not be the "best" or "most portable"
>>> way of setting the highest bit of a value, and it /does/ have some
>>> limitations. Show your work, and I might show mine.
>>
>> #include <limits.h>
>> unsigned long long int msb_mask(unsigned long long int valu)
>> {
>> unsigned long long int mask;
>>
>> for (mask = ((ULLONG_MAX) ^ (ULLONG_MAX >> 1));
>> mask && !(mask&valu);
>> mask >>= 1) continue;
>> return mask&valu;
>> }
>
> Well, I'll be go to COBOL. A minor tweak just occurred to me.
>
> unsigned long long int msb_mask(unsigned long long int valu)
> {
> unsigned long long int mask;
>
> for (mask = ((ULLONG_MAX) ^ (ULLONG_MAX >> 1));
> mask && !(mask&valu);
> mask >>= 1) continue;
> return mask; /* don't need to AND with valu now */
> }

This function depends on the type by using ULLONG_MAX. It is
easy though to make it not depend on that, and so to work
with an arbitrary unsigned type T:

T
msb_mask_revised( T value ){
T ones = -1, mask = ones ^ ones>>1;

while( mask && ! (mask & value) ) mask >>= 1;

return mask;
}

On 16/10/2023 13:26, Tim Rentsch wrote:
> Lew Pitcher <lew.pitcher@digitalfreehold.ca> writes:

>> Well, I'll be go to COBOL. A minor tweak just occurred to me.
>>
>> unsigned long long int msb_mask(unsigned long long int valu)
>> {
>> unsigned long long int mask;
>>
>> for (mask = ((ULLONG_MAX) ^ (ULLONG_MAX >> 1));
>> mask && !(mask&valu);
>> mask >>= 1) continue;
>> return mask; /* don't need to AND with valu now */
>> }
>
> This function depends on the type by using ULLONG_MAX. It is
> easy though to make it not depend on that, and so to work
> with an arbitrary unsigned type T:

If T has to be an unsigned type then it is not arbitrary!

Presumably you also want T to be a narrow type like u8 or u16, but I
can't see the point of this. It may mean extra masking operations to
truncate intermediate results. (Does it mean a shorter number of loop
iterations?)

However, how will a function such as the one below be used in practice:
will there be only the one such function in a program? Say, for T set to
unsigned short.

But then suppose the need comes up elsewhere for it to work on unsigned
long long; will there now be two versions, differently named, or just
one that does both?

I would be inclined to just write the one function anyway, working on
u64 that will accept any integer types, and possibly have a separate
version for a narrower type if that is considered to confer advantages.

In that case, there is no need for type-agnostic code.

>
> T
> msb_mask_revised( T value ){
> T ones = -1, mask = ones ^ ones>>1;
>
> while( mask && ! (mask & value) ) mask >>= 1;
>
> return mask;
> }
>

Michael S <already5chosen@yahoo.com> writes:

> On Mon, 16 Oct 2023 02:47:22 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Anton Shepelev <anton.txt@gmail.moc> writes:
>>
>>> Tim Rentsch:
>>>
>>>> Can you find a different solution that works in
>>>> logarithmic time rather than linear time?
>>>
>>> Direct linear search comes to mind. Instead of long long
>>> int below, use the widest integer type that your C
>>> environment supports:
>>>
>>> #define LLBM CHAR_BIT * sizeof( long long ) - 1
>>
>> The challenge is to write code that works without having to
>> know what that type is. The code you give relies on the type
>> directly by using ULLONG_MAX, and also indirectly by using the
>> above macro to calculate the number of bits in the type.
>> However the size of the type is not guaranteed to reflect
>> accurately how many value bits are available. If type T is an
>> unsigned type, we can get a value with all one bits easily:
>>
>> T ones = -1;
>>
>> To get the width of this value, let's postulate the existence
>> of a function (or macro) that calculates the width of such
>> values (that is, values that are one less than a power of two):
>>
>> unsigned width = MASK_WIDTH( ones );
>>
>> We could of course write a function that would compute such a
>> result, but we would like not to have to make a function call
>> at runtime. For the moment let's just assume we can do this.
>>
>>> unsigned long long int
>>> high_bit_mask( unsigned long long n )
>>> { unsigned long long m = ULLONG_MAX;
>>> int l = 0, r = LLBM+1;
>>> while( 1 )
>>> { const int ofs = (l + r) / 2;
>>> const unsigned long long mn = n & (m << LLBM - ofs);
>>>
>>> if( mn > 0 ) r = ofs;
>>> else if( mn == 0 ) l = ofs + 1;
>>> if( l == r ) break;
>>> }
>>> /* How can I avoid this condition? */
>>> return l == LLBM + 1 ? 0 : 1 << LLBM-l;
>>> }
>>
>> This code works but it strikes me as very busy; it seems to be
>> more cumbersome or cluttered than it needs to be. Using the
>> same basic approach of doing a binary search, here is a cleaner
>> and simpler version:
>>
>> T
>> highest_bit_set_revised( T n ){
>> T const ones = -1;
>> unsigned least = 0, limit = MASK_WIDTH( ones );
>>
>> do {
>> unsigned k = least+limit >> 1;
>> if( n & ones<<k ) least = k;
>> else limit = k;
>> } while( least+1 != limit );
>>
>> return n & ones<<least;
>> }
>>
>> To me this revision is a lot easier to read and understand.
>> What do you think about it?
>>
>> (PS: Explanation of MASK_WIDTH() macro to follow in a later
>> posting.)
>
> It works, but...

> [reordered]
> Second, your loop is 2-3 times slower then loops based Kaz's
> approach. 4-5 times slower than Kaz's non-loop code.

True. I was meaning only to clean up the function Anton posted,
not completely rewrite it. I'm saving my own writings for a
followon to the posting of your algorithm (which is the fastest
I have tested not counting ones I've written myself).

Note that Kaz's code doesn't solve the problem, because it
doesn't work for types of arbitrary width. To solve the
problem, there must be some kind of loop.

> First, you postulated that zero-run-time MASK_WIDTH() exist
> without actually writing such function. That sounds like
> cheating.

I did say an explanation would be forthcoming. Fasten your
seat belts...

#define MASK_WIDTH( m ) ( 0U + (unsigned)+( \
(m) /((m)%32767 +1) /32767 %32767 *15 \
+ (m) %32767 /((m)%31 +1) /31 %31 *5 \
+ 4 - 12 / ((m)%31 + 3) \
))

Truth in advertising: I make no claim of originality. I don't
even understand how it works exactly. But it does work, over a
very wide range, wide enough so that for practical purposes it
is unlimited.

This definition of MASK_WIDTH() results in compile-time constants
for the code above, under both gcc and clang, with -O1 (an up, I
presume), tested with type T up to 128 bits.

> Overall, C grade at best.

The above function isn't even close to my own best efforts.
Still gathering all that together for the aforementioned
followup.

James Kuyper wrote:

> On 10/15/23 13:18, Blue-Maned_Hawk wrote:
>> Tim Rentsch wrote:
>>
>>> The word obsolete means no longer used or no longer useful. If
>>> someone is still using it then by definition it is not obsolete.
>>
>> That is not my definition. I consider something obsolete when it has
>> been replaced.
>
> That's still not the case. C90 has not yet been fully replaced, not even
> by C99, much less by later versions - there's still people out there
> demanding implementations to support that version of the standard, and
> most do. C90 hasn't been the official C version as far as ISO is
> concerned for 24 years now, but as far as actual use of the language is
> concerned, C90 continues to be used in parallel with all of the other
> later versions.

C89 has been replaced by C99 and, nowadays, C11 and, soon, C23. If an
implentation is not updated, that is not an indication that the standard
is not yet obsolete. It is an indication that that implementation is
obsolete.

--

On 10/16/23 09:44, Blue-Maned_Hawk wrote:
....
> C89 has been replaced by C99 and, nowadays, C11 and, soon, C23. If an
> implentation is not updated, that is not an indication that the standard
> is not yet obsolete. It is an indication that that implementation is
> obsolete.

If the implementation is still in use by people who deliberately choose
it because they prefer the version of the standard that it implements,
it's not obsolete. I don't share that preference, but it is their
decision to make, not yours.

And regardless of whether or not you approve of that decision, the fact
that, every time a new version of the standard has come out, many people
wait for many years to adopt it, and as a result many implementations
delay implementing it, does affect the portability of code to those
implementations.

On Monday, October 16, 2023 at 4:01:49 PM UTC+3, Tim Rentsch wrote:
> Michael S <already...@yahoo.com> writes:
>
> > On Mon, 16 Oct 2023 02:47:22 -0700
> > Tim Rentsch <tr.1...@z991.linuxsc.com> wrote:
> >
> >> Anton Shepelev <anto...@gmail.moc> writes:
> >>
> >>> Tim Rentsch:
> >>>
> >>>> Can you find a different solution that works in
> >>>> logarithmic time rather than linear time?
> >>>
> >>> Direct linear search comes to mind. Instead of long long
> >>> int below, use the widest integer type that your C
> >>> environment supports:
> >>>
> >>> #define LLBM CHAR_BIT * sizeof( long long ) - 1
> >>
> >> The challenge is to write code that works without having to
> >> know what that type is. The code you give relies on the type
> >> directly by using ULLONG_MAX, and also indirectly by using the
> >> above macro to calculate the number of bits in the type.
> >> However the size of the type is not guaranteed to reflect
> >> accurately how many value bits are available. If type T is an
> >> unsigned type, we can get a value with all one bits easily:
> >>
> >> T ones = -1;
> >>
> >> To get the width of this value, let's postulate the existence
> >> of a function (or macro) that calculates the width of such
> >> values (that is, values that are one less than a power of two):
> >>
> >> unsigned width = MASK_WIDTH( ones );
> >>
> >> We could of course write a function that would compute such a
> >> result, but we would like not to have to make a function call
> >> at runtime. For the moment let's just assume we can do this.
> >>
> >>> unsigned long long int
> >>> high_bit_mask( unsigned long long n )
> >>> { unsigned long long m = ULLONG_MAX;
> >>> int l = 0, r = LLBM+1;
> >>> while( 1 )
> >>> { const int ofs = (l + r) / 2;
> >>> const unsigned long long mn = n & (m << LLBM - ofs);
> >>>
> >>> if( mn > 0 ) r = ofs;
> >>> else if( mn == 0 ) l = ofs + 1;
> >>> if( l == r ) break;
> >>> }
> >>> /* How can I avoid this condition? */
> >>> return l == LLBM + 1 ? 0 : 1 << LLBM-l;
> >>> }
> >>
> >> This code works but it strikes me as very busy; it seems to be
> >> more cumbersome or cluttered than it needs to be. Using the
> >> same basic approach of doing a binary search, here is a cleaner
> >> and simpler version:
> >>
> >> T
> >> highest_bit_set_revised( T n ){
> >> T const ones = -1;
> >> unsigned least = 0, limit = MASK_WIDTH( ones );
> >>
> >> do {
> >> unsigned k = least+limit >> 1;
> >> if( n & ones<<k ) least = k;
> >> else limit = k;
> >> } while( least+1 != limit );
> >>
> >> return n & ones<<least;
> >> }
> >>
> >> To me this revision is a lot easier to read and understand.
> >> What do you think about it?
> >>
> >> (PS: Explanation of MASK_WIDTH() macro to follow in a later
> >> posting.)
> >
> > It works, but...
> > [reordered]
> > Second, your loop is 2-3 times slower then loops based Kaz's
> > approach. 4-5 times slower than Kaz's non-loop code.
> True. I was meaning only to clean up the function Anton posted,
> not completely rewrite it. I'm saving my own writings for a
> followon to the posting of your algorithm (which is the fastest
> I have tested not counting ones I've written myself).
>
> Note that Kaz's code doesn't solve the problem, because it
> doesn't work for types of arbitrary width. To solve the
> problem, there must be some kind of loop.
> > First, you postulated that zero-run-time MASK_WIDTH() exist
> > without actually writing such function. That sounds like
> > cheating.
> I did say an explanation would be forthcoming. Fasten your
> seat belts...
>
> #define MASK_WIDTH( m ) ( 0U + (unsigned)+( \
> (m) /((m)%32767 +1) /32767 %32767 *15 \
> + (m) %32767 /((m)%31 +1) /31 %31 *5 \
> + 4 - 12 / ((m)%31 + 3) \
> ))
>
> Truth in advertising: I make no claim of originality. I don't
> even understand how it works exactly. But it does work, over a
> very wide range, wide enough so that for practical purposes it
> is unlimited.
>
> This definition of MASK_WIDTH() results in compile-time constants
> for the code above, under both gcc and clang, with -O1 (an up, I
> presume), tested with type T up to 128 bits.

Wow! That clever!

> > Overall, C grade at best.
> The above function isn't even close to my own best efforts.
> Still gathering all that together for the aforementioned
> followup.

James Kuyper wrote:

> If the implementation is still in use by people who deliberately choose
> it because they prefer the version of the standard that it implements,
> it's not obsolete. I don't share that preference, but it is their
> decision to make, not yours.

If they were to fork it and maintain their own version of that version of
the standard, then yes, it would not be obsolete, but it would also be a
dialect of C, not C itself, and therefore portability between it and C
can't ever be expected anyway.

--

On 16/10/2023 22:17, Blue-Maned_Hawk wrote:
> James Kuyper wrote:
>
>> If the implementation is still in use by people who deliberately choose
>> it because they prefer the version of the standard that it implements,
>> it's not obsolete. I don't share that preference, but it is their
>> decision to make, not yours.
>
> If they were to fork it and maintain their own version of that version of
> the standard, then yes, it would not be obsolete, but it would also be a
> dialect of C, not C itself, and therefore portability between it and C
> can't ever be expected anyway.
>

I can't find a way to interpret that which makes any practical sense.
Who is "they" here, and what is "it" which "they" might be forking? Are
you suggesting users (C programmers) fork the standards? Or that
compiler implementers should fork the users who want to maintain current
code bases with current languages?

On 10/16/23 16:17, Blue-Maned_Hawk wrote:
> James Kuyper wrote:
>
>> If the implementation is still in use by people who deliberately choose
>> it because they prefer the version of the standard that it implements,
>> it's not obsolete. I don't share that preference, but it is their
>> decision to make, not yours.
>
> If they were to fork it and maintain their own version of that version of
> the standard, then yes, it would not be obsolete, ...

Why would they need to fork it or maintain it? The version of C that
they want to code to has already been standardized, and they want to
adhere to that standard, not use it as a starting point for a new
version of C.

While some of them stick permanently to an older version of C (C90
remains "the only version of C" for a surprisingly large number of
people), most of them are merely putting off adopting the latest version
of the standard for a while. They're waiting till implementations have
worked out the bugs, until people with experience using the new standard
are available for hire, or until they've had time to consider carefully
how their code should be changed to make use of the new features.

And because there's always a fair number of people delaying use of the
new standard, there's a number of implementations delaying
implementation of it. As a result, this behavior reduces the portability
of code relying on the new features, regardless of whether or not you
approve of this behavior.

> ... but it would also be a
> dialect of C, not C itself,

It isn't the current standard version of C, but it is an older standard
version of C, not a non-standard dialect. Theoretically, newer versions
of the standard automatically superseded all older versions, but in the
real world, implementations conforming to superceded versions of the
standard have typically remained in use for many years (and in some
cases, for a few people, for decades) after it was superseded.

> ... and therefore portability between it and C
> can't ever be expected anyway.

Well, of course not. The reason they prefer using an older version of C
is that the newer version has some incompatibilities with it. If there
were no incompatibilities, there would be no reason not to use an
implementation of the newer version, and just avoid the features of that
version that they didn't want to use.

I want to emphasize again that I'm describing the attitude of other
people, one I don't share. I myself tend, to the extent possible, to be
an early adopter. I'm just pointing out that it is a perfectly
reasonable attitude, and regardless of whether you agree that it's
reasonable, one that affects the portability of code.

On 17/10/2023 06:39, James Kuyper wrote:
> On 10/16/23 16:17, Blue-Maned_Hawk wrote:
>> James Kuyper wrote:
>>
>>> If the implementation is still in use by people who deliberately choose
>>> it because they prefer the version of the standard that it implements,
>>> it's not obsolete. I don't share that preference, but it is their
>>> decision to make, not yours.
>>
>> If they were to fork it and maintain their own version of that version of
>> the standard, then yes, it would not be obsolete, ...
>
> Why would they need to fork it or maintain it? The version of C that
> they want to code to has already been standardized, and they want to
> adhere to that standard, not use it as a starting point for a new
> version of C.
>
> While some of them stick permanently to an older version of C (C90
> remains "the only version of C" for a surprisingly large number of
> people), most of them are merely putting off adopting the latest version
> of the standard for a while. They're waiting till implementations have
> worked out the bugs, until people with experience using the new standard
> are available for hire, or until they've had time to consider carefully
> how their code should be changed to make use of the new features.

I think you are missing one of the most important reasons people
continue to code to old C standards. (The reasons you give are
perfectly valid too.)

People rarely code in a vacuum. When you are writing code for yourself
at home, you can pick whatever standards and whatever tools you like.
But most programming is done in companies, in projects, in teams. And
most programming is done in continuations of existing code, not as a
fresh start. So how you code always involves some kinds of agreements
for consistency. That can mean simply agreeing on a standard, or
toolchains (maybe a range of versions, maybe a specific version), or
formal coding standards, or many other factors. Fixing on a particular
C standard version is often part of that, and it does not change easily.

Picture a company that has a software development group in charge of a
major product, written originally to C90. Along comes C99. Should they
change? Adopting C99 means:

* Group leaders need to study the new standard to learn about its pros
and cons.
* Support in new toolchains must be investigated.
* Any possible incompatibilities between the standards must be identified.
* The entire existing code base - with no single person being familiar
with it all - must be audited to check that there are no apparent problems.
* The code must be rebuild using C99 standard compilers. It needs full
and extensive testing - unit tests, system tests, regression tests, beta
tests at customer installations, etc.
* A team needs to identify which aspects of the new standards will be
taken in use, and which will be left out. They need to figure out if
these limits can be checked or enforced automatically (such as via
compiler error or warning flags).
* The company's coding standards need to be updated and re-written to
the new standard.
* Programmers in the department need training - both on what they can
now use, and what features of the new standard they are not allowed to
use in the code (or at least, not yet).
* All tools and procedures need to be updated to new toolchains and
build settings.
* A trial period is needed where extra care is used during development,
and extra checking is done, to consider whether the new features are a
good idea in practice or if things need to be revised again.
* A team needs to consider what existing code should be changed to make
use of new features, and what should be left unchanged. Possible
obsolescent code features would be planned for updates, and the balance
between the maintenance cost of mixed styles with the cost of re-writing
needs to be considered.
* In parallel to all this, which will take a significant time, other
team members must continue to work on the C90 branch of the code.

And what will be gained from moving to C99? IMHO it is a significantly
nicer language than C90. But for commercial programming, the cost of
changing can be enormous - are the benefits worth it in pure dollar
terms? The change is definitely /not/ just a matter of changing
"-std=c90" to "-std=c99" in the compiler settings. And "change to C99
and just don't use the new features you don't want" is not going to fly
in a team setting.

Basically, C90, C99 and C11 are important and not obsolete for the same
sorts of reasons COBOL and FORTRAN are important and not obsolete.

> I want to emphasize again that I'm describing the attitude of other
> people, one I don't share. I myself tend, to the extent possible, to be
> an early adopter. I'm just pointing out that it is a perfectly
> reasonable attitude, and regardless of whether you agree that it's
> reasonable, one that affects the portability of code.

I too like to use new standards and new features when I can. In my
company, programming is a lot more individualistic than I described
above as the programs are far smaller. But within a project, we would
need very powerful reasoning to change C standards (and I have a couple
of projects that span over 20 years). We also don't change toolchain
versions in a running project unless it is absolutely necessary.

Michael S to Tim Rentsch:

> First, you postulated that zero-run-time MASK_WIDTH()
> exist without actually writing such function. That sounds
> like cheating.

Or an exercise for the reader.

> Second, your loop is 2-3 times slower then loops based
> Kaz's approach.

I believe Tim wanted to improve my approach without
completely redesigning it.

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

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.

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

It does not work with `long long' in my environment, so I
post the code for `long'. This is the cleanest binary
search vesion that I can think of.

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

On 17/10/2023 16:33, Anton Shepelev wrote:
> 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.
>
> 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;
> }
>
> It does not work with `long long' in my environment, so I
> post the code for `long'. This is the cleanest binary
> search vesion that I can think of.

The choice of 'long' for a function such as this is odd. Because its
width is so variable:

32 64 Platform bits
---------------------
Windows 32 32 'long' bits
Linux 32 64

Presumably your environment is a 32-bit one where C does not support
64-bit intgers?

On Fri, 13 Oct 2023 20:12:45 -0000 (UTC), LO AND BEHOLD; vallor
<vallor@cultnix.org> determined that the following was of great
importance and subsequently decided to freely share it with us in
<ugc8bs$3bvcj$1@dont-email.me>:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= On Thu, 12 Oct 2023 13:42:03 -0000 (UTC), Blue-Maned_Hawk
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= <bluemanedhawk@invalid.invalid> wrote in
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= <pan$325f3$70a576a8$3150c04a$26db7b31@invalid.invalid>:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Keith Thompson wrote:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= A solution that depends on a header that's introduced in C23, a standard
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= that hasn't been published yet, is hardly portable.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Well, it will be in 2024.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= BTW, here's what your signature looks like in my newsreader (Gnus):
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Blue-Maned_HawkÃ\203\203\203\203Ã\203\203\202Ã\203\202Ã\202¢
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= \224\202shortens
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= to HawkÃ\203\203\203\203Ã\203\203\202Ã\203\202Ã\202¢\224\202/
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= blu.mÃ\203\203\203\203\211\233in.dÃ\203\203\203\203\212Ã\203\203\203\
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= 202Ã\203\203\202Ã\203\202Ã\202°ak/
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Ã\203\203\203\203Ã\203\203\202Ã\203\202Ã\202¢\224\202he/him/his/
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= himself/Mr.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= bluemanedhawk.github.io Minor vehicular events! And in Thunderbird:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Blue-Maned_HawkÃÃÃâshortens to HawkÃÃÃâ/
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= blu.mÃin.dÃÃÃÃðak/ ÃÃÃâhe/him/his/himself/Mr.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= bluemanedhawk.github.io Minor vehicular events!
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Blame Pan for corrupting it. That was meant to have its fields
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= separated by the │ character, including a pronunciation explanation
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= =?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= field that has IPA characters in it.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= (followup-to: news.software.readers)
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= I doubt Pan is to blame, but if it is, let's get a patch in to the
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= maintainers.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= Some folks have offered to help with your sig. I'm willing to help as
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= time allows, but you have to be willing to put in the time to stop
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= posting mojibakes. :/
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= If you're shy about email, please come visit news.software.readers,
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= where you will find the thread "Usenet characters".
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= The article where I post the relevant RFC quotes, cites, and maybe a
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= little shade on non-compliant newsreaders; can be found in article:
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= <zDOJM.1001200$TPw2.839294@fx17.iad>
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?= I've set the fu2 in this article to news.software.readers.
=?UTF-8?B?8J+Ps++4j+KAjfCfjIg=?=

You're still fucking crying about emojis, Scott?

--

Golden Killfile, June 2005
KOTM, November 2006
Bob Allisat Memorial Hook, Line & Sinker, November 2006
Special Ops Cody Memorial Purple Heart, November 2006
Special Ops Cody Memorial Purple Heart, September 2007
Tony Sidaway Memorial "Drama Queen" Award, November 2006
Busted Urinal Award, April 2007
Order of the Holey Sockpuppet, September 2007
Barbara Woodhouse Memorial Dog Whistle, September 2006
Barbara Woodhouse Memorial Dog Whistle, April 2008
Tinfoil Sombrero, February 2007
AUK Mascot, September 2007
Putting the Awards Out of Order to Screw With the OCD Fuckheads, March 2016

David Brown wrote:

> On 16/10/2023 22:17, Blue-Maned_Hawk wrote:
>> James Kuyper wrote:
>>
>>> If the implementation is still in use by people who deliberately
>>> choose it because they prefer the version of the standard that it
>>> implements, it's not obsolete. I don't share that preference, but it
>>> is their decision to make, not yours.
>>
>> If they were to fork it and maintain their own version of that version
>> of the standard, then yes, it would not be obsolete, but it would also
>> be a dialect of C, not C itself, and therefore portability between it
>> and C can't ever be expected anyway.
>>
>>
> I can't find a way to interpret that which makes any practical sense.
> Who is "they" here, and what is "it" which "they" might be forking? Are
> you suggesting users (C programmers) fork the standards? Or that
> compiler implementers should fork the users who want to maintain current
> code bases with current languages?

I was referring to the forking of the C language.

--

James Kuyper wrote:

> On 10/16/23 16:17, Blue-Maned_Hawk wrote:
>> James Kuyper wrote:
>>
>>> If the implementation is still in use by people who deliberately
>>> choose it because they prefer the version of the standard that it
>>> implements, it's not obsolete. I don't share that preference, but it
>>> is their decision to make, not yours.
>>
>> If they were to fork it and maintain their own version of that version
>> of the standard, then yes, it would not be obsolete, ...
>
> Why would they need to fork it or maintain it? The version of C that
> they want to code to has already been standardized, and they want to
> adhere to that standard, not use it as a starting point for a new
> version of C.

They would need to fork it if they want any maintainence. They would need
maintainence because times and needs are in an unstoppable state of flux.

> While some of them stick permanently to an older version of C (C90
> remains "the only version of C" for a surprisingly large number of
> people), most of them are merely putting off adopting the latest version
> of the standard for a while. They're waiting till implementations have
> worked out the bugs, until people with experience using the new standard
> are available for hire, or until they've had time to consider carefully
> how their code should be changed to make use of the new features.

Within reason, that seems completely reasonable.

> And because there's always a fair number of people delaying use of the
> new standard, there's a number of implementations delaying
> implementation of it. As a result, this behavior reduces the portability
> of code relying on the new features, regardless of whether or not you
> approve of this behavior.

Well, if their adoptation of the newest standard is, albeit delayed,
inevitable, i seen't a reason to worry.

--

Blue-Maned_Hawk <bluemanedhawk@invalid.invalid> writes:
> James Kuyper wrote:
[...]
>> Why would they need to fork it or maintain it? The version of C that
>> they want to code to has already been standardized, and they want to
>> adhere to that standard, not use it as a starting point for a new
>> version of C.
>
> They would need to fork it if they want any maintainence. They would need
> maintainence because times and needs are in an unstoppable state of flux.
[...]

If you're talking about maintenance of the implementation, C
implementations that support older editions of the C standard
typically provide maintenance. For example, the latest versions
of gcc and clang continue to support C90, C99, C11, et al.

If you're talking about maintenance *of the standard*, there's no
reason that would be necesssary. If a project is using C90, it
will continue to use C90 until and unless there's a need to move
to C99 or later. It wouldn't make sense to take a copy of the C90
standard and make local modifications to it.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

Keith Thompson wrote:

> If you're talking about maintenance *of the standard*, there's no reason
> that would be necesssary. If a project is using C90, it will continue
> to use C90 until and unless there's a need to move to C99 or later. It
> wouldn't make sense to take a copy of the C90 standard and make local
> modifications to it.

Why not?

--

On 10/17/23 16:38, Blue-Maned_Hawk wrote:
> James Kuyper wrote:
....
>> Why would they need to fork it or maintain it? The version of C that
>> they want to code to has already been standardized, and they want to
>> adhere to that standard, not use it as a starting point for a new
>> version of C.
>
> They would need to fork it if they want any maintainence. They would need
> maintainence because times and needs are in an unstoppable state of flux.

But why would it need maintenance? A small minority of these people
never intend to change which version of C they will use, the vast
majority will migrate to later versions of the standard when they're
ready, but there's no suggestion that any changes be made to the version
of C that they are using.

>> While some of them stick permanently to an older version of C (C90
>> remains "the only version of C" for a surprisingly large number of
>> people),

Note: in this context, I consider any number greater than 0 to be
"surprisingly large". The actual number I've observed is 5, but that's
just a biased sample of what I suspect is a significantly larger population.

....
>> And because there's always a fair number of people delaying use of the
>> new standard, there's a number of implementations delaying
>> implementation of it. As a result, this behavior reduces the portability
>> of code relying on the new features, regardless of whether or not you
>> approve of this behavior.
>
> Well, if their adoptation of the newest standard is, albeit delayed,
> inevitable, i seen't a reason to worry.

That isn't the case for the 5 people I know of who never intend to move
on from C90, but I still don't see a reason to worry.

On 17/10/2023 22:35, Blue-Maned_Hawk wrote:
> David Brown wrote:
>
>> On 16/10/2023 22:17, Blue-Maned_Hawk wrote:
>>> James Kuyper wrote:
>>>
>>>> If the implementation is still in use by people who deliberately
>>>> choose it because they prefer the version of the standard that it
>>>> implements, it's not obsolete. I don't share that preference, but it
>>>> is their decision to make, not yours.
>>>
>>> If they were to fork it and maintain their own version of that version
>>> of the standard, then yes, it would not be obsolete, but it would also
>>> be a dialect of C, not C itself, and therefore portability between it
>>> and C can't ever be expected anyway.
>>>
>>>
>> I can't find a way to interpret that which makes any practical sense.
>> Who is "they" here, and what is "it" which "they" might be forking? Are
>> you suggesting users (C programmers) fork the standards? Or that
>> compiler implementers should fork the users who want to maintain current
>> code bases with current languages?
>
> I was referring to the forking of the C language.
>

And who is "they" ? The people writing the implementations?

People who are interested in writing portable code aim to conform to
/standards/. They are not interested in forks of standards, because
that loses all the benefits - a fork of a standard is, obviously, not a
standard.

So no one is making forks of the C language, at least in the sense
"LibreOffice started as a fork of OpenOffice" or the "fork this project"
option on github.

Many implementations do, for various reasons, have extensions to C
standard language and library. And these will be documented and
maintained by the implementation, and some users will rely on them (not
everyone writes fully portable code). But these are not forks of the C
language or C standards - they are extensions, mostly orthogonal to the
standards (they are generally available whatever language standard you
pick).

None of that influences whether or not older C standards are obsolete.
As long as there are supporting toolchains, relevant code, and
non-negligible numbers of users working with the older standards, they
are not obsolete.

On 18/10/2023 11:52, David Brown wrote:
> On 17/10/2023 22:35, Blue-Maned_Hawk wrote:
>> David Brown wrote:
>>
>>> On 16/10/2023 22:17, Blue-Maned_Hawk wrote:
>>>> James Kuyper wrote:
>>>>
>>>>> If the implementation is still in use by people who deliberately
>>>>> choose it because they prefer the version of the standard that it
>>>>> implements, it's not obsolete. I don't share that preference, but it
>>>>> is their decision to make, not yours.
>>>>
>>>> If they were to fork it and maintain their own version of that version
>>>> of the standard, then yes, it would not be obsolete, but it would also
>>>> be a dialect of C, not C itself, and therefore portability between it
>>>> and C can't ever be expected anyway.
>>>>
>>>>
>>> I can't find a way to interpret that which makes any practical sense.
>>> Who is "they" here, and what is "it" which "they" might be forking?  Are
>>> you suggesting users (C programmers) fork the standards?  Or that
>>> compiler implementers should fork the users who want to maintain current
>>> code bases with current languages?
>>
>> I was referring to the forking of the C language.
>>
>
> And who is "they" ?  The people writing the implementations?
>
> People who are interested in writing portable code aim to conform to
> /standards/.  They are not interested in forks of standards, because
> that loses all the benefits - a fork of a standard is, obviously, not a
> standard.
>
> So no one is making forks of the C language, at least in the sense
> "LibreOffice started as a fork of OpenOffice" or the "fork this project"
> option on github.
>
> Many implementations do, for various reasons, have extensions to C
> standard language and library.  And these will be documented and
> maintained by the implementation, and some users will rely on them (not
> everyone writes fully portable code).  But these are not forks of the C
> language or C standards

So what does a fork of C look like?

Michael S <already5chosen@yahoo.com> writes:

> On Thu, 12 Oct 2023 08:05:40 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>> On Thu, 12 Oct 2023 07:01:47 -0700
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> [non-working example]
>>>
>>> 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?
>
> Naturally, I can. But the code is not as easy to comprehend as I
> would like. And I am not sure that for typical distributions with
> prevalence of small numbers it is faster than above variant.

I agree that whether a particular method is acceptably fast
depends on the expected distribution of inputs, and also on
the sizes of the types involved. For 8 or 16 bit inputs,
probably even very simple schemes are just fine. But since
what was asked for is not to depend on the sizes, and nothing
was said about what the expected inputs would be, it's natural
to look for logarithmic solution, and try to make it as easy
to understand as we can.

> T
> highest_bit_set2( T u ){
> T v;
> for (int rshift = 0; (v = (u >> rshift) >> 1) != 0; rshift = rshift*2+1)
> u |= v;
> return u ^ (u>>1);
> }

I want to look at a lot of different approaches, but let me say
at the start that this method is very much like one I had coded
earlier, and the one you give here is pretty good. We'll get
back to this case later but let's start at the simple answers and
move on to the more elaborate ones.

Generally speaking there are two ways of getting a result,
namely, either look for the value or construct the value. Linear
methods tend to look for the result, either starting at the top
and scanning down, or starting at the bottom and scanning up
(which is what your first answer did). The poster jak gave a
nice function that is linear but of the constructive variety.
The next code is jak's except the layout is slightly different
and it uses the type T (stipulated to be unsigned) rather than a
putting in a particular definite type.

T
hbs_jak( T val ){
int i;
for( i = 0; val > 1; val /= 2, i++ );
return val << i;
}

This function nicely and naturally handles an input value of
zero, which is something to look for (that is, how a zero input
is handled) when considering high-bit-determining functions (for
the obvious reason that zero is kind of an oddball because it has
no bits set).

As mentioned before your first answer is linear, and uses an
upward scan, and deals naturally with a zero input.

Thinking about the choice of scan direction, it occurred to me
that rather than start at one end or the other, we could start in
the middle, and do either an upward scan or a downward scan
depending on an initial test. I wrote this:

T
hbs_split( T u ){
unsigned n = MASK_WIDTH( 0?u:-1 )/2;
T v = u>>1;
T bit = (0?bit:1) << n;
if( bit > u ) do bit >>= 1; while( bit > u );
else while( bit <= v ) bit <<= 1;
return bit;
}

If the inputs are evenly distributed this function should on average
be about twice as fast as a single-direction scan.

In between linear and logarithmic, there is a well-known sublinear
technique that I was half expecting someone would post. Besides
being a little faster than a straight linear scan, it has the nice
property that the code is very simple:

T
hbs_zap_low_bit( T u ){
while( u & u-1 ) u &= u-1;
return u;
}

The loop takes time proportional to the number of one bits (so
strictly speaking it is not sublinear, but still faster than
other linear methods). This function runs as fast or faster than
all the other non-logarithmic methods I tried. (I did simple
performance measurements with an input set of all values between
0 and 300,000,000, for each of three type sizes, those being 32,
64, and 128 bits.)

On the subject of performance, the various functions being posted
are given roughly in performance order, slowest first and getting
faster as we go on.

Now we have arrived at the logarithmic methods. Anton posted a
method using binary search (but using a specific type), which I
revised to be type-agnostic:

T
hbs_binary_search( T n ){
T const ones = -1;
unsigned least = 0, limit = MASK_WIDTH( ones );

do {
unsigned k = least+limit >> 1;
if( n & ones<<k ) least = k;
else limit = k;
} while( least+1 != limit );

return n & ones<<least;
}

After doing this version I had the idea of doing a more careful
binary search, which would detect the case of having found an
result and exit the loop immediately. That idea yielded this
function:

T
hbs_binary_search_with_early_exit( T x ){
unsigned t = MASK_WIDTH( (T)-1 ) +1, s = t/2, u = t-s-1;
T y = (0?y:1) << u-1, z = x >> 1;;

do {} while(
t < 2 ? 0 :
y <= z ? t = s, u = t/2, s = t-u-1, y <<= u+1 :
y > x ? t = u, s = t/2, u = t-s-1, y >>= s+1 :
/********/ 0
);

return y;
}

To see how this works, at each step there are 't' bits total, with
's' bits to the left of the bit under test, and 'u' bits to the
right, so t = s+u+1. The variable 'x' holds the input value, 'z'
holds the input value shifted right one, and 'y' holds the one-bit
value being checked. Thus if x >= y and y > z, y is the answer.
Writing the function was an exercise in careful bookkeeping, and
not easy to write - it took me about half a dozen tries before I
got it right. And, sadly, not really any better than the simple
binary search. But it was fun to try.

Next we get to your first logarithmic version (namely, the one given
in the post being responded to here), which gives appreciably better
speed than the binary searches. This function uses the "expanding
bit-smearing" technique, and is similar to a method I had written,
which went through several revisions, as follows:

T
hbs_expanding_smearing_1( T u ){
unsigned shift = 1;
while( (u & u>>1) != u>>1 ) u |= u>>shift, shift += shift;
return u ^ u>>1;
}

T
hbs_expanding_smearing_2( T u ){
unsigned shift = 1;
do u |= u>>shift, shift <<= 1; while( (u & u>>1) != u>>1 );
return u ^ u>>1;
}

T
hbs_expanding_smearing_3( T u ){
T r;

for(
unsigned s = 1;
u |= u>>s, r = u ^ u>>1, r & r-1;
s <<= 1
){}

return r;
}

One can see the progression of putting the smearing earlier in the
sequence of operations. The motivation to change from a 'do' to a
'for' is so changing the shift amount could be done only after we
know we are getting to the next (half) loop iteration. All of these
ran a bit faster than your first logarithmic versioon. (I should
say again that my performance measurements were done more casually
than carefully.)

Then you posted a revised version of your first logarithmic effort:

T
hbs_michael_s_2_revised( T u ){
for (int rshift = 1; ((u+1) & u) != 0; rshift += rshift)
u |= (u >> rshift);
return u ^ (u>>1);
}

Nice! This revision runs about the same speed as the fastest of the
three functions above (the third one). I think a lot of that
improvement is a consequence of the simple exit test in the for()
loop. Seeing that inspired me to re-do my earlier version, giving
this:

T
hbs_expanding_smearing_with_michael_s_exit_test( T u ){
for(
unsigned s = 1;
u |= u>>s, u+1 & u;
s <<= 1
){}

return u ^ u>>1;
}

This revision runs about 15% faster than the _3 version above. I
attribute all of the gain to using your simplified loop exit test.