David Brown <david.brown@hesbynett.no> writes:

> On 11/10/2023 19:34, Tim Rentsch wrote:
....
>> * Very few cases with undefined behavior
>
> Why would you accept any cases?
>
>> * Forms an excellent basis for several interview questions
>
> Anyone suggesting such a solution for an interview in my world would get an
> extremely poor scoring. But they might get points for showing why it is
> such a bad idea.

Exactly. That's what Tim said -- good for several interview questions.

I think you missed the whole tone of the post. There were lots of
signals, but surely "Very few cases with undefined behavior" should have
sealed it.

>> (I'm resisting the temptation to make an off-topic remark
>> regarding the number of properties.)
>> P.S. This response is meant to be more entertaining than
>> useful. I do hope it helps broaden your thinking in
>> searching for an answer.
>
> It's fine to give some "off the beaten track" solutions, but don't lie
> about them.

What is the lie? I don't see one.

--
Ben.

On 10/11/23 13:02, Richard Harnden wrote:
> Why 0x100000000 and not 0x800000000?

Wait, how do you specify a binary constant again?
--
user <candycane> is generated from /dev/urandom

On 10/11/23 12:03, Ian C wrote:
> On 11/10/2023 17:19, candycanearter07 wrote:
>> On 10/11/23 02:27, Anton Shepelev wrote:
>>> candycanearter07:
>>>
>>>> What is the best/most portable way to get the highest bit
>>>> set?
>>>>
>>>> ie. 011010001
>>>> to  010000000
>>>
>>> What is your best attempt, even if unsuccessful?
>>>
>>
>> int out;
>> for(out = 0x100000000; out; out >> 1)
>>      if(out & input) break;
>>
>> I'm trying to find something size independent, though.
>> Or at least able to be swapped out with a #define
>
> If you want the highest bit, 0x800000000 may be a better start :-)
>
> If it was me I'd do it in reverse.  Assuming it's unsigned, shift your
> input to the right until it hits zero, counting the number of shifts
> which will be your bit number.  Assuming my head is currently working.
>
>
> Ian C

Actually yeah, I think that could work.
--
user <candycane> is generated from /dev/urandom

On 12/10/2023 01:25, candycanearter07 wrote:
> On 10/11/23 13:02, Richard Harnden wrote:
>> Why 0x100000000 and not 0x800000000?
>
> Wait, how do you specify a binary constant again?

Use 0b rather than 0x. But without numeric separators, you will need to
count carefully if you have up to 64 bits.

Easier might be to write 1U<<31 or 1ULL<<63.

Bart <bc@freeuk.com> writes:
> On 12/10/2023 01:25, candycanearter07 wrote:
>> On 10/11/23 13:02, Richard Harnden wrote:
>>> Why 0x100000000 and not 0x800000000?

I think there's an extra 0 on both of those constants.

>> Wait, how do you specify a binary constant again?
>
> Use 0b rather than 0x. But without numeric separators, you will need
> to count carefully if you have up to 64 bits.
>
> Easier might be to write 1U<<31 or 1ULL<<63.

C does not currently support binary constants. C23 adds them, and gcc
and clang both support them as an extension (some other compilers might
also).

In C23, a binary integer constant starts with "0b" or "0B".

C23 will also allow apostrophe as a digit separator (a feature borrowed
from C++), so you can write 0b1100'1001 -- but don't count on any
pre-C23 compilers supporting that as an extension.

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

On 10/11/23 19:35, Bart wrote:
> Use 0b rather than 0x. But without numeric separators, you will need to
> count carefully if you have up to 64 bits.
>
> Easier might be to write 1U<<31 or 1ULL<<63.

Okey thanks.
--
user <candycane> is generated from /dev/urandom

Ben Bacarisse ha scritto:
> jak <nospam@please.ty> writes:
>
>> candycanearter07 ha scritto:
>>> Hi,
>>> What is the best/most portable way to get the highest bit set?
>>> ie. 011010001
>>> to  010000000
>>
>> Hi,
>> I don't think it's the best but the most portable could be the
>> mathematical approach:
>>
>> #include <stdio.h>
>> #include <math.h>
>>
>> int main()
>> {
>> unsigned long val = 3000, ret;
>
> Test case: val = 0xFFFFFFFFFFFFFFFF

This is due to the approximation of the floating point:

log(18446744073709541615) / log(2) =
63.99999999999999921849

>
>> ret = (unsigned long)pow(2., (double)(unsigned long)(log((double)val) /
>> log(2.)));
>>
>> printf("%lu -> %lu", val, ret);
>>
>> return 0;
>> }
>

Tim Rentsch:

> I've coded up a dozen[*] different solutions.
> Here is my current avorite[**]:
>
> typedef union {
> long double d;
> struct { unsigned long long s; unsigned e:15;} b;
> } X;
>
> unsigned long long
> high_bit_set( unsigned long long u ){
> return 1ULL << (X){ .d = u }.b.e - 16383 & u;
> }

