jak <nospam@please.ty> writes:

> Tim Rentsch ha scritto:

[considering the problems of non-powers-of-two sizes]

> #include <limits.h>
>
> typedef unsigned long T;
>
> T h_bit(T val)
> {
> int tbits = 0, bits = (sizeof(val) * CHAR_BIT) / 2;
> for(; bits > 0; bits /= 2)
> if((((T)-1) << bits) & val)
> {
> val >>= bits;
> tbits += bits;
> }
> for(; val > 1; val /= 2, tbits++);
> return val << tbits;
> }
>
> In this way it also works with char_bit == 12 and for any value it
> performs:
> 3 Interactions per data 1 byte wide.
> +1 When the width doubles (e.g. 6 for 8 bytes).
> +1 if CHAR_BIT == 12.
> If there is no something that halves these timing, given its
> simplicity I remain happy.

Two problems: it isn't obvious what the performance costs of
this scheme are, and clearly it may do more shifts than it
needs to. The problem is easy to fix, so let's just fix it.

T
h_bit( T v ){
T ones = -1;
unsigned w = ALL_ONES_WIDTH( ones );
unsigned shift = largest_power_of_two_less_than( w );
T mask = ones >> w-shift;
unsigned total_shift = 0;

do {
if( v > mask ){
v >>= shift;
total_shift += shift;
}
} while( shift /= 2, mask >>= shift, shift > 0 );

return v << total_shift;
}

Here ALL_ONES_WIDTH is just a different name for the MASK_WIDTH
macro I showed before (and is better than multiplying CHAR_BIT
times sizeof (T), which might not give the right answer):

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

Yes, it's complicated, but the point of abstraction is it isn't
necessary to understand how something works when it is abstracted
away.

All that's left is the largest_power_of_two_less_than() function:

unsigned
largest_power_of_two_less_than( unsigned n ){
unsigned s, t = 1;

do s = t, t <<= 1; while( t < n );

return n > 1 ? s : 0;
}

Easy as falling off a log. Also it isn't hard to write a macro
that does the same thing, at compile time, for all practical
values of widths (corresponding to the parameter n). Doing
that means the initialization of 'shift' is done with a
compile-time constant.

Blue-Maned_Hawk <bluemanedhawk@invalid.invalid> writes:
> 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.

If someone is still using it, then it has not been replaced, and thus by
your definition it's not obsolete.

You are confusing "has been replaced" with "newer alternatives
exist". They are different concepts.

Phil
--
We are no longer hunters and nomads. No longer awed and frightened, as we have
gained some understanding of the world in which we live. As such, we can cast
aside childish remnants from the dawn of our civilization.
-- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/

Michael S <already5chosen@yahoo.com> writes:

> On Sun, 22 Oct 2023 09:25:45 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

[...]

>> Incidentally, I found the default number of iterations in the tool
>> to be too low to give reliable indicators of performance. I ended
>> up using about 2000 iterations, which gave pretty steady results.
>
> Most likely, you computer was heavily loaded with other jobs.
> On idle computer median should stabilaze much sooner.

The processor is not otherwise loaded. Remember, I am looking
for the effects of small changes, where the difference may be
noticeably less than 10%. At 13 iterations it isn't unusual to
see fluctuations of more than 20%.

[...]

>> End result, my sense is that the fastest method is likely to be
>> platform specific, and probably needs to be coded in assembly.
>
> Intrinsic functions should be as fast as asm.
> With gcc - __builtin_clz() family. It does not belong to the
> realm of portable C, but still is much more portable than asm.
> And arguably still on topic in this group, if not in this thread.

I tend to think of intrinsics like __builtin_clz() as assembler
in disguise. However it is true that they are more portable
than assembler, when and where they are available, and depending
on what types are supported.

[...]

>> My comment upthread is about scaling. As the size gets bigger,
>> the method of oring with ever-increasing shift amounts is doomed,
>> because it's an O(N*log(N)) algorithm, but the problem can be
>> solved in O(N). My sense is that 128 bits is close to the
>> crossover, and maybe even is the crossover if we were writing in
>> assembly rather than C. And now that I've said that, it's time
>> to abandon the discussion, since it is now no longer topical in
>> a C newsgroup. :)
>
> As to your suggestion that the problem can be solved in O(N) time,
> right now, at night, I can only think of sort of O(N) solutions
> that exploit knowledge of internal representation of wide integer
> number, e.g. knowledge of its endiannes, either Little or Big.
> Which is not exactly portable.

If we wait until you have the benefit of some daylight thinking
hours I expect you will see how this can be done. (Disclaimer
and possible spoiler alert: strictly speaking there may be some
issues on implementations with integer types that have trap
representations. These days though I don't think any machines
even have any padding bits, let alone trap representations. Oh,
I have to take that back - I know of one contemporary machine
where unsigned types don't use the sign bit, and so have one
padding bit. In that case though there is enough information
so the padding bit is known, and potential trap representations
can be avoided.)

Phil Carmody wrote:

> You are confusing "has been replaced" with "newer alternatives exist".

You are confusing alternatives with replacements.

--

On 2023-10-22, jak <nospam@please.ty> wrote:
> #include <limits.h>
>
> typedef unsigned long T;
>
> T h_bit(T val)
> {
> int tbits = 0, bits = (sizeof(val) * CHAR_BIT) / 2;
> for(; bits > 0; bits /= 2)
> if((((T)-1) << bits) & val)
> {
> val >>= bits;
> tbits += bits;
> }
> for(; val > 1; val /= 2, tbits++);
> return val << tbits;
> }

This is a nice approach if we are interested in the tbits value.

GCC does a good job of unrolling the looping. Only problem is, there
are branches:

E.g. x86 code with gcc 7.5:

