Best way to set MSB

[Tomás]

What's the best portable way to set the MSB of an unsigned integer type?

Is the following any good?:


Start of with: 0000 0000

Flip all the bits: 1111 1111

Shift once to the right: 0111 1111

Flip all the bits: 1000 0000


Here it is done in code:

typedef unsigned short UIntType;

UIntType msb_only =
~( ~( (UIntType)0 ) >> 1 );


Is there a better way?


-Tomás

[Richard Bos]

Re: Best way to set MSB

"Tomás" <No.Email@Addre ss> wrote:
[color=blue]
> What's the best portable way to set the MSB of an unsigned integer type?
>
> Is the following any good?:
>
> Start of with: 0000 0000
> Flip all the bits: 1111 1111
> Shift once to the right: 0111 1111
> Flip all the bits: 1000 0000
>
> Here it is done in code:
>
> typedef unsigned short UIntType;
>
> UIntType msb_only =
> ~( ~( (UIntType)0 ) >> 1 );
>
> Is there a better way?[/color]

Because of the way unsigned integer overflow is handled in C, you can
replace the first two steps with converting -1 to the desired type. This
results in

UIntType msb_only = ~( (UIntType)-1 >> 1 );

This is obviously shorter; up to you to decide whether you find it as
legible.

Richard

[Andrew Poelstra]

Re: Best way to set MSB

On 2006-06-02, Richard Bos <rlb@hoekstra-uitgeverij.nl> wrote:[color=blue]
> "Tomás" <No.Email@Addre ss> wrote:
>[color=green]
>> What's the best portable way to set the MSB of an unsigned integer type?
>>
>> Is the following any good?:
>>
>> Start of with: 0000 0000
>> Flip all the bits: 1111 1111
>> Shift once to the right: 0111 1111
>> Flip all the bits: 1000 0000
>>
>> Here it is done in code:
>>
>> typedef unsigned short UIntType;
>>
>> UIntType msb_only =
>> ~( ~( (UIntType)0 ) >> 1 );
>>
>> Is there a better way?[/color]
>
> Because of the way unsigned integer overflow is handled in C, you can
> replace the first two steps with converting -1 to the desired type. This
> results in
>
> UIntType msb_only = ~( (UIntType)-1 >> 1 );
>
> This is obviously shorter; up to you to decide whether you find it as
> legible.[/color]

I would take one and left-shift it sizeof(type) * CHAR_BIT.

This solution is pretty easy to read:

int m = 1 << (sizeof m * CHAR_BIT) /* Set MSB */

--
Andrew Poelstra < http://www.wpsoftware.net/blog >
To email me, use "apoelstra" at the above address.
You can lead a blind man to water but you can't make him chug it.

[Eric Sosman]

Re: Best way to set MSB



Andrew Poelstra wrote On 06/02/06 11:26,:[color=blue]
> On 2006-06-02, Richard Bos <rlb@hoekstra-uitgeverij.nl> wrote:
> [color=green]
>>"Tomás" <No.Email@Addre ss> wrote:
>>
>>[color=darkred]
>>>What's the best portable way to set the MSB of an unsigned integer type?
>>>
>>>Is the following any good?:
>>>
>>> Start of with: 0000 0000
>>> Flip all the bits: 1111 1111
>>> Shift once to the right: 0111 1111
>>> Flip all the bits: 1000 0000
>>>
>>>Here it is done in code:
>>>
>>> typedef unsigned short UIntType;
>>>
>>> UIntType msb_only =
>>> ~( ~( (UIntType)0 ) >> 1 );
>>>
>>>Is there a better way?[/color]
>>
>>Because of the way unsigned integer overflow is handled in C, you can
>>replace the first two steps with converting -1 to the desired type. This
>>results in
>>
>> UIntType msb_only = ~( (UIntType)-1 >> 1 );
>>
>>This is obviously shorter; up to you to decide whether you find it as
>>legible.[/color]
>
>
> I would take one and left-shift it sizeof(type) * CHAR_BIT.
>
> This solution is pretty easy to read:
>
> int m = 1 << (sizeof m * CHAR_BIT) /* Set MSB */[/color]

