Best way to set MSB

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

  1. Tomás

    Tomás Guest

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

  2. Tomás

    Richard Bos Guest

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

    Richard
     
    Richard Bos, Jun 2, 2006
    #2
    1. Advertising

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

    --
    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
    #3
  4. Tomás

    Eric Sosman Guest

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

    --
     
    Eric Sosman, Jun 2, 2006
    #4
  5. Tomás

    SM Ryan Guest

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

    --
    SM Ryan http://www.rawbw.com/~wyrmwif/
    Don't say anything. Especially you.
     
    SM Ryan, Jun 2, 2006
    #5
  6. Tomás

    Eric Sosman Guest

    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.

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


    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
    #7
  8. Tomás

    Eric Sosman Guest

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

    >
    >
    > 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 Sosman, Jun 2, 2006
    #8
  9. Tomás

    Eric Guest

    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
    #9
  10. Tomás

    Michael Mair Guest

    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
    #10
  11. 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
    #11
  12. Tomás

    pete Guest

    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
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=

    determining of the position of the MSB

    =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=, Jul 27, 2004, in forum: VHDL
    Replies:
    20
    Views:
    3,031
    Jonathan Bromley
    Aug 2, 2004
  2. Replies:
    0
    Views:
    648
  3. Andi Hotz

    How to get the MSB?

    Andi Hotz, Nov 21, 2003, in forum: C++
    Replies:
    3
    Views:
    345
    Mike Wahler
    Nov 21, 2003
  4. no spam
    Replies:
    29
    Views:
    737
    Dave Thompson
    Jan 24, 2005
  5. Niv (KP)
    Replies:
    2
    Views:
    512
    Niv (KP)
    Feb 3, 2009
Loading...

Share This Page