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]

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]

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 */

 

[Eric Sosman]

Andrew Poelstra wrote On 06/02/06 11:26,:

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?

 

[Eric Sosman]

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.

 

[Andrew Poelstra]

Andrew Poelstra wrote On 06/02/06 11:26,:

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.

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,:

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

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]

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

 

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

 

[pete]

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.