h_bit:
movl 4(%esp), %eax
xorl %ecx, %ecx
testl $-65536, %eax
je .L2
shrl $16, %eax
movl $16, %ecx
..L2:
testl $-256, %eax
je .L3
shrl $8, %eax
addl $8, %ecx
..L3:
testl $-16, %eax
je .L4
shrl $4, %eax
addl $4, %ecx
..L4:
testl $-4, %eax
je .L5
shrl $2, %eax
addl $2, %ecx
..L5:
testl $-2, %eax
je .L6
addl $1, %ecx
movl $1, %eax
..L6:
sall %cl, %eax
ret

(Also, note that the translated code shows that you have some
unnecessary details in the C code. If you reverse engineer
the code back to C, you will get better C. Your second for
loop disappeared entirely.)

Let's look at the code I posted a while ago:

unsigned long fill_mask_down(unsigned long x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;

#if UINT_MAX == UINT32_MAX
x |= x >> 16;
#elif UINT_MAX == UINT64_MAX
x |= x >> 16;
x |= x >> 32;
#elif UINT_MAX != UINT16_MAX
#error port me!
#endif

return x;
}

unsigned long isolate_highest_bit(unsigned long x)
{
unsigned long m = fill_mask_down(x);
return m ^ (m >> 1);
}

This leads to a single branch-free basic block:

isolate_highest_bit:
movl 4(%esp), %edx
movl %edx, %eax
shrl %eax
orl %edx, %eax
movl %eax, %edx
shrl $2, %edx
orl %edx, %eax
movl %eax, %edx
shrl $4, %edx
orl %edx, %eax
movl %eax, %edx
shrl $8, %edx
orl %edx, %eax
movl %eax, %edx
shrl $16, %edx
orl %edx, %eax
movl %eax, %edx
shrl %edx
xorl %edx, %eax
ret

This doesn't require branch prediction or speculative execution to go
fast.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

On 2023-10-23, Phil Carmody <pc+usenet@asdf.org> wrote:
> Blue-Maned_Hawk <bluemanedhawk@invalid.invalid> writes:
>> 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.
>
> If someone is still using it, then it has not been replaced, and thus by
> your definition it's not obsolete.
>
> You are confusing "has been replaced" with "newer alternatives
> exist". They are different concepts.

The problem with a purely use-based definition of obsolescence is that
all sorts of dead obsolete cruft is still in use by someone.

For instance, steam locomotives are still running in places, thus
the steam locomotive isn't obsolete?

Obsolescence is a somewhat broad topic with fuzzy edges.

Let's get one form of obsolescence out of the way: a form of artistic
expression or style is obsolete when all new manifestations of it are
recognized as references to, imitations/parodies of, or homages to that
form's original era, and this aspect of the works interferes with or
occludes consideration of their inherent originality.

I have a sense that this discussion has been about the economic
obsolescence of something practical, like a technology.

Old technologies can be in use, yet obsolete. Someone somewhere is
operating a server on a DEC MicroVAX. Yet that machine is obsolete.

Roughly, a tangible product is obsolete when it is no longer made.

So there are probably people in the world who are becoming new owners of
DEC MicroVAXen. But each time that happens, someone simultaneously stops
being an owner. In other words, trade of DEC MicroVAXen is closed
system in which ecnonomic production isn't taking place. It's a
backwards-looking retro-computing hobby.

Not only are those machines not made, but the ecosystem for making them
isn't there. If you wanted to make an exact replica of that machine, you
would have a hard time sourcing new parts. Same with steam locomotives.
Someone building a replica of a locomotive from 1900 would have to
produce their own parts. Scavenged parts from an existing such
locomotive don't count as new production; that's a rebuild.

Talk was made in this thread about whether to make C code portable to
obsolete systems, which means installations of old machines running old
operating systems.

Economically, it is poorly justified. The users of those systems are
mainly interested in the original software. Some such systems run
in the proverbial corner, serving some role. People in the surrouding
organization have their fingers crossed. Some have their fingers crossed
that the machine will not die today. Others have their fingers crossed
that it does. Neither group wants to put a new C program on it.

(There is some retrocomputing activity whereby new software titles are
written for old machines: such a new games for old eight bit
microcomputers. Those games can run on new machines emulation, so the
games themselves might nto be obsolete.)

There was talk in this thread about using old C dialects: are they
obsolete.

I would say this: that if you're actually using a 30-year-old compiler
binary to build your C90 code, then you're targetting an obsolete
implementation.

If the only way you can use a programming language is via an old
computer system, then it's probably obsolete. Dead programming languages
can be revived much more easily than dead human languages though,
and it's possible to ship a new, working solution in them.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
[...]
> If we wait until you have the benefit of some daylight thinking
> hours I expect you will see how this can be done. (Disclaimer
> and possible spoiler alert: strictly speaking there may be some
> issues on implementations with integer types that have trap
> representations. These days though I don't think any machines
> even have any padding bits, let alone trap representations. Oh,
> I have to take that back - I know of one contemporary machine
> where unsigned types don't use the sign bit, and so have one
> padding bit. In that case though there is enough information
> so the padding bit is known, and potential trap representations
> can be avoided.)

Which contemporary machine is that?

--
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 */