And mine is quite anticlimactic. It accepts a byte, because
I wrote it yesterday, before learning that the OP needs a
more generic solution:

unsigned char highest_bit( unsigned char byte )
{ int i ;
unsigned char mask = 1 << 7;
for( i = 0; i <= 8; i += 1 )
{ if( byte & mask )
{ break; }
mask >>= 1;
}
return mask;
}

It is the most straight-forward method that I could think
of, and extensible to larger sizes of the variable.

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

On Wednesday, October 11, 2023 at 11:47:56 PM UTC+3, David Brown wrote:
> On 11/10/2023 19:34, Tim Rentsch wrote:
> > candycanearter07 <n...@thanks.net> writes:
> >
> >> On 10/11/23 02:27, Anton Shepelev wrote:
> >>
> >>> candycanearter07:
> >>>
> >>>> What is the best/most portable way to get the highest bit
> >>>> set?
> >>>>
> >>>> ie. 011010001
> >>>> to 010000000
> >>>
> >>> What is your best attempt, even if unsuccessful?
> >>
> >> int out;
> >> for(out = 0x100000000; out; out >> 1)
> >> if(out & input) break;
> >>
> >> I'm trying to find something size independent, though.
> >> Or at least able to be swapped out with a #define
> >
> > I've coded up a dozen[*] different solutions. Here is my current
> > favorite[**]:
> >
> > typedef union {
> > long double d;
> > struct { unsigned long long s; unsigned e:15;} b;
> > } X;
> >
> > unsigned long long
> > high_bit_set( unsigned long long u ){
> > return 1ULL << (X){ .d = u }.b.e - 16383 & u;
> > }
> >
> >
> > This answer has these nice properties:
> >
> > * Single line function body
> Irrelevant.
> > * No looping or testing
> That could be useful for efficiency. But a solution that can boil down
> to some kind of "count leading zeros" or "find first one" instruction
> will be much more efficient. (And the shift will be a loop on smaller
> processors.) And if you had bothered to look at the generated code,
> even on efficient compilers for the one target it supports, you'd see it
> generates tests and either a branch or a conditional move.
> > * Large domain of inputs supported
> True - it supports up to 64 bits.
>
> > * Widely portable
>
> Completely incorrect - unless you think that x86 extended precision
> floating point format is "widely portable". It's not even portable in
> the x86 world. Basically, it will fail for any compiler for which "long
> double" is the same format as "double", which includes MSVC, and gcc for
> many non-x86 targets.

It will also fail for any compiler for which "long double" is *not* the same
format as "double", but also not the same as Intel's 80-bit. That includes all
aarch64 Linux compiler where 'long double' is equivalent of IEEE
binary128 and is implemented in software.

> > * Very few cases with undefined behavior
> Why would you accept any cases?
> > * Forms an excellent basis for several interview questions
> Anyone suggesting such a solution for an interview in my world would get
> an extremely poor scoring. But they might get points for showing why it
> is such a bad idea.
> > * Sure to launch a torrent of followups on its pros and cons
> /That/ one I agree on, though of course you will ignore my reply.
>
> It also has not-nice properties including:
>
> * Totally dependent on floating point standards found only on some
> compilers.
>
> * Slow and inefficient on x86, because it requires non-SIMD floating point.
>

That's not true. On prevalent Intel and AMD processors, for scalar
calculations like above, x87 FPU is about as fast SSE/AVX FPU.
Speed wise, on x64 Linux or BSD Tim's solution is quite o.k, second
only to non-portable intrinsic and to non-existing C23 variants.

> * Non-obvious code with a magic number, using features well outside the
> problem domain.
>
> * Unnecessarily outside the C++ compatible subset of C (this is
> important to some people).
> >
> > (I'm resisting the temptation to make an off-topic remark
> > regarding the number of properties.)
> >
> >
> > P.S. This response is meant to be more entertaining than
> > useful. I do hope it helps broaden your thinking in
> > searching for an answer.
> >
> It's fine to give some "off the beaten track" solutions, but don't lie
> about them.

On 12/10/2023 01:31, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
>
>> On 11/10/2023 19:34, Tim Rentsch wrote:
> ...
>>> * Very few cases with undefined behavior
>>
>> Why would you accept any cases?
>>
>>> * Forms an excellent basis for several interview questions
>>
>> Anyone suggesting such a solution for an interview in my world would get an
>> extremely poor scoring. But they might get points for showing why it is
>> such a bad idea.
>
> Exactly. That's what Tim said -- good for several interview questions.
>
> I think you missed the whole tone of the post. There were lots of
> signals, but surely "Very few cases with undefined behavior" should have
> sealed it.
>
>>> (I'm resisting the temptation to make an off-topic remark
>>> regarding the number of properties.)
>>> P.S. This response is meant to be more entertaining than
>>> useful. I do hope it helps broaden your thinking in
>>> searching for an answer.
>>
>> It's fine to give some "off the beaten track" solutions, but don't lie
>> about them.
>
> What is the lie? I don't see one.
>