This is wrong. R-O-N-G, wrong. Where to begin?

- It assumes all bits of an `int' are value bits, and
ignores the possibility of padding bits. All right,
that may be more of a "theoretica l" than an "actual"
problem, but it's not the only one ...

- Shift operators are only defined when the shift
distance is strictly less than the width of the
shifted value. There's a `-1' missing, without which
the above yields undefined behavior (6.5.7/3). On
actual machines, the likely result is `m=0' or `m=1'.

- Even with the `-1', the above is an attempt to shift
a value bit into the sign position, which once again
yields undefined behavior (6.5.7/4). The missing `-1'
should perhaps be a `-2', depending on how you choose
to define the "M"SB of a signed integer.

- Speaking of signed integers, the O.P. specifically
asked about *un*signed integers.

If somebody offers you this "solution," I'd recommend
that you not drink it.

--
Eric.Sosman@sun .com

[SM Ryan]

Re: Best way to set MSB

"Tomás" <No.Email@Addre ss> wrote:
#
# What's the best portable way to set the MSB of an unsigned integer type?

Is MSB a meaningful concept in portable code?

--
SM Ryan http://www.rawbw.com/~wyrmwif/
Don't say anything. Especially you.

[Eric Sosman]

Re: Best way to set MSB



SM Ryan wrote On 06/02/06 13:05,:[color=blue]
> "Tomás" <No.Email@Addre ss> wrote:
> #
> # What's the best portable way to set the MSB of an unsigned integer type?
>
> Is MSB a meaningful concept in portable code?[/color]

It's portable in the same sense that UINT_MAX is
portable. Every implementation has a UINT_MAX, even
though the value of UINT_MAX is implementation-dependent.
Every unsigned integer type has a Most Significant Bit,
even though its value is implementation-dependent.

--
Eric.Sosman@sun .com

[Andrew Poelstra]

Re: Best way to set MSB

On 2006-06-02, Eric Sosman <Eric.Sosman@su n.com> wrote:[color=blue]
>
>
> Andrew Poelstra wrote On 06/02/06 11:26,:[color=green]
>> On 2006-06-02, Richard Bos <rlb@hoekstra-uitgeverij.nl> wrote:
>>[color=darkred]
>>>"Tomás" <No.Email@Addre ss> wrote:
>>>
>>>
>>>>What's the best portable way to set the MSB of an unsigned integer type?
>>>>
>>>>Is the following any good?:
>>>>
>>>> Start of with: 0000 0000
>>>> Flip all the bits: 1111 1111
>>>> Shift once to the right: 0111 1111
>>>> Flip all the bits: 1000 0000
>>>>
>>>>Here it is done in code:
>>>>
>>>> typedef unsigned short UIntType;
>>>>
>>>> UIntType msb_only =
>>>> ~( ~( (UIntType)0 ) >> 1 );
>>>>
>>>>Is there a better way?
>>>
>>>Because of the way unsigned integer overflow is handled in C, you can
>>>replace the first two steps with converting -1 to the desired type. This
>>>results in
>>>
>>> UIntType msb_only = ~( (UIntType)-1 >> 1 );
>>>
>>>This is obviously shorter; up to you to decide whether you find it as
>>>legible.[/color]
>>
>>
>> I would take one and left-shift it sizeof(type) * CHAR_BIT.
>>
>> This solution is pretty easy to read:
>>
>> int m = 1 << (sizeof m * CHAR_BIT) /* Set MSB */[/color]
>
> This is wrong. R-O-N-G, wrong. Where to begin?
>
> - It assumes all bits of an `int' are value bits, and
> ignores the possibility of padding bits. All right,
> that may be more of a "theoretica l" than an "actual"
> problem, but it's not the only one ...
>
> - Shift operators are only defined when the shift
> distance is strictly less than the width of the
> shifted value. There's a `-1' missing, without which
> the above yields undefined behavior (6.5.7/3). On
> actual machines, the likely result is `m=0' or `m=1'.
>
> - Even with the `-1', the above is an attempt to shift
> a value bit into the sign position, which once again
> yields undefined behavior (6.5.7/4). The missing `-1'
> should perhaps be a `-2', depending on how you choose
> to define the "M"SB of a signed integer.
>
> - Speaking of signed integers, the O.P. specifically
> asked about *un*signed integers.
>
> If somebody offers you this "solution," I'd recommend
> that you not drink it.
>[/color]

Point 1 is generally not a concern for primitive types.
Point 2 is correct; I did forget a -1.
Point 3 is eliminated by point 4, and in fact.

My definition of MSB is leftmost bit. My solution (with a -1)
works by that definition.

--
Andrew Poelstra < http://www.wpsoftware.net/blog >
To email me, use "apoelstra" at the above address.
You can lead a blind man to water but you can't make him chug it.

[Eric Sosman]

Re: Best way to set MSB



Andrew Poelstra wrote On 06/02/06 14:59,:[color=blue]
> On 2006-06-02, Eric Sosman <Eric.Sosman@su n.com> wrote:
> [color=green]
>>
>>Andrew Poelstra wrote On 06/02/06 11:26,:
>>[color=darkred]
>>>On 2006-06-02, Richard Bos <rlb@hoekstra-uitgeverij.nl> wrote:
>>>
>>>
>>>>"Tomás" <No.Email@Addre ss> wrote:
>>>>
>>>>
>>>>
>>>>>What's the best portable way to set the MSB of an unsigned integer type?
>>>>>
>>>>>Is the following any good?:
>>>>>
>>>>> Start of with: 0000 0000
>>>>> Flip all the bits: 1111 1111
>>>>> Shift once to the right: 0111 1111
>>>>> Flip all the bits: 1000 0000
>>>>>
>>>>>Here it is done in code:
>>>>>
>>>>> typedef unsigned short UIntType;
>>>>>
>>>>> UIntType msb_only =
>>>>> ~( ~( (UIntType)0 ) >> 1 );
>>>>>
>>>>>Is there a better way?
>>>>
>>>>Because of the way unsigned integer overflow is handled in C, you can
>>>>replace the first two steps with converting -1 to the desired type. This
>>>>results in
>>>>
>>>> UIntType msb_only = ~( (UIntType)-1 >> 1 );
>>>>
>>>>This is obviously shorter; up to you to decide whether you find it as
>>>>legible.
>>>
>>>
>>>I would take one and left-shift it sizeof(type) * CHAR_BIT.
>>>
>>>This solution is pretty easy to read:
>>>
>>>int m = 1 << (sizeof m * CHAR_BIT) /* Set MSB */[/color]
>>
>> This is wrong. R-O-N-G, wrong. Where to begin?
>>
>> - It assumes all bits of an `int' are value bits, and
>> ignores the possibility of padding bits. All right,
>> that may be more of a "theoretica l" than an "actual"
>> problem, but it's not the only one ...
>>
>> - Shift operators are only defined when the shift
>> distance is strictly less than the width of the
>> shifted value. There's a `-1' missing, without which
>> the above yields undefined behavior (6.5.7/3). On
>> actual machines, the likely result is `m=0' or `m=1'.
>>
>> - Even with the `-1', the above is an attempt to shift
>> a value bit into the sign position, which once again
>> yields undefined behavior (6.5.7/4). The missing `-1'
>> should perhaps be a `-2', depending on how you choose
>> to define the "M"SB of a signed integer.
>>
>> - Speaking of signed integers, the O.P. specifically
>> asked about *un*signed integers.
>>
>> If somebody offers you this "solution," I'd recommend
>>that you not drink it.
>>[/color]
>
>
> Point 1 is generally not a concern for primitive types.
> Point 2 is correct; I did forget a -1.
> Point 3 is eliminated by point 4, and in fact.
>
> My definition of MSB is leftmost bit. My solution (with a -1)
> works by that definition.[/color]

Well, it works once you've changed from `int' to
`unsigned int' (in *two* places) and tacked on a `-1',
provided there are no padding bits. Putting all this
together and generalizing to types that might be wider
than an `int', you wind up with

UIntType m = (UIntType)1 << (CHAR_BIT * sizeof m - 1);

Readability is in the eye of the beholder, but I don't
find this more readable than

UIntType m = ((UIntType)-1 >> 1) + 1;

... which has the virtues of being both bullet-proof and
shorter. This beholder's eye sees no reason to prefer
the longer, shakier construct.

By the way, note that `~((UIntType)-1 >> 1)' is not
guaranteed to work. If UIntType is sufficiently narrow it
will be subject to the "integer promotions" and the value
inside the parentheses will be a non-negative signed `int'
(non-negative because otherwise promotion wouldn't have
occurred). Applying `~' yields a non-positive value, but
just what that value is depends on how the system represents
negative integers. On a ones' complement machine, converting
back to UIntType would give an unintended result.