Tim Rentsch ha scritto:
> jak <nospam@please.ty> writes:
>
>> Tim Rentsch ha scritto:
>
> [considering the problems of non-powers-of-two sizes]
>
>> #include <limits.h>
>>
>> typedef unsigned long T;
>>
>> T h_bit(T val)
>> {
>> int tbits = 0, bits = (sizeof(val) * CHAR_BIT) / 2;
>> for(; bits > 0; bits /= 2)
>> if((((T)-1) << bits) & val)
>> {
>> val >>= bits;
>> tbits += bits;
>> }
>> for(; val > 1; val /= 2, tbits++);
>> return val << tbits;
>> }
>>
>> In this way it also works with char_bit == 12 and for any value it
>> performs:
>> 3 Interactions per data 1 byte wide.
>> +1 When the width doubles (e.g. 6 for 8 bytes).
>> +1 if CHAR_BIT == 12.
>> If there is no something that halves these timing, given its
>> simplicity I remain happy.
>
> Two problems: it isn't obvious what the performance costs of
> this scheme are, and clearly it may do more shifts than it
> needs to. The problem is easy to fix, so let's just fix it.
>
> T
> h_bit( T v ){
> T ones = -1;
> unsigned w = ALL_ONES_WIDTH( ones );
> unsigned shift = largest_power_of_two_less_than( w );
> T mask = ones >> w-shift;
> unsigned total_shift = 0;
>
> do {
> if( v > mask ){
> v >>= shift;
> total_shift += shift;
> }
> } while( shift /= 2, mask >>= shift, shift > 0 );
>
> return v << total_shift;
> }
>
> Here ALL_ONES_WIDTH is just a different name for the MASK_WIDTH
> macro I showed before (and is better than multiplying CHAR_BIT
> times sizeof (T), which might not give the right answer):
>
> #define ALL_ONES_WIDTH( m ) ( 0U + (unsigned)+( \
> (m) /((m)%32767 +1) /32767 %32767 *15 \
> + (m) %32767 /((m)%31 +1) /31 %31 *5 \
> + 4 - 12 / ((m)%31 + 3) \
> ))
>
> Yes, it's complicated, but the point of abstraction is it isn't
> necessary to understand how something works when it is abstracted
> away.
>
> All that's left is the largest_power_of_two_less_than() function:
>
> unsigned
> largest_power_of_two_less_than( unsigned n ){
> unsigned s, t = 1;
>
> do s = t, t <<= 1; while( t < n );
>
> return n > 1 ? s : 0;
> }
>
> Easy as falling off a log. Also it isn't hard to write a macro
> that does the same thing, at compile time, for all practical
> values of widths (corresponding to the parameter n). Doing
> that means the initialization of 'shift' is done with a
> compile-time constant.
>

I read, appreciated and I consider your explanation valid, so much so
that I wanted to compare our solutions (main recall function 10000
times). I copied my source file and replaced your solution to mine. I
had a surprise because I expected the opposite:

$ gcc jak.c -o jak
$ gcc tim.c -o tim

$ jak
val = 0x00000000FFFFFFFF
ret = 0x0000000080000000
Time measured: 0.000180 seconds.
$ tim
val = 0x00000000FFFFFFFF
ret = 0x0000000080000000
Time measured: 0.000582 seconds.

$ gcc jak.c -Ofast -o jak
$ gcc tim.c -Ofast -o tim

$ jak
val = 0x00000000FFFFFFFF
ret = 0x0000000080000000
Time measured: 0.000001 seconds.
$ tim
val = 0x00000000FFFFFFFF
ret = 0x0000000080000000
Time measured: 0.000065 seconds.

I don't know how to explain it. Maybe the optimizer manages my version
better.

Kaz Kylheku <864-117-4973@kylheku.com> writes:

> On 2023-10-15, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Kaz Kylheku <864-117-4973@kylheku.com> writes:
>>
>>> On 2023-10-11, Kaz Kylheku <864-117-4973@kylheku.com> wrote:
>>>
>>>> E.g. 32 bit code:
>>>>
>>>> uint32_t fill_mask_down(uint32_t x)
>>>> {
>>>> x |= x >> 1; // e.g. 1000...0000 -> 1100...0000
>>>> x |= x >> 2; // e.g. 1100...0000 -> 1111...0000
>>>> x |= x >> 4; // e.g. 11110000... -> 11111111...
>>>> x |= x >> 8;
>>>> x |= x >> 16;
>>>>
>>>> return x;
>>>> }
>>>>
>>>> Thus:
>>>>
>>>> uint32_t isolate_highest_bit(uint32_t x)
>>>> {
>>>> uint32_t m = fill_mask_down(x);
>>>> return m ^ (m >> 1);
>>>> }
>>>
>>> I guess this went over people's heads?
>>
>> Not at all. It's a well-known technique. But it doesn't
>> address the central ask for an approach that works no
>> matter how wide the value type is.
>
> Oh, if I had to make it work with the unsigned long type, like the other
> solutions,

That is a misrepresentation.

