Velocity Reviews > Best way to set MSB

Best way to set MSB

Tomás
Guest
Posts: n/a

 06-02-2006

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
Guest
Posts: n/a

 06-02-2006

> 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

Andrew Poelstra
Guest
Posts: n/a

 06-02-2006
On 2006-06-02, Richard Bos <(E-Mail Removed)> 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.

Eric Sosman
Guest
Posts: n/a

 06-02-2006

Andrew Poelstra wrote On 06/02/06 11:26,:
> On 2006-06-02, Richard Bos <(E-Mail Removed)> 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.

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

SM Ryan
Guest
Posts: n/a

 06-02-2006
#
# 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
Guest
Posts: n/a

 06-02-2006

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.

--
(E-Mail Removed)

Andrew Poelstra
Guest
Posts: n/a

 06-02-2006
On 2006-06-02, Eric Sosman <(E-Mail Removed)> wrote:
>
>
> Andrew Poelstra wrote On 06/02/06 11:26,:
>> On 2006-06-02, Richard Bos <(E-Mail Removed)> 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.

Eric Sosman
Guest
Posts: n/a

 06-02-2006

Andrew Poelstra wrote On 06/02/06 14:59,:
> On 2006-06-02, Eric Sosman <(E-Mail Removed)> wrote:
>
>>
>>Andrew Poelstra wrote On 06/02/06 11:26,:
>>
>>>On 2006-06-02, Richard Bos <(E-Mail Removed)> 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.

--
(E-Mail Removed)

Eric
Guest
Posts: n/a

 06-02-2006
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

Michael Mair
Guest
Posts: n/a

 06-02-2006
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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Niv (KP) VHDL 2 02-03-2009 02:36 PM sameergn@gmail.com Java 0 06-07-2005 06:49 AM no spam C Programming 29 01-24-2005 04:06 AM =?ISO-8859-1?Q?Johan_Bernsp=E5ng?= VHDL 20 08-02-2004 05:56 PM Andi Hotz C++ 3 11-21-2003 07:30 PM