--
Eric.Sosman@sun .com

[Eric]

Re: Best way to set MSB

Tomás wrote:
[color=blue]
>
> What's the best portable way to set the MSB of an unsigned integer type?
>
> Is the following any good?:
>
>
> Start of with: 0000 0000
>
> Flip all the bits: 1111 1111
>
> Shift once to the right: 0111 1111
>
> Flip all the bits: 1000 0000
>
>
> Here it is done in code:
>
> typedef unsigned short UIntType;
>
> UIntType msb_only =
> ~( ~( (UIntType)0 ) >> 1 );
>
>
> Is there a better way?
>
>
> -Tomás[/color]

unsigned integer type, hmm, you probably mean a 32 bit unsigned int although
your example uses an 8 bit type.
Anyway for 32 bits v = v | 0x80000000;
for 8 bits (like your example)
v = v|0x80;
Eric

[Michael Mair]

Re: Best way to set MSB

Eric schrieb:[color=blue]
> Tomás wrote:
>[color=green]
>>What's the best portable way to set the MSB of an unsigned integer type?
>>
>>Is the following any good?:
>>
>> Start of with: 0000 0000
>>
>> Flip all the bits: 1111 1111
>>
>> Shift once to the right: 0111 1111
>>
>> Flip all the bits: 1000 0000
>>
>>
>>Here it is done in code:
>>
>> typedef unsigned short UIntType;
>>
>> UIntType msb_only =
>> ~( ~( (UIntType)0 ) >> 1 );
>>
>>Is there a better way?[/color]
>
> unsigned integer type, hmm, you probably mean a 32 bit unsigned int although
> your example uses an 8 bit type.[/color]