> I'd probably just do this:
>
> unsigned long fill_mask_down(unsigned long x)
> {
> x |= x >> 1;
> x |= x >> 2;
> x |= x >> 4;
> x |= x >> 8;
>
> #if UINT_MAX == UINT32_MAX
> x |= x >> 16;
> [...]

The challenge is to find an algorithm that works
without being tied to a specific type. If you
aren't up to the task that's okay with me, but
don't pretend it's something it isn't. It's
always easier to find an answer if one is free
to change the question.

jak <nospam@please.ty> writes:

> Tim Rentsch ha scritto:

[Tim presented an alternate implementation of jak's algorithm.]

> I read, appreciated and I consider your explanation valid, so much
> so that I wanted to compare our solutions (main recall function
> 10000 times). I copied my source file and replaced your solution to
> mine. I had a surprise because I expected the opposite:
>
> $ gcc jak.c -o jak
> $ gcc tim.c -o tim
>
> $ jak
> val = 0x00000000FFFFFFFF
> ret = 0x0000000080000000
> Time measured: 0.000180 seconds.
> $ tim
> val = 0x00000000FFFFFFFF
> ret = 0x0000000080000000
> Time measured: 0.000582 seconds.
>
> $ gcc jak.c -Ofast -o jak
> $ gcc tim.c -Ofast -o tim
>
> $ jak
> val = 0x00000000FFFFFFFF
> ret = 0x0000000080000000
> Time measured: 0.000001 seconds.
> $ tim
> val = 0x00000000FFFFFFFF
> ret = 0x0000000080000000
> Time measured: 0.000065 seconds.
>
> I don't know how to explain it. Maybe the optimizer manages my
> version better.

I took our two implementations and plugged them into my measuring
setup based on Michael S's testbench.

First pass - mine was a lot worse. That wasn't surprising, since
what I posted calls a runtime function rather than using a scheme
to produce a compile time constant. Incidentally, all of my
tests were done on 128 bit integers (and that only because it was
more convenient for my testing setup than other widths).

Second pass - I plugged in the macro so my version calculated the
intial shift at compile time, making it more an apples-and-apples
comparison. Note by the way that the width involved are already
powers of two, so the sequence of shifts in the two versions will
be identical. Here are results from that run:

my-jak-runit-128
Generating 1000000 test points...done. 60.480 msec.
Throughput time (nsec) mean/med 26.572 / 26.429
Latency time (nsec) mean/med 26.676 / 26.579

jak-runit-128
Generating 1000000 test points...done. 63.289 msec.
Throughput time (nsec) mean/med 23.598 / 23.504
Latency time (nsec) mean/med 24.082 / 24.047

These results show the jak version runs between 10 and 13
percent faster than mine. That was kind of discouraging.

Third pass - I used the same code as in the second pass, but
compiled with clang instead of gcc. Here are results from that
run:

my-jak-runit-128
Generating 1000000 test points...done. 64.892 msec.
Throughput time (nsec) mean/med 8.538 / 8.462
Latency time (nsec) mean/med 11.092 / 11.074

jak-runit-128
Generating 1000000 test points...done. 63.851 msec.
Throughput time (nsec) mean/med 13.648 / 13.563
Latency time (nsec) mean/med 17.995 / 17.983

These results show both versions sped up a lot, but my version
sped up more than jak's, giving an overall result that my
version runs about 60% faster than the jak version.

These kinds of fluctuations were a major part of what motivated
me to stop exploring the different approaches.

On Mon, 23 Oct 2023 20:03:34 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Kaz Kylheku <864-117-4973@kylheku.com> writes:
>
> > On 2023-10-15, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> Kaz Kylheku <864-117-4973@kylheku.com> writes:
> >>
> >>> On 2023-10-11, Kaz Kylheku <864-117-4973@kylheku.com> wrote:
> >>>
> >>>> E.g. 32 bit code:
> >>>>
> >>>> uint32_t fill_mask_down(uint32_t x)
> >>>> {
> >>>> x |= x >> 1; // e.g. 1000...0000 -> 1100...0000
> >>>> x |= x >> 2; // e.g. 1100...0000 -> 1111...0000
> >>>> x |= x >> 4; // e.g. 11110000... -> 11111111...
> >>>> x |= x >> 8;
> >>>> x |= x >> 16;
> >>>>
> >>>> return x;
> >>>> }
> >>>>
> >>>> Thus:
> >>>>
> >>>> uint32_t isolate_highest_bit(uint32_t x)
> >>>> {
> >>>> uint32_t m = fill_mask_down(x);
> >>>> return m ^ (m >> 1);
> >>>> }
> >>>
> >>> I guess this went over people's heads?
> >>
> >> Not at all. It's a well-known technique. But it doesn't
> >> address the central ask for an approach that works no
> >> matter how wide the value type is.
> >
> > Oh, if I had to make it work with the unsigned long type, like the
> > other solutions,
>
> That is a misrepresentation.
>
> > I'd probably just do this:
> >
> > unsigned long fill_mask_down(unsigned long x)
> > {
> > x |= x >> 1;
> > x |= x >> 2;
> > x |= x >> 4;
> > x |= x >> 8;
> >
> > #if UINT_MAX == UINT32_MAX
> > x |= x >> 16;
> > [...]
>
> The challenge is to find an algorithm that works
> without being tied to a specific type. If you
> aren't up to the task that's okay with me, but
> don't pretend it's something it isn't. It's
> always easier to find an answer if one is free
> to change the question.

In my own tests I used following form of Kaz's algorithm:

T
highest_bit_set( T u ){
for (int k = 0; ((T)-1 >> ((1 <<k)-1)) > 1; ++k)
u |= u >> (1 << k);
return u ^ (u >> 1);
}

Both gcc -O3 and clang -O2 and -O3 translate it into the same object
code as manually written sequence.
Of course, this code works only for types with number of bits equal to
power of two. For my tests it was o.k. because my test platforms
have no other integer types anyway.

I was not able to generalize this loop for non-power-of-two. For
example, the variant below produces desired code with clang, but gcc12
generates loop instead of straight line.

T
highest_bit_set( T u ){
u |= u >> 1;
for (int k = 0; (((T)-1 >> (1<<k)) >> (1<<k)) != 0; ++k)
u |= u >> (1 << (k+1));
return u ^ (u >> 1);
}

I tried several other variations of this theme. Many were good for
neither compiler, many others only good for clang, one or two only good
for gcc, but none good for both.

Fortunately there is always a magic macro of yours. It works fine
with both compilers. May be, it has theoretical limits, but in practice
it is more than good enough.

T
highest_bit_set( T u ){
const int nbits = MASK_WIDTH((T)-1);
for (int k = 0; (1<<k) < nbits; ++k)
u |= u >> (1<<k);
return u ^ (u >> 1);
}

Michael S <already5chosen@yahoo.com> writes:

> On Mon, 23 Oct 2023 20:03:34 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> The challenge is to find an algorithm that works
>> without being tied to a specific type. [...]
>
> [an effort to generalize a type-specific function]
>
> T
> highest_bit_set( T u ){
> for (int k = 0; ((T)-1 >> ((1 <<k)-1)) > 1; ++k)
> u |= u >> (1 << k);
> return u ^ (u >> 1);
> }
>
> Both gcc -O3 and clang -O2 and -O3 translate it into the same object
> code as manually written sequence.

Great! That's cool.

> Of course, this code works only for types with number of bits
> equal to power of two. For my tests it was o.k. because my test
> platforms have no other integer types anyway.
>
> I was not able to generalize this loop for non-power-of-two. For
> example, the variant below produces desired code with clang, but
> gcc12 generates loop instead of straight line.
>
> T
> highest_bit_set( T u ){
> u |= u >> 1;
> for (int k = 0; (((T)-1 >> (1<<k)) >> (1<<k)) != 0; ++k)
> u |= u >> (1 << (k+1));
> return u ^ (u >> 1);
> }
>
> I tried several other variations of this theme. Many were good
> for neither compiler, many others only good for clang, one or two
> only good for gcc, but none good for both.

Try this:

T
highest_bit_set( T u ){
T one = 1, all = -one;
unsigned k, s;

u |= u>>1;
for( k = 0; s = 1<<k, all>>s > one<<s; k++ ){
u |= u >> s*2;
}

return u ^ (u >> 1);
}

With -O3 this works for me with both gcc and clang (both at least
several years old).

> Fortunately there is always a magic macro of yours.

Again, not mine. The original author was Hallvard Furuseth
(with my MASK_WIDTH() being a less ambitious version of his
IMAX_BITS()).

> It works
> fine with both compilers. May be, it has theoretical limits,
> but in practice it is more than good enough.
>
> T
> highest_bit_set( T u ){
> const int nbits = MASK_WIDTH((T)-1);
> for (int k = 0; (1<<k) < nbits; ++k)
> u |= u >> (1<<k);
> return u ^ (u >> 1);
> }

The version of MASK_WIDTH I posted tops out at 491504 bits.

If that's not enough, here is the original (my choice of layout,
wrapping, and using 'unsigned long' type, but otherwise the same):

#define IMAX_BITS(m) IMAX_BITS_((m))
#define IMAX_BITS_(m) ( \
m / (m%0x3fffffffUL+1) / 0x3fffffffUL % 0x3fffffffUL * 30 \
+ m%0x3fffffffUL / (m%31+1) / 31 % 31 * 5 \
+ 4 - 12/(m%31+3) \
)

This form is good (or so I understand) up to more than 30 billion
bits. I haven't tested it that high. :)

Original author: Hallvard Breien Furuseth<h.b.furuseth@usit.uio.no>

Reference in
http://www.stackprinter.com/export?question=3957252&service=stackoverflow

On Tue, 24 Oct 2023 07:35:02 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> > On Mon, 23 Oct 2023 20:03:34 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> The challenge is to find an algorithm that works
> >> without being tied to a specific type. [...]
> >
> > [an effort to generalize a type-specific function]
> >
> > T
> > highest_bit_set( T u ){
> > for (int k = 0; ((T)-1 >> ((1 <<k)-1)) > 1; ++k)
> > u |= u >> (1 << k);
> > return u ^ (u >> 1);
> > }
> >
> > Both gcc -O3 and clang -O2 and -O3 translate it into the same object
> > code as manually written sequence.
>
> Great! That's cool.
>
> > Of course, this code works only for types with number of bits
> > equal to power of two. For my tests it was o.k. because my test
> > platforms have no other integer types anyway.
> >
> > I was not able to generalize this loop for non-power-of-two. For
> > example, the variant below produces desired code with clang, but
> > gcc12 generates loop instead of straight line.
> >
> > T
> > highest_bit_set( T u ){
> > u |= u >> 1;
> > for (int k = 0; (((T)-1 >> (1<<k)) >> (1<<k)) != 0; ++k)
> > u |= u >> (1 << (k+1));
> > return u ^ (u >> 1);
> > }
> >
> > I tried several other variations of this theme. Many were good
> > for neither compiler, many others only good for clang, one or two
> > only good for gcc, but none good for both.
>
> Try this:
>
> T
> highest_bit_set( T u ){
> T one = 1, all = -one;
> unsigned k, s;
>
> u |= u>>1;
> for( k = 0; s = 1<<k, all>>s > one<<s; k++ ){
> u |= u >> s*2;
> }
>
> return u ^ (u >> 1);
> }
>
> With -O3 this works for me with both gcc and clang (both at least
> several years old).
>

Yes, it works with my relatively new compilers too.
I wonder why gcc understands this but not that. Both variants appear
to have equal complexity.

>
> > Fortunately there is always a magic macro of yours.
>
> Again, not mine. The original author was Hallvard Furuseth
> (with my MASK_WIDTH() being a less ambitious version of his
> IMAX_BITS()).
>
> > It works
> > fine with both compilers. May be, it has theoretical limits,
> > but in practice it is more than good enough.
> >
> > T
> > highest_bit_set( T u ){
> > const int nbits = MASK_WIDTH((T)-1);
> > for (int k = 0; (1<<k) < nbits; ++k)
> > u |= u >> (1<<k);
> > return u ^ (u >> 1);
> > }
>
> The version of MASK_WIDTH I posted tops out at 491504 bits.
>
> If that's not enough, here is the original (my choice of layout,
> wrapping, and using 'unsigned long' type, but otherwise the same):
>
> #define IMAX_BITS(m) IMAX_BITS_((m))
> #define IMAX_BITS_(m) ( \
> m / (m%0x3fffffffUL+1) / 0x3fffffffUL % 0x3fffffffUL * 30 \
> + m%0x3fffffffUL / (m%31+1) / 31 % 31 * 5 \
> + 4 - 12/(m%31+3) \
> )
>
> This form is good (or so I understand) up to more than 30 billion
> bits. I haven't tested it that high. :)
>
> Original author: Hallvard Breien Furuseth<h.b.furuseth@usit.uio.no>
>
> Reference in
> http://www.stackprinter.com/export?question=3957252&service=stackoverflow

