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
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
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
Andrew Poelstra wrote On 06/02/06 11:26,:
> On 2006-06-02, Richard Bos <r...@hoekstra-uitgeverij.nl> wrote:
>
>>"Tomás" <No.Email@Address> 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
asked about *un*signed integers.
If somebody offers you this "solution," I'd recommend
that you not drink it.
SM Ryan
#
# 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
SM Ryan wrote On 06/02/06 13:05,:
> "Tomás" <No.Email@Address> wrote:
> #
> # 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.
Andrew Poelstra
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.
Eric Sosman
Andrew Poelstra wrote On 06/02/06 14:59,:
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
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
> 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?
>
> 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.
Peter Nilsson
> 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
pete
> 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