Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #221103 > unrolled thread

portable way to get highest bit set?

Back to article view | Back to comp.lang.c

Contents

  portable way to get highest bit set? candycanearter07 <no@thanks.net> - 2023-10-11 01:56 -0500
    Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-11 10:27 +0300
      Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 11:31 +0200
        Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-11 12:33 +0300
          Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 13:58 +0200
            Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-11 15:17 +0300
              Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 16:22 +0200
                Re: portable way to get highest bit set? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2023-10-11 18:08 +0300
                Re: portable way to get highest bit set? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-10-11 17:20 +0100
                  Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 18:28 +0200
      Re: portable way to get highest bit set? candycanearter07 <no@thanks.net> - 2023-10-11 11:19 -0500
        Re: portable way to get highest bit set? David Brown <david.brown@hesbynett.no> - 2023-10-11 18:45 +0200
        Re: portable way to get highest bit set? Ian C <deathstation9000@gmail.com> - 2023-10-11 18:03 +0100
          Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-11 10:17 -0700
        Re: portable way to get highest bit set? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-10-11 10:34 -0700
        Re: portable way to get highest bit set? Richard Harnden <richard.nospam@gmail.invalid> - 2023-10-11 19:02 +0100
    Re: portable way to get highest bit set? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-10-11 13:56 +0100
    Re: portable way to get highest bit set? Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2023-10-11 14:54 +0000
    Re: portable way to get highest bit set? Kaz Kylheku <864-117-4973@kylheku.com> - 2023-10-11 17:23 +0000

#221103 — portable way to get highest bit set?

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

[toc] | [next] | [standalone]

#221506

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

[toc] | [prev] | [next] | [standalone]

#223350

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?

[toc] | [prev] | [next] | [standalone]

#223379

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

[toc] | [prev] | [next] | [standalone]

#224982

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.

[toc] | [prev] | [next] | [standalone]

#225134

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

[toc] | [prev] | [next] | [standalone]

#226475

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.

[toc] | [prev] | [next] | [standalone]

#227024

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

[toc] | [prev] | [next] | [standalone]

#228061

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.

[toc] | [prev] | [next] | [standalone]

#228097

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.

[toc] | [prev] | [next] | [standalone]

#228045

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

[toc] | [prev] | [next] | [standalone]

#228236

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.

[toc] | [prev] | [next] | [standalone]

#228378

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

[toc] | [prev] | [next] | [standalone]

#228443

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?

[toc] | [prev] | [next] | [standalone]

#228549

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"

[toc] | [prev] | [next] | [standalone]

#228649

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

[toc] | [prev] | [next] | [standalone]

#225463

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.

[toc] | [prev] | [next] | [standalone]

#226858

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"

[toc] | [prev] | [next] | [standalone]

#228480

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web