Thank you. From now on I promise to give a correct attribution.

On 2023-10-24, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Kaz Kylheku <864-117-4973@kylheku.com> writes:
>> Oh, if I had to make it work with the unsigned long type, like the other
>> solutions,
>
> That is a misrepresentation.

I think I based that statement on seeing "typedef unsigned long T"
all over the thread.

>> I'd probably just do this:
>>
>> unsigned long fill_mask_down(unsigned long x)
>> {
>> x |= x >> 1;
>> x |= x >> 2;
>> x |= x >> 4;
>> x |= x >> 8;
>>
>> #if UINT_MAX == UINT32_MAX
>> x |= x >> 16;
>> [...]
>
> The challenge is to find an algorithm that works
> without being tied to a specific type.

The weakest interpretation of that requirement statement is that the
solution must be generic; in the same program, the function is applied
to different types, and is calculated using a specialized variant of the
code customized to hat type.

This does not characterize the solutions I'm seeing in the thread,
which were not challenged on grounds of not conforming to the task.
These ar are organized around a single type called T, which is an alias
for a single, specific type in any given translation of the code.

If the definition of the T typedef is accompanied by a limit macro
such as:

typedef unsigned T;
#define T_MAX UINT_MAX

we can adapt the above solution to T.

> If you
> aren't up to the task that's okay with me, but
> don't pretend it's something it isn't.

I may have mistaken this for something that is supposed to be
practically useful in an actual project.

(If I have to work with a single type T in some project, which is not
defined in my code and which can vary from platform to platform, I can
always come up with a limit macro for it.)

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

On 2023-10-24, Michael S <already5chosen@yahoo.com> wrote:
> In my own tests I used following form of Kaz's algorithm:
>
> T
> highest_bit_set( T u ){
> for (int k = 0; ((T)-1 >> ((1 <<k)-1)) > 1; ++k)
> u |= u >> (1 << k);
> return u ^ (u >> 1);
> }
>
> Both gcc -O3 and clang -O2 and -O3 translate it into the same object
> code as manually written sequence.
> Of course, this code works only for types with number of bits equal to
> power of two. For my tests it was o.k. because my test platforms
> have no other integer types anyway.
>
> I was not able to generalize this loop for non-power-of-two.

For reference, how I would adapt my practical solution to
non-power-of-two would be to accompany the definition of the type T with
a limit macro that gives the maximum value of the smallest
power-of-two-sized type that is no smaller than that type.

(I've not lost track of that the solution still depends on the UINTn_MAX
macros being available, which isn't guaranteed.)

#include <limits.h>
#include <stdint.h>

typedef unsigned long T;
#define T_MAX ULONG_MAX
#define T_BP2_MAX ULONG_MAX /* max of bounding power of two type */

T fill_mask_down(T x)
{
x |= x >> 1;
x |= x >> 2;
#if T_BP2_MAX == UINT8_MAX
x |= x >> 4;
#elif T_BP2_MAX == UINT16_MAX
x |= x >> 4;
x |= x >> 8;
#elif T_BP2_MAX == UINT32_MAX
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
#elif T_BP2_MAX == UINT64_MAX
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
#else
#error port me!
#endif

return x;
}

T isolate_highest_bit(T x)
{
T m = fill_mask_down(x);
return m ^ (m >> 1);
}

Suppose we are working on PIC24 and want T to be the __uint24 type
(or whatever it is called in that toolchain). Then:

typedef define __uint24 T;
#define T_MAX 0xFFFFFFU
#define T_BP2_MAX UINT32_MAX

So essentially, the algorithm pretends that a type between 17 and 32
bits wide is 32 bits wide.

But this is okay because for that size, it never executes a right shift
exceeding 16.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

(Your 24-Oct post is not appearing on ES for some reason; I'm responding
to that via a 23-Oct post.)

On 24/10/2023 17:54, Kaz Kylheku wrote:
> On 2023-10-24, Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>> Kaz Kylheku <864-117-4973@kylheku.com> writes:
>>> Oh, if I had to make it work with the unsigned long type, like the
other
>>> solutions,
>>
>> That is a misrepresentation.
>
> I think I based that statement on seeing "typedef unsigned long T"
> all over the thread.
>
>>> I'd probably just do this:
>>>
>>> unsigned long fill_mask_down(unsigned long x)
>>> {
>>> x |= x >> 1;
>>> x |= x >> 2;
>>> x |= x >> 4;
>>> x |= x >> 8;
>>>
>>> #if UINT_MAX == UINT32_MAX
>>> x |= x >> 16;
>>> [...]
>>
>> The challenge is to find an algorithm that works
>> without being tied to a specific type.
>
> The weakest interpretation of that requirement statement is that the
> solution must be generic; in the same program, the function is applied
> to different types, and is calculated using a specialized variant of the
> code customized to hat type.
>
> This does not characterize the solutions I'm seeing in the thread,
> which were not challenged on grounds of not conforming to the task.
> These ar are organized around a single type called T, which is an alias
> for a single, specific type in any given translation of the code.
>
> If the definition of the T typedef is accompanied by a limit macro
> such as:
>
> typedef unsigned T;
> #define T_MAX UINT_MAX
>
> we can adapt the above solution to T.
>
>> If you
>> aren't up to the task that's okay with me, but
>> don't pretend it's something it isn't.
>
> I may have mistaken this for something that is supposed to be
> practically useful in an actual project.

This has long moved on from being anything practical. The original task
was something you'd do in 5 minutes and move on.

A practical solution would be written for u32 or u64 or both.

But the new requirement (which seems to have been invented by Tim)
apparently has to be a single algorithm that works with u128 as well as
u32/u64, and probably any non-power-of-two sizes.

> (If I have to work with a single type T in some project, which is not
> defined in my code and which can vary from platform to platform, I can
> always come up with a limit macro for it.)

I made this point a week ago: if any one program needs this for two or
more different Ts, there will need to be two or more distinct functions
anyway. Exactly how the resulting T-based function would be deployed,
especially when multiple Ts are in the same scope, is not clear.

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> [...]
>
>> If we wait until you have the benefit of some daylight thinking
>> hours I expect you will see how this can be done. (Disclaimer
>> and possible spoiler alert: strictly speaking there may be some
>> issues on implementations with integer types that have trap
>> representations. These days though I don't think any machines
>> even have any padding bits, let alone trap representations. Oh,
>> I have to take that back - I know of one contemporary machine
>> where unsigned types don't use the sign bit, and so have one
>> padding bit. In that case though there is enough information
>> so the padding bit is known, and potential trap representations
>> can be avoided.)
>
> Which contemporary machine is that?

My understanding is that one of the Unisys machines, which to the
best of my knowledge are still being produced, have unsigned
types that don't use the sign bit as a value bit for unsigned
types (and so for example INT_MAX == UINT_MAX). Even if that
arrangement no longer applies, my belief that it might was
enough that I felt obliged to put in the disclaimer.

On Wed, 25 Oct 2023 00:19:08 +0100
Bart <bc@freeuk.com> wrote:

>
> I made this point a week ago: if any one program needs this for two
> or more different Ts, there will need to be two or more distinct
> functions anyway. Exactly how the resulting T-based function would be
> deployed, especially when multiple Ts are in the same scope, is not
> clear.
>

The most obvious answer to that is "Use C preprocessor."
For example, in project A you compile your module with -DT='uint16_t'
and in project B you compile with -DT='unsigned __int128'.
If you want to use both variants in the same project then you apply
token pasting operator of preprocessor to mangle function name,
thus avoiding names clash. The last step is not necessarily trivial,
esp. for type names consisting of more than one token, but off topic
here.

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 25 Oct 2023 00:19:08 +0100
> Bart <bc@freeuk.com> wrote:
>
>>
>> I made this point a week ago: if any one program needs this for two
>> or more different Ts, there will need to be two or more distinct
>> functions anyway. Exactly how the resulting T-based function would be
>> deployed, especially when multiple Ts are in the same scope, is not
>> clear.
>
> The most obvious answer to that is "Use C preprocessor."
> For example, in project A you compile your module with -DT='uint16_t'
> and in project B you compile with -DT='unsigned __int128'.
> If you want to use both variants in the same project then you apply
> token pasting operator of preprocessor to mangle function name,
> thus avoiding names clash. The last step is not necessarily trivial,
> esp. for type names consisting of more than one token, but off topic
> here.

Why is it off-topic here? It seems right on topic for the group. Do
you mean in this thread? Even so I'd say it's OK since it addresses
something that has caused some confusion*. It's even more on-topic (I'd
say) since C23's proposed unsigned _BitInt(n) have been mentioned.

[*] The idea of a function that will work for any unsigned (but
otherwise arbitrary) integer type has a meaning in other languages that
does not tie up with the meaning used here. Macro fiddling is a way to
approximate the meaning that applies in languages with better type
polymorphism.

--
Ben.

On Wed, 25 Oct 2023 20:40:22 +0100
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 25 Oct 2023 00:19:08 +0100
> > Bart <bc@freeuk.com> wrote:
> >
> >>
> >> I made this point a week ago: if any one program needs this for two
> >> or more different Ts, there will need to be two or more distinct
> >> functions anyway. Exactly how the resulting T-based function would
> >> be deployed, especially when multiple Ts are in the same scope, is
> >> not clear.
> >
> > The most obvious answer to that is "Use C preprocessor."
> > For example, in project A you compile your module with
> > -DT='uint16_t' and in project B you compile with -DT='unsigned
> > __int128'. If you want to use both variants in the same project
> > then you apply token pasting operator of preprocessor to mangle
> > function name, thus avoiding names clash. The last step is not
> > necessarily trivial, esp. for type names consisting of more than
> > one token, but off topic here.
>
> Why is it off-topic here? It seems right on topic for the group. Do
> you mean in this thread?

Yes, that what I meant.
This thread is about algorithms or, at least, that what I think it is.

> Even so I'd say it's OK since it addresses
> something that has caused some confusion*. It's even more on-topic
> (I'd say) since C23's proposed unsigned _BitInt(n) have been
> mentioned.
>
> [*] The idea of a function that will work for any unsigned (but
> otherwise arbitrary) integer type has a meaning in other languages
> that does not tie up with the meaning used here. Macro fiddling is a
> way to approximate the meaning that applies in languages with better
> type polymorphism.
>

Hopefully, even if Bart does not remember how to solve it with
concatanation operator ##, now after being reminded about it, with a
little help of search engines he can easily figure it out.
I mean, he can easily figure out how to solve a simple case, where the
type is expressed as a single token. Solving multi-token case is not
trivial and right now I don't know how to do it.

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 24 Oct 2023 07:35:02 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:

[..getting compilers to completely unroll a loop..]

>>> I was not able to generalize this loop for non-power-of-two.
>>> For example, the variant below produces desired code with
>>> clang, but gcc12 generates loop instead of straight line.
>>>
>>> T
>>> highest_bit_set( T u ){
>>> u |= u >> 1;
>>> for (int k = 0; (((T)-1 >> (1<<k)) >> (1<<k)) != 0; ++k)
>>> u |= u >> (1 << (k+1));
>>> return u ^ (u >> 1);
>>> }
>>>
>>> I tried several other variations of this theme. Many were
>>> good for neither compiler, many others only good for clang,
>>> one or two only good for gcc, but none good for both.
>>
>> Try this:
>>
>> T
>> highest_bit_set( T u ){
>> T one = 1, all = -one;
>> unsigned k, s;
>>
>> u |= u>>1;
>> for( k = 0; s = 1<<k, all>>s > one<<s; k++ ){
>> u |= u >> s*2;
>> }
>>
>> return u ^ (u >> 1);
>> }
>>
>> With -O3 this works for me with both gcc and clang (both at least
>> several years old).
>
> Yes, it works with my relatively new compilers too. I wonder
> why gcc understands this but not that. Both variants appear to
> have equal complexity.

I played around with this a bit. It looks like gcc is following
some heuristic for when a control expression is too complicated,
and the one you used was over the line - the "complexity" of one
variable shift (rather than a constant shift) followed by another
is more than gcc wants to deal with.

Here is my latest version:

T
highest_bit_set( T u ){
for( long s = 1; (T){-1} >>s/2 > (T){1} <<s/2; s <<= 1 ){
u |= u>>s;
}
return u ^ u>>1;
}

I am pleased by the simple form of this function. Also I think
you deserve kudos for the idea of two half-shifts, which works
great.

Incidentally, for people who are focused on absolute correctness,
there is an almost insignificant limitation in the above function
definition. What is the limitation and how can it be addressed?
No hints now but I am willing to give a hint if asked.

>>> Fortunately there is always a magic macro of yours.
>>
>> Again, not mine. The original author was Hallvard Furuseth
>> (with my MASK_WIDTH() being a less ambitious version of his
>> IMAX_BITS()). [...]
>
> Thank you. From now on I promise to give a correct attribution.

I didn't mean to take you to task. I felt it necessary to give
the attribution to observe my own sense of intellectual honesty.

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

> Tim Rentsch to Anton Shepelev:
> [earlier version removed]
>
>> 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.
>
> OK:
>
> T
> high_bit_mask( T n )
> { const T M = (T)1 << (CHAR_BIT * sizeof( T ) - 1);
> T mask = 0;
> int l = -1,
> r = CHAR_BIT * sizeof( T );
>
> do
> { const int m = (l + r)/2;
> T C = M >> m;
>
> if( n >= C ) { r = m; mask = C; }
> else { l = m; }
> } while( r - l > 1 );
>
> return mask;
> }
>
>> 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;
>> }
>
> I disagree about the higher simplicity of your code,

I have responses to your comments below, followed by some more
general remarks about your rendition.

> because it
>
> 1. has two return statements,

Having two return statements makes the code easier to understand,
not harder. During the course of the loop if the answer is found
it is returned immediately. It's easy to see from the code that
the right value is being returned; just immediately returning it
makes it easier to reason about what else is going on.

General comment: a dogmatic aversion to having multiple returns
is wrongheaded, especially in pure functions like this one.

> 2. employs the /clever trick/ of comparing the mask to
> different values in different branches.

It isn't particularly clever, and it certainly isn't a trick.
It's easy to see that, if

u>>1 < bit && bit <= u

then bit is the value we are looking for, so we're done. Outside
of that range the value is either too high or too low, and the
boundary markers are adjusted accordingly.

> 3. uses a three-way `if'.

There are three branches because the interval subdivides naturally
into three parts. The problem here is unlike a general binary
search in that we know there is exactly one solution, and it will
be an exact match to one of the generated values. Searching for a
value in an array is different because, one, we aren't sure in
general that the value we're looking for will be there, and two,
the array might contain duplicate values. Neither of those apply
here, so the three-way choice is natural. In a sense we are
deciding what to do depending on whether the generated bit value
is less than, greater than, or equal to, the right value. By
contrast the two-way branch is either greater than or {less than
or maybe equal} (or maybe the other way around; it isn't easy to
tell). The three-way test is a more natural fit, and easier to
reason about for determining correctness.

> 4. uses conditions that are not mutually exclusive.

Given an argument value 'u' and a generated test value 'bit',
exactly one of

bit <= u<<1

u<<1 < bit && bit <= u

u < bit

is true. These conditions correspond directly to the three
branches of the if-else chain, and they are mutually exclusive.
So either your statement is wrong or I don't know what you
mean.

> 5. uses `least' and `limit' instead of intuitive `left'
> and `right' or `min' and `max'. My version makes a
> point of giving its left and right indices the
> intuitive meaning that they have in the standard
> positional notation.

Pshaw. The comparison operators in C are less than and greater
than, not left-of and right-of. Calling the end markers left and
right means having to mentally translate from a left/right
coordinate system to the less-than/greater-then numeric coordinate
system that C uses. Another problem with left/right is that they
seem to be symmetric. Generally reasoning about binary search is
easier if a half-open interval is used (which indeed is what my
code does). The name 'limit' is chosen to indicate which boundary
marker corresponds to the half-open end, and 'least' for the
closed end (i.e., the 'least' value can be possible, whereas the
'limit' value never is).

I would never use either 'left' and 'right' or 'max' and 'min' for
names of the boundary markers in a binary search, because they are
either confusingly or misleadingly evocative. Also I think of
'left' as "bigger", because digits more leftward represent larger
values. For me your 'left' and 'right' are backwards.

> My version, however, is still not a plain-vanilla binary search.

It's a different problem, not like a typical binary search.

For me "simpler" usually means "easier to convince myself that it
works." There are several things about the code you posted that
cause it to take more mental effort for me to understand:

name choices that make it harder to see how the code works

confusingly shifting a top bit down rather than a low bit
up; shifting a low bit up is easier because then the
generated value (what I call bit) goes in the same direction
as the quantity used to produce it

choice of 'int' for the boundary markers, including one
initialized to a negative number. Thinking of the boundary
markers as holding shift values on '1' is natural, and it's
easy to see that the initial values are right: the least
shift is zero, and the width of the argument type is one
more than the largest shift allowed. Shifting a high-order
bit means I have to think harder about the calculation to
produce the high-order bit, and more mental effort is
needed to translate between the shift values and the
generated bit value, because numerically they go in opposite
directions, making the relationship more complicated (and
also different for different width types). Seeing an 'int'
used as a shift amount, with one of the boundary markers
initialized with a negative value, makes me nervous, because
I need to think carefully to be sure there is never a shift
with a negative shift amount. Using an unsigned type for
the shift amounts gets rid of that problem.

Probably my biggest complaint is that to see how the code is
working I need to keep track of the state changes to 'mask' to see
that it has the right value. This property could be a consequence
of avoiding multiple returns: if there is a rule against having
more than one return, that can cause one or more of (a) the code
needing to be altered to avoid doing an early return, (b) having
to use some kind of intra-function jump (goto or break), or (c)
needing a variable to hold the return value, so it can be returned
by the one 'return' statement. The code you posted has such a
variable, and that results in more mental effort needed to see
whether the function works. Needing that extra variable is a huge
cost in terms of reasoning about the code, and that by itself is
enough for me see my code as simpler.