The OP clearly stated that he is looking for a general solution for
unsigned integer types. The thing is that you do _not_ know the number
of value bits of the type beforehand; assuming padding bits, it may be
not equal to the type's width.
[color=blue]
> Anyway for 32 bits v = v | 0x80000000;
> for 8 bits (like your example)
> v = v|0x80;[/color]

What is that the solution for?


Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Peter Nilsson]

Re: Best way to set MSB

Tomás wrote:[color=blue]
> What's the best portable way to set the MSB of an unsigned integer type?[/color]

Define best.
[color=blue]
> Is the following any good?:
>
> Start of with: 0000 0000
> Flip all the bits: 1111 1111
> Shift once to the right: 0111 1111
> Flip all the bits: 1000 0000
>
> Here it is done in code:
>
> typedef unsigned short UIntType;
>
> UIntType msb_only =
> ~( ~( (UIntType)0 ) >> 1 );[/color]

This can fail if UIntType has a rank lower than int. Try...

UIntType msb_only = ((uintN_t) -1)/2+1;

If UIntType is unsigned or unsigned long, then the notation is
even cleaner, e.g. ...

unsigned msb = -1u/2+1;

--
Peter

[pete]

Re: Best way to set MSB

Eric Sosman wrote:
[color=blue]
> UIntType m = ((UIntType)-1 >> 1) + 1;[/color]

That's what I use to set the MSB.

It's both simple and bulletproof, as you have already stated.

--
pete