Hi,

What is the best/most portable way to get the highest bit set?

ie. 011010001
to 010000000
--
user <candycane> is generated from /dev/urandom

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?

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

On 11/10/2023 09: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?
>

And what is your definition of "best" and "most portable" ?

"Best" can mean smallest, neatest, fastest, and that can depend highly
on the compiler, target and flags.

"Portable" can mean relying only on pure standard C (and if so, which
standard version?), or one compiler but many targets, or one target and
many compilers, or a group of common targets and compilers excluding
"unusual" ones.

And what types do you want to support? All integer types, or just some
specific ones?

What is the specification for the function you want? In particular,
what should it do for 0? Do you really want a result with one bit set,
or do you actually want the bit number?

David Brown:

> And what types do you want to support? All integer types,
> or just some specific ones?

The OP's example shows a byte -- an 8-bit value, but I
encourage them to try and publish their own solution first.

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

On 11/10/2023 11:33, Anton Shepelev wrote:
> David Brown:
>
>> And what types do you want to support? All integer types,
>> or just some specific ones?
>
> The OP's example shows a byte -- an 8-bit value, but I
> encourage them to try and publish their own solution first.
>

I fully agree with that suggestion.

But he/she also needs to say if 8-bit values are all that are of
interest, when considering portability.

David Brown:

> But he/she also needs to say if 8-bit values are all that
> are of interest, when considering portability.

Yes, endianness, and then a hackish way to hanle it is to
use socket functions. Hackish, because conceptualy that
means the reliance of a general low-level function on a
more specific and higher-level function/library.

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

candycanearter07 <no@thanks.net> writes:

> What is the best/most portable way to get the highest bit set?
>
> ie. 011010001
> to 010000000

While bit twiddling solutions will be needed for some years, it's worth
noting that C23 has <stdbit.h> which includes functions (including
type-generic ones) like stdc_bit_floor. C++ has had something similar
since C++20.

--
Ben.

On 11/10/2023 14:17, Anton Shepelev wrote:
> David Brown:
>
>> But he/she also needs to say if 8-bit values are all that
>> are of interest, when considering portability.
>
> Yes, endianness, and then a hackish way to hanle it is to
> use socket functions. Hackish, because conceptualy that
> means the reliance of a general low-level function on a
> more specific and higher-level function/library.
>

Endianness should not be an issue. The question is about values, and
values don't have endianness. Only storage has endianness.

On Wed, 11 Oct 2023 01:56:49 -0500, candycanearter07 wrote:

> Hi,
>
> What is the best/most portable way to get the highest bit set?
>
> ie. 011010001 to 010000000

What have you tried?

I can think of one way, but it may not be the "best" or "most portable"
way of setting the highest bit of a value, and it /does/ have some
limitations. Show your work, and I might show mine.

--
Lew Pitcher
"In Skills We Trust"

David Brown corrected Anton Shepelev:

> Endianness should not be an issue. The question is about
> values, and values don't have endianness. Only storage
> has endianness.

I blundered bad!

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

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
--
user <candycane> is generated from /dev/urandom

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

> Endianness should not be an issue. The question is about values, and
> values don't have endianness. Only storage has endianness.

But solutions could use the byte representation and endianness would
then come into it.

--
Ben.

On 11/10/2023 18:20, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
>
>> Endianness should not be an issue. The question is about values, and
>> values don't have endianness. Only storage has endianness.
>
> But solutions could use the byte representation and endianness would
> then come into it.
>

Sure. But that would be an artefact of a particular solution, rather
than being inherent in the problem.

On 11/10/2023 18: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

OK, that's a start.

First, I strongly recommend you use unsigned integer types for anything
involving bit manipulation, masking, shifting, etc. You avoid any
awkwardness or potential undefined behaviour, and have the full range of
the bits. I also recommend using the C99 <stdint.h> size-specific
types. They are not quite as portable as the standard integer types,
but they are portable enough for the vast majority of real-world cases,
and you are always sure of the exact number of bits, which is often
clearer IMHO. (Note that not all C programmers will agree with my
preferences here.)

Now, you still have not answered what you mean by "portable". How I
would approach this would depend significantly on that. If "portable"
meant "any target for gcc or clang", I'd be using gcc builtins. If it
meant "any C23 compiler", I'd likely use "auto" in my solution. If it
meant "any C11 or C17 compiler", I'd use "_Generic". If it meant "any
C99 compiler", I'd use <stdint.h> types. If "portable" means any
standard C version, with any hypothetical implementation, it's going to
get messy putting together a solution that will work even for extended
unsigned integer types that are bigger than "unsigned long".

These different approaches can have significantly different
efficiencies, if that is important, but each has different requirements
of the standard and compiler.

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

