# Best way to set MSB

Discussion in 'C Programming' started by Tomás, Jun 2, 2006.

1. ### TomásGuest

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

Tomás, Jun 2, 2006

2. ### Richard BosGuest

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

Richard

Richard Bos, Jun 2, 2006

3. ### Andrew PoelstraGuest

On 2006-06-02, Richard Bos <> 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 */

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

Andrew Poelstra, Jun 2, 2006
4. ### Eric SosmanGuest

Andrew Poelstra wrote On 06/02/06 11:26,:
> On 2006-06-02, Richard Bos <> 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 */

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 "theoretical" 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

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

--

Eric Sosman, Jun 2, 2006
5. ### SM RyanGuest

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

SM Ryan, Jun 2, 2006
6. ### Eric SosmanGuest

SM Ryan wrote On 06/02/06 13:05,:
> #
> # What's the best portable way to set the MSB of an unsigned integer type?
>
> Is MSB a meaningful concept in portable code?

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, Jun 2, 2006
7. ### Andrew PoelstraGuest

On 2006-06-02, Eric Sosman <> wrote:
>
>
> Andrew Poelstra wrote On 06/02/06 11:26,:
>> On 2006-06-02, Richard Bos <> 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 */

>
> 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 "theoretical" 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
>
> If somebody offers you this "solution," I'd recommend
> that you not drink it.
>

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.

Andrew Poelstra, Jun 2, 2006
8. ### Eric SosmanGuest

Andrew Poelstra wrote On 06/02/06 14:59,:
> On 2006-06-02, Eric Sosman <> wrote:
>
>>
>>Andrew Poelstra wrote On 06/02/06 11:26,:
>>
>>>On 2006-06-02, Richard Bos <> 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 */

>>
>> 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 "theoretical" 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
>>
>> If somebody offers you this "solution," I'd recommend
>>that you not drink it.
>>

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

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

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, Jun 2, 2006
9. ### EricGuest

Tomás 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?
>
>
> -Tomás

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

Eric, Jun 2, 2006
10. ### Michael MairGuest

Eric schrieb:
> Tomás 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?

>
> unsigned integer type, hmm, you probably mean a 32 bit unsigned int although
> your example uses an 8 bit type.

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.

> Anyway for 32 bits v = v | 0x80000000;
> for 8 bits (like your example)
> v = v|0x80;

What is that the solution for?

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

Michael Mair, Jun 2, 2006
11. ### Peter NilssonGuest

Tomás wrote:
> What's the best portable way to set the MSB of an unsigned integer type?

Define best.

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

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

Peter Nilsson, Jun 3, 2006
12. ### peteGuest

Eric Sosman wrote:

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

That's what I use to set the MSB.

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

--
pete

pete, Jun 3, 2006