"Widely portable". In general, I thought his post might mislead people
into thinking it was a serious line of attack for the problem - creative
uses of floating point operations have been seen before for this kind of
thing. (I started writing a longer explanation, but scraped it to avoid
rambling off topic, so we can get back to the C.)

One thing that I did find interesting, however, was when I tried it on
godbolt and made a couple of test functions like :

unsigned test1(void) { return high_bit_set(7654(; }

gcc was happy to pre-calculate the correct result at compile time. I
know gcc (and clang) can simulate floating point hardware accurately at
compile time, but it surprised me that these compilers managed that.

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

There exist more straight-forward method that you could think of
if you try to think a little longer. It is suggested by IanC near beginning
of this thread starting from "If it was me I'd do it in reverse".

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

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

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

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

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

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

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

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> David Brown <david.brown@hesbynett.no> writes:
>
>> On 11/10/2023 19:34, Tim Rentsch wrote:
>
> ...
>
>>> * Very few cases with undefined behavior
>>
>> Why would you accept any cases?
>>
>>> * Forms an excellent basis for several interview questions
>>
>> Anyone suggesting such a solution for an interview in my world would
>> get an extremely poor scoring. But they might get points for showing
>> why it is such a bad idea.
>
> Exactly. That's what Tim said -- good for several interview questions.
>
> I think you missed the whole tone of the post. There were lots of
> signals, but surely "Very few cases with undefined behavior" should
> have sealed it.
>
>>> (I'm resisting the temptation to make an off-topic remark
>>> regarding the number of properties.)
>>> P.S. This response is meant to be more entertaining than
>>> useful. I do hope it helps broaden your thinking in
>>> searching for an answer.
>>
>> It's fine to give some "off the beaten track" solutions, but don't lie
>> about them.
>
> What is the lie? I don't see one.

Thank you Ben. Your comments are all spot on.

jak <nospam@please.ty> writes:

> Ben Bacarisse ha scritto:
>> jak <nospam@please.ty> writes:
>>
>>> candycanearter07 ha scritto:
>>>> Hi,
>>>> What is the best/most portable way to get the highest bit set?
>>>> ie. 011010001
>>>> to  010000000
>>>
>>> Hi,
>>> I don't think it's the best but the most portable could be the
>>> mathematical approach:
>>>
>>> #include <stdio.h>
>>> #include <math.h>
>>>
>>> int main()
>>> {
>>> unsigned long val = 3000, ret;
>> Test case: val = 0xFFFFFFFFFFFFFFFF
>
> This is due to the approximation of the floating point:

I know the reason. I was just pointing out that you need to at least
test the boundary cases!

--
Ben.

On Thursday, October 12, 2023 at 12:20:39 PM UTC+3, Michael S wrote:
> On Wednesday, October 11, 2023 at 11:47:56 PM UTC+3, David Brown wrote:
> > On 11/10/2023 19:34, Tim Rentsch wrote:
> > > candycanearter07 <n...@thanks.net> writes:
> > >
> > >> On 10/11/23 02:27, Anton Shepelev wrote:
> > >>
> > >>> candycanearter07:
> > >>>
> > >>>> What is the best/most portable way to get the highest bit
> > >>>> set?
> > >>>>
> > >>>> ie. 011010001
> > >>>> to 010000000
> > >>>
> > >>> What is your best attempt, even if unsuccessful?
> > >>
> > >> int out;
> > >> for(out = 0x100000000; out; out >> 1)
> > >> if(out & input) break;
> > >>
> > >> I'm trying to find something size independent, though.
> > >> Or at least able to be swapped out with a #define
> > >
> > > I've coded up a dozen[*] different solutions. Here is my current
> > > favorite[**]:
> > >
> > > typedef union {
> > > long double d;
> > > struct { unsigned long long s; unsigned e:15;} b;
> > > } X;
> > >
> > > unsigned long long
> > > high_bit_set( unsigned long long u ){
> > > return 1ULL << (X){ .d = u }.b.e - 16383 & u;
> > > }
> > >
> > >
> > > This answer has these nice properties:
> > >
> > > * Single line function body
> > Irrelevant.
> > > * No looping or testing
> > That could be useful for efficiency. But a solution that can boil down
> > to some kind of "count leading zeros" or "find first one" instruction
> > will be much more efficient. (And the shift will be a loop on smaller
> > processors.) And if you had bothered to look at the generated code,
> > even on efficient compilers for the one target it supports, you'd see it
> > generates tests and either a branch or a conditional move.
> > > * Large domain of inputs supported
> > True - it supports up to 64 bits.
> >
> > > * Widely portable
> >
> > Completely incorrect - unless you think that x86 extended precision
> > floating point format is "widely portable". It's not even portable in
> > the x86 world. Basically, it will fail for any compiler for which "long
> > double" is the same format as "double", which includes MSVC, and gcc for
> > many non-x86 targets.
> It will also fail for any compiler for which "long double" is *not* the same
> format as "double", but also not the same as Intel's 80-bit. That includes all
> aarch64 Linux compiler where 'long double' is equivalent of IEEE
> binary128 and is implemented in software.
> > > * Very few cases with undefined behavior
> > Why would you accept any cases?
> > > * Forms an excellent basis for several interview questions
> > Anyone suggesting such a solution for an interview in my world would get
> > an extremely poor scoring. But they might get points for showing why it
> > is such a bad idea.
> > > * Sure to launch a torrent of followups on its pros and cons
> > /That/ one I agree on, though of course you will ignore my reply.
> >
> > It also has not-nice properties including:
> >
> > * Totally dependent on floating point standards found only on some
> > compilers.
> >
> > * Slow and inefficient on x86, because it requires non-SIMD floating point.
> >
> That's not true. On prevalent Intel and AMD processors, for scalar
> calculations like above, x87 FPU is about as fast SSE/AVX FPU.
> Speed wise, on x64 Linux or BSD Tim's solution is quite o.k, second
> only to non-portable intrinsic and to non-existing C23 variants.
> > * Non-obvious code with a magic number, using features well outside the
> > problem domain.
> >
> > * Unnecessarily outside the C++ compatible subset of C (this is
> > important to some people).
> > >
> > > (I'm resisting the temptation to make an off-topic remark
> > > regarding the number of properties.)
> > >
> > >
> > > P.S. This response is meant to be more entertaining than
> > > useful. I do hope it helps broaden your thinking in
> > > searching for an answer.
> > >
> > It's fine to give some "off the beaten track" solutions, but don't lie
> > about them.

Test.
Trying to figure out why Eternal September does not show the message
that I am replying to.

On Wednesday, October 11, 2023 at 11:47:56 PM UTC+3, David Brown wrote:
> On 11/10/2023 19:34, Tim Rentsch wrote:
> > candycanearter07 <n...@thanks.net> writes:
> >
> >> On 10/11/23 02:27, Anton Shepelev wrote:
> >>
> >>> candycanearter07:
> >>>
> >>>> What is the best/most portable way to get the highest bit
> >>>> set?
> >>>>
> >>>> ie. 011010001
> >>>> to 010000000
> >>>
> >>> What is your best attempt, even if unsuccessful?
> >>
> >> int out;
> >> for(out = 0x100000000; out; out >> 1)
> >> if(out & input) break;
> >>
> >> I'm trying to find something size independent, though.
> >> Or at least able to be swapped out with a #define
> >
> > I've coded up a dozen[*] different solutions. Here is my current
> > favorite[**]:
> >
> > typedef union {
> > long double d;
> > struct { unsigned long long s; unsigned e:15;} b;
> > } X;
> >
> > unsigned long long
> > high_bit_set( unsigned long long u ){
> > return 1ULL << (X){ .d = u }.b.e - 16383 & u;
> > }
> >
> >
> > This answer has these nice properties:
> >
> > * Single line function body
> Irrelevant.
> > * No looping or testing
> That could be useful for efficiency. But a solution that can boil down
> to some kind of "count leading zeros" or "find first one" instruction
> will be much more efficient. (And the shift will be a loop on smaller
> processors.) And if you had bothered to look at the generated code,
> even on efficient compilers for the one target it supports, you'd see it
> generates tests and either a branch or a conditional move.
> > * Large domain of inputs supported
> True - it supports up to 64 bits.
>
> > * Widely portable
>
> Completely incorrect - unless you think that x86 extended precision
> floating point format is "widely portable". It's not even portable in
> the x86 world. Basically, it will fail for any compiler for which "long
> double" is the same format as "double", which includes MSVC, and gcc for
> many non-x86 targets.
> > * Very few cases with undefined behavior
> Why would you accept any cases?
> > * Forms an excellent basis for several interview questions
> Anyone suggesting such a solution for an interview in my world would get
> an extremely poor scoring. But they might get points for showing why it
> is such a bad idea.
> > * Sure to launch a torrent of followups on its pros and cons
> /That/ one I agree on, though of course you will ignore my reply.
>
> It also has not-nice properties including:
>
> * Totally dependent on floating point standards found only on some
> compilers.
>
> * Slow and inefficient on x86, because it requires non-SIMD floating point.
>
> * Non-obvious code with a magic number, using features well outside the
> problem domain.
>
> * Unnecessarily outside the C++ compatible subset of C (this is
> important to some people).
> >
> > (I'm resisting the temptation to make an off-topic remark
> > regarding the number of properties.)
> >
> >
> > P.S. This response is meant to be more entertaining than
> > useful. I do hope it helps broaden your thinking in
> > searching for an answer.
> >
> It's fine to give some "off the beaten track" solutions, but don't lie
> about them.

Another test.
Still trying to figure out what Eternal September shows and what not.

Repeating myself,
I can't figure out why Eternal September server refuses to show a previous
response.

On Wednesday, October 11, 2023 at 11:47:56 PM UTC+3, David Brown wrote:
> On 11/10/2023 19:34, Tim Rentsch wrote:
> > candycanearter07 <n...@thanks.net> writes:
> >
> >> On 10/11/23 02:27, Anton Shepelev wrote:
> >>
> >>> candycanearter07:
> >>>
> >>>> What is the best/most portable way to get the highest bit
> >>>> set?
> >>>>
> >>>> ie. 011010001
> >>>> to 010000000
> >>>
> >>> What is your best attempt, even if unsuccessful?
> >>
> >> int out;
> >> for(out = 0x100000000; out; out >> 1)
> >> if(out & input) break;
> >>
> >> I'm trying to find something size independent, though.
> >> Or at least able to be swapped out with a #define
> >
> > I've coded up a dozen[*] different solutions. Here is my current
> > favorite[**]:
> >
> > typedef union {
> > long double d;
> > struct { unsigned long long s; unsigned e:15;} b;
> > } X;
> >
> > unsigned long long
> > high_bit_set( unsigned long long u ){
> > return 1ULL << (X){ .d = u }.b.e - 16383 & u;
> > }
> >
> >
> > This answer has these nice properties:
> >
> > * Single line function body
> Irrelevant.
> > * No looping or testing
> That could be useful for efficiency. But a solution that can boil down
> to some kind of "count leading zeros" or "find first one" instruction
> will be much more efficient. (And the shift will be a loop on smaller
> processors.) And if you had bothered to look at the generated code,
> even on efficient compilers for the one target it supports, you'd see it
> generates tests and either a branch or a conditional move.
> > * Large domain of inputs supported
> True - it supports up to 64 bits.
>
> > * Widely portable
>
> Completely incorrect - unless you think that x86 extended precision
> floating point format is "widely portable". It's not even portable in
> the x86 world. Basically, it will fail for any compiler for which "long
> double" is the same format as "double", which includes MSVC, and gcc for
> many non-x86 targets.

It will also fail for any compiler for which "long double" is *not* the same
format as "double", but also not the same as Intel's 80-bit. That includes all
aarch64 Linux compiler where 'long double' is equivalent of IEEE
binary128 and is implemented in software.

> > * Very few cases with undefined behavior
> Why would you accept any cases?
> > * Forms an excellent basis for several interview questions
> Anyone suggesting such a solution for an interview in my world would get
> an extremely poor scoring. But they might get points for showing why it
> is such a bad idea.
> > * Sure to launch a torrent of followups on its pros and cons
> /That/ one I agree on, though of course you will ignore my reply.
>
> It also has not-nice properties including:
>
> * Totally dependent on floating point standards found only on some
> compilers.
>
> * Slow and inefficient on x86, because it requires non-SIMD floating point.

That's not true. On prevalent Intel and AMD processors, for scalar
calculations like above, x87 FPU is about as fast SSE/AVX FPU.
Speed wise, on x64 Linux or BSD Tim's solution is quite o.k, second
only to non-portable intrinsic and to non-yet-existing C23 variants.

>
> * Non-obvious code with a magic number, using features well outside the
> problem domain.
>
> * Unnecessarily outside the C++ compatible subset of C (this is
> important to some people).
> >
> > (I'm resisting the temptation to make an off-topic remark
> > regarding the number of properties.)
> >
> >
> > P.S. This response is meant to be more entertaining than
> > useful. I do hope it helps broaden your thinking in
> > searching for an answer.
> >
> It's fine to give some "off the beaten track" solutions, but don't lie
> about them.

David Brown <david.brown@hesbynett.no> writes:

> On 12/10/2023 01:31, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> On 11/10/2023 19:34, Tim Rentsch wrote:
>> ...
>>>> * Very few cases with undefined behavior
>>>
>>> Why would you accept any cases?
>>>
>>>> * Forms an excellent basis for several interview questions
>>>
>>> Anyone suggesting such a solution for an interview in my world would get an
>>> extremely poor scoring. But they might get points for showing why it is
>>> such a bad idea.
>> Exactly. That's what Tim said -- good for several interview questions.
>> I think you missed the whole tone of the post. There were lots of
>> signals, but surely "Very few cases with undefined behavior" should have
>> sealed it.
>>
>>>> (I'm resisting the temptation to make an off-topic remark
>>>> regarding the number of properties.)
>>>> P.S. This response is meant to be more entertaining than
>>>> useful. I do hope it helps broaden your thinking in
>>>> searching for an answer.
>>>
>>> It's fine to give some "off the beaten track" solutions, but don't lie
>>> about them.
>> What is the lie? I don't see one.
>>
>
> "Widely portable". In general, I thought his post might mislead people
> into thinking it was a serious line of attack for the problem - creative
> uses of floating point operations have been seen before for this kind of
> thing. (I started writing a longer explanation, but scraped it to avoid
> rambling off topic, so we can get back to the C.)

Lying involves a deliberate intent to decisive. The intent here was to
amuse and entertain. Now it's not always easy to get that across in a
post, so there is a risk that misleading information (pretty much the
whole of the post) could be taken seriously, but that's not lying.

> One thing that I did find interesting, however, was when I tried it on
> godbolt and made a couple of test functions like :
>
> unsigned test1(void) { return high_bit_set(7654(; }
>
> gcc was happy to pre-calculate the correct result at compile time. I know
> gcc (and clang) can simulate floating point hardware accurately at compile
> time, but it surprised me that these compilers managed that.

Interesting. I would not have expected that either. Mind you, there is
no need to simulate the /behaviour/ of the hardware. The code relies
only on the meaning of a set of bits when interpreted as floating point
so it is, perhaps, at the easier end of the spectrum.

--
Ben.

Repeating myself once again.
I can't figure out why Eternal September server refuses to show a
previous response twice.

On Wed, 11 Oct 2023 22:47:35 +0200
David Brown <david.brown@hesbynett.no> wrote:

> On 11/10/2023 19:34, Tim Rentsch wrote:
> > candycanearter07 <no@thanks.net> writes:
> >
> >> On 10/11/23 02:27, Anton Shepelev wrote:
> >>
> >>> candycanearter07:
> >>>
> >>>> What is the best/most portable way to get the highest bit
> >>>> set?
> >>>>
> >>>> ie. 011010001
> >>>> to 010000000
> >>>
> >>> What is your best attempt, even if unsuccessful?
> >>
> >> int out;
> >> for(out = 0x100000000; out; out >> 1)
> >> if(out & input) break;
> >>
> >> I'm trying to find something size independent, though.
> >> Or at least able to be swapped out with a #define
> >
> > I've coded up a dozen[*] different solutions. Here is my current
> > favorite[**]:
> >
> > typedef union {
> > long double d;
> > struct { unsigned long long s; unsigned e:15;} b;
> > } X;
> >
> > unsigned long long
> > high_bit_set( unsigned long long u ){
> > return 1ULL << (X){ .d = u }.b.e - 16383 & u;
> > }
> >
> >
> > This answer has these nice properties:
> >
> > * Single line function body
>
> Irrelevant.
>
> > * No looping or testing
>
> That could be useful for efficiency. But a solution that can boil
> down to some kind of "count leading zeros" or "find first one"
> instruction will be much more efficient. (And the shift will be a
> loop on smaller processors.) And if you had bothered to look at the
> generated code, even on efficient compilers for the one target it
> supports, you'd see it generates tests and either a branch or a
> conditional move.
>
> > * Large domain of inputs supported
>
> True - it supports up to 64 bits.
>
> > * Widely portable
>
> Completely incorrect - unless you think that x86 extended precision
> floating point format is "widely portable". It's not even portable
> in the x86 world. Basically, it will fail for any compiler for which
> "long double" is the same format as "double", which includes MSVC,
> and gcc for many non-x86 targets.
>

It will also fail for any compiler for which "long double" is *not* the
same format as "double", but also not the same as Intel's 80-bit. That
includes all aarch64 Linux compiler where 'long double' is equivalent
of IEEE binary128 and is implemented in software.

> > * Very few cases with undefined behavior
>
> Why would you accept any cases?
>
> > * Forms an excellent basis for several interview questions
>
> Anyone suggesting such a solution for an interview in my world would
> get an extremely poor scoring. But they might get points for showing
> why it is such a bad idea.
>
> > * Sure to launch a torrent of followups on its pros and cons
>
> /That/ one I agree on, though of course you will ignore my reply.
>
> It also has not-nice properties including:
>
> * Totally dependent on floating point standards found only on some
> compilers.
>
> * Slow and inefficient on x86, because it requires non-SIMD floating
> point.
>

That's not true. On prevalent Intel and AMD processors, for scalar
calculations like above, x87 FPU is about as fast SSE/AVX FPU.
Speed wise, on x64 Linux or BSD Tim's solution is quite o.k, second
only to non-portable intrinsic and to non-existing C23 variants.

> * Non-obvious code with a magic number, using features well outside
> the problem domain.
>
> * Unnecessarily outside the C++ compatible subset of C (this is
> important to some people).
>
> >
> > (I'm resisting the temptation to make an off-topic remark
> > regarding the number of properties.)
> >
> >
> > P.S. This response is meant to be more entertaining than
> > useful. I do hope it helps broaden your thinking in
> > searching for an answer.
> >
>
> It's fine to give some "off the beaten track" solutions, but don't
> lie about them.
>
>

Tim Rentsch:

> But the approach you are using requires knowing the size
> of the type involved. The challenge is to write code that
> works without having to know the size in advance.

Well, I could use macros, or the largest integer type, or:
#include <stddef.h>
#include <limits.h>

char is_le()
{ const int v = 1;
const char* p = (unsigned char*)&v;
return *p == 0;
}

unsigned char highest_bit_1( unsigned char byte )
{ int i ;
unsigned char mask = 1 << (CHAR_BIT-1);
for( i = 0; i <= CHAR_BIT; i += 1 )
{ if( byte & mask )
{ break; }
mask >>= 1;
}
return mask;
}

unsigned long long highest_bit_2( void* val, size_t sz )
{ int i,f,inc;
unsigned char *p = val;
unsigned char c;
char le = is_le();

if( le )
{ inc = 1; } else
{ inc = -1; p += sz-1; }

f = sz;
for( i = 0; i < sz; i += 1 )
{ if( (c = *p) == 0 )
{ p += inc; }
else
{ f = i;
break;
}
}
return highest_bit_1( c ) << (CHAR_BIT*(sz-1-f));
}

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

Michael S:

> Test. Trying to figure out why Eternal September does not
> show the message that I am replying to.

If you suspect a false positive for its SPAM filter, report
its `Message-ID:' header in eternal-september.support .

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

Ben Bacarisse ha scritto:
> jak <nospam@please.ty> writes:
>
>> Ben Bacarisse ha scritto:
>>> jak <nospam@please.ty> writes:
>>>
>>>> candycanearter07 ha scritto:
>>>>> Hi,
>>>>> What is the best/most portable way to get the highest bit set?
>>>>> ie. 011010001
>>>>> to  010000000
>>>>
>>>> Hi,
>>>> I don't think it's the best but the most portable could be the
>>>> mathematical approach:
>>>>
>>>> #include <stdio.h>
>>>> #include <math.h>
>>>>
>>>> int main()
>>>> {
>>>> unsigned long val = 3000, ret;
>>> Test case: val = 0xFFFFFFFFFFFFFFFF
>>
>> This is due to the approximation of the floating point:
>
> I know the reason. I was just pointing out that you need to at least
> test the boundary cases!
>

I am sure you knew and I have verified that the problem persists up to
"~0UL - 10000" but I don't find an elegant way, type independent, to
work around... just adding an 'if' or a ternary operator.

On Thursday, October 12, 2023 at 2:35:34 PM UTC+3, jak wrote:
> Ben Bacarisse ha scritto:
> > jak <nos...@please.ty> writes:
> >
> >> Ben Bacarisse ha scritto:
> >>> jak <nos...@please.ty> writes:
> >>>
> >>>> candycanearter07 ha scritto:
> >>>>> Hi,
> >>>>> What is the best/most portable way to get the highest bit set?
> >>>>> ie. 011010001
> >>>>> to 010000000
> >>>>
> >>>> Hi,
> >>>> I don't think it's the best but the most portable could be the
> >>>> mathematical approach:
> >>>>
> >>>> #include <stdio.h>
> >>>> #include <math.h>
> >>>>
> >>>> int main()
> >>>> {
> >>>> unsigned long val = 3000, ret;
> >>> Test case: val = 0xFFFFFFFFFFFFFFFF
> >>
> >> This is due to the approximation of the floating point:
> >
> > I know the reason. I was just pointing out that you need to at least
> > test the boundary cases!
> >
> I am sure you knew and I have verified that the problem persists up to
> "~0UL - 10000" but I don't find an elegant way, type independent, to
> work around... just adding an 'if' or a ternary operator.

I don't know what do you consider elegant, but that code solves
problem of rounding:
int save = fegetround();
fesetround(FE_TOWARDZERO);
volatile double dval = val;
fesetround(save);
Pay attention that without 'volatile' it is not guaranteed to work which
I personally consider as a bug in the Standard.

Also frexp()/ldexp() would be a little less slow than yours log()/pow().
int e;
frexp(dval, &e);
ldexp(0.5, e);
But it still would not work at val=0.

On Thu, 12 Oct 2023 13:35:01 +0200
jak <nospam@please.ty> wrote:

> Ben Bacarisse ha scritto:
> > jak <nospam@please.ty> writes:
> >
> >> Ben Bacarisse ha scritto:
> >>> jak <nospam@please.ty> writes:
> >>>
> >>>> candycanearter07 ha scritto:
> >>>>> Hi,
> >>>>> What is the best/most portable way to get the highest bit set?
> >>>>> ie. 011010001
> >>>>> to  010000000
> >>>>
> >>>> Hi,
> >>>> I don't think it's the best but the most portable could be the
> >>>> mathematical approach:
> >>>>
> >>>> #include <stdio.h>
> >>>> #include <math.h>
> >>>>
> >>>> int main()
> >>>> {
> >>>> unsigned long val = 3000, ret;
> >>> Test case: val = 0xFFFFFFFFFFFFFFFF
> >>
> >> This is due to the approximation of the floating point:
> >
> > I know the reason. I was just pointing out that you need to at
> > least test the boundary cases!
> >
>
> I am sure you knew and I have verified that the problem persists up to
> "~0UL - 10000" but I don't find an elegant way, type independent, to
> work around... just adding an 'if' or a ternary operator.

I don't know what do you consider elegant, but that code solves
problem of rounding:
int save = fegetround();
fesetround(FE_TOWARDZERO);
volatile double dval = val;
fesetround(save);
Pay attention that without 'volatile' it is not guaranteed to work which
I personally consider as a bug in the Standard.

Also frexp()/ldexp() would be a little less slow than yours log()/pow().
int e;
frexp(dval, &e);
ldexp(0.5, e);
But it still would not work at val=0.

I don't know what do you consider elegant, but that code solves
problem of rounding:
int save = fegetround();
fesetround(FE_TOWARDZERO);
volatile double dval = val;
fesetround(save);
Pay attention that without 'volatile' it is not guaranteed to work which
I personally consider as a bug in the Standard.

Also frexp()/ldexp() would be a little less slow than yours log()/pow().
int e;
frexp(dval, &e);
ldexp(0.5, e);
But it still would not work at val=0.

I don't know what do you consider elegant, but that code solves
problem of rounding:
int save = fegetround();
fesetround(FE_TOWARDZERO);
volatile double dval = val;
fesetround(save);
Pay attention that without 'volatile' it is not guaranteed to work which
I personally consider as a bug in the Standard.

Also frexp()/ldexp() would be a little less slow than yours log()/pow().
int e;
frexp(dval, &e);
ldexp(0.5, e);
But it still would not work at val=0.

On 12/10/2023 12:20, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
>
>> On 12/10/2023 01:31, Ben Bacarisse wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>>> On 11/10/2023 19:34, Tim Rentsch wrote:
>>> ...
>>>>> * Very few cases with undefined behavior
>>>>
>>>> Why would you accept any cases?
>>>>
>>>>> * Forms an excellent basis for several interview questions
>>>>
>>>> Anyone suggesting such a solution for an interview in my world would get an
>>>> extremely poor scoring. But they might get points for showing why it is
>>>> such a bad idea.
>>> Exactly. That's what Tim said -- good for several interview questions.
>>> I think you missed the whole tone of the post. There were lots of
>>> signals, but surely "Very few cases with undefined behavior" should have
>>> sealed it.
>>>
>>>>> (I'm resisting the temptation to make an off-topic remark
>>>>> regarding the number of properties.)
>>>>> P.S. This response is meant to be more entertaining than
>>>>> useful. I do hope it helps broaden your thinking in
>>>>> searching for an answer.
>>>>
>>>> It's fine to give some "off the beaten track" solutions, but don't lie
>>>> about them.
>>> What is the lie? I don't see one.
>>>
>>
>> "Widely portable". In general, I thought his post might mislead people
>> into thinking it was a serious line of attack for the problem - creative
>> uses of floating point operations have been seen before for this kind of
>> thing. (I started writing a longer explanation, but scraped it to avoid
>> rambling off topic, so we can get back to the C.)
>
> Lying involves a deliberate intent to decisive. The intent here was to
> amuse and entertain. Now it's not always easy to get that across in a
> post, so there is a risk that misleading information (pretty much the
> whole of the post) could be taken seriously, but that's not lying.

That's a reasonable viewpoint. I think Tim should have considered that
his post might be misinterpreted and worded it differently (the
readership includes people relatively new to C, people for whom English
is a challenge, and people for who find it difficult to interpret
subtexts such as sarcasm or parody), but I agree that he did not
deliberately intend to deceive, so "lie" was an unfair and inappropriate
choice of words.

>
>> One thing that I did find interesting, however, was when I tried it on
>> godbolt and made a couple of test functions like :
>>
>> unsigned test1(void) { return high_bit_set(7654(; }
>>
>> gcc was happy to pre-calculate the correct result at compile time. I know
>> gcc (and clang) can simulate floating point hardware accurately at compile
>> time, but it surprised me that these compilers managed that.
>
> Interesting. I would not have expected that either. Mind you, there is
> no need to simulate the /behaviour/ of the hardware. The code relies
> only on the meaning of a set of bits when interpreted as floating point
> so it is, perhaps, at the easier end of the spectrum.
>

I am not an expert on the details of floating point - for my own use, I
am happy with the "they give approximate answers to real-number
calculations" interpretation. I am under the impression - perhaps
incorrectly - that some types of floating point calculations can give
slightly different results on different implementations. That is why
gcc includes a rather large library that aims to mimic real floating
point hardware for such compile-time calculation. But it is entirely
possible that this was not needed here, and the behaviour is fully
covered by IEEE floating point specifications.

Regardless, I thought the optimisation here was impressive.

A more useful challenge might be to find a way to express the problem
(for a given fixed size of integer type) in standard C in a way that gcc
and/or clang can turn into a "count leading zeros" or similar assembly
instruction. The most efficient implementation of this function is
typically achievable by using a C23 <stdbit.h> function, a compiler
__builtin instruction, or a target-specific intrinsic or inline
assembly. It would be nice to see a portable C implementation that gave
similar efficiency in the generated code, at least for some
compiler/target/flag combinations.