Ian C <deathstation9000@gmail.com> writes:

> 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.

Wouldn't you first write a test function to be sure the
value returned is correct? ;)

I found it harder to write a correct test function than
to write a function that just returns a correct value.
Interesting, eh?

On 2023-10-11, candycanearter07 <no@thanks.net> wrote:
> Hi,
>
> What is the best/most portable way to get the highest bit set?
>
> ie. 011010001
> to 010000000

I don't know about best or portable, but in the run-time of the
TXR language, I solved it like this (see highest_bit function):

https://www.kylheku.com/cgit/txr/tree/arith.c

If we have GNU C builtin primitives for this, we use them.
Otherwise do a statically coded binary search (no loop).

The build configuration system provides constants like SIZEOF_PTR.

That is not essential because you can just use regular conditionals.

--
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.

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
* No looping or testing
* Large domain of inputs supported
* Widely portable
* Very few cases with undefined behavior
* Forms an excellent basis for several interview questions
* Sure to launch a torrent of followups on its pros and cons

(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.

[*] that might be a baker's dozen, due to off-by-one error

[**] for some values of "favorite"

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;

Why 0x100000000 and not 0x800000000?

>
> I'm trying to find something size independent, though.
> Or at least able to be swapped out with a #define

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;

ret = (unsigned long)pow(2., (double)(unsigned
long)(log((double)val) / log(2.)));

printf("%lu -> %lu", val, ret);

return 0;
}

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.

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

candycanearter07 wrote:

> Hi,
>
> What is the best/most portable way to get the highest bit set?
>
> ie. 011010001 to 010000000

#include <stdbit.h>

unsigned char highest_bit_setc(unsigned char x)
{ return stdc_first_leading_one(x) ? (1 << stdc_first_leading_one(x)
- 1) : 0;
}

/* Repeat for all appropriate types and then probably make a generic macro
for all the subroutines. */

--
Blue-Maned_Hawk│shortens to
Hawk│/
blu.mɛin.dÊ°ak/
│he/him/his/himself/Mr.
bluemanedhawk.github.io
Minor vehicular events!

Blue-Maned_Hawk <bluemanedhawk@invalid.invalid> writes:
> candycanearter07 wrote:
>> What is the best/most portable way to get the highest bit set?
>>
>> ie. 011010001 to 010000000
>
> #include <stdbit.h>
>
> unsigned char highest_bit_setc(unsigned char x)
> {
> return stdc_first_leading_one(x) ? (1 << stdc_first_leading_one(x)
> - 1) : 0;
> }
>
> /* Repeat for all appropriate types and then probably make a generic macro
> for all the subroutines. */

A solution that depends on a header that's introduced in C23, a standard
that hasn't been published yet, is hardly portable.

BTW, here's what your signature looks like in my newsreader (Gnus):

Blue-Maned_HawkÃ\203\203\203\203Ã\203\203\202Ã\203\202Ã\202¢\224\202shortens to
HawkÃ\203\203\203\203Ã\203\203\202Ã\203\202Ã\202¢\224\202/
blu.mÃ\203\203\203\203\211\233in.dÃ\203\203\203\203\212Ã\203\203\203\202Ã\203\203\202Ã\203\202Ã\202°ak/
Ã\203\203\203\203Ã\203\203\202Ã\203\202Ã\202¢\224\202he/him/his/himself/Mr.
bluemanedhawk.github.io
Minor vehicular events!

And in Thunderbird:

Blue-Maned_HawkÃÃÃâshortens to
HawkÃÃÃâ/
blu.mÃin.dÃÃÃÃðak/
ÃÃÃâhe/him/his/himself/Mr.
bluemanedhawk.github.io
Minor vehicular events!

--
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 2023-10-11, candycanearter07 <no@thanks.net> wrote:
> Hi,
>
> What is the best/most portable way to get the highest bit set?
>
> ie. 011010001
> to 010000000

I just noticed you really want the *mask* of the highest bit set,
not its position.

That's pretty easy to do in a portable way.

First we calculate this fully saturated mask:

011111111

then, we just right shift that to produce this mask:

001111111

and XOR them together to get

010000000

Now how do we get that first mask? Like ethis:

Start with x:

011010001 x

OR it with x >> 1:

| 001101000 x >> 1
------------
= 011111001

Take that to be the new x. OR it with x >> 2

011111001
| 000111110
------------
= 011111111

And here we are done; but we continue to x >> 4 and x >> 8.

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

Note that this has no branches whatsoever. There are data hazards
because we are updating an accumulator in place; that's likely
going to cost some pipeline-level parallelism.

Note that the numbeer of |= steps in fill_mask_down is the log2
of the number of bits. The 64 bit code just ads x |= x >> 32.

--
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.

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

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

--
Ben.