bit shifting...undefined behaviour?

[Sebastiani]

given the following code:

unsigned
mask = (~unsigned() << 1) >> 1;

one would expect the result to have all but the most significant bit set. but when I compile this with gcc, all bits are set. is this addressed by the standard?

[anon]

This shouldn't even compile. Did you mean:

unsigned
mask = (~0u << 1) >> 1;

Or

unsigned
mask = (~unsigned() << 1) >> 1;

Both output 2147483647.

By the way, is the left-shift needed?

[CornedBee]

~unsigned

This even compiles?

[Sebastiani]

sorry, that was a typo. anyway, to put it more clearly, shouldn't a shift always produce cleared bits in the vacated positions (unless the number of shifts exceeds the size of the data type, which is undefined)?

>> Both output 2147483647.

well, assuming a 4 byte integer, yes. but I get different results depending on the compiler.

>> By the way, is the left-shift needed?

no. I was just giving an example.

[twomers]

#include <bitset>
#include <iostream>

int main( void ) {
  std::bitset<sizeof(unsigned)*8> mask_set( (~unsigned()<<1)>>1 );
  std::cout<< mask_set;

  return 0;
}

My output: "01111111111111111111111111111111" ... seems right, no?

[robatino]

sorry, that was a typo. anyway, to put it more clearly, shouldn't a shift always produce cleared bits in the vacated positions (unless the number of shifts exceeds the size of the data type, which is undefined)?

For a left shift, yes. For a right shift, it depends on whether the integral type is signed or unsigned. For an unsigned type, yes again. For a signed type, it does either an arithmetic shift or a logical shift, depending on the machine (logical shift is what you're thinking of).

http://en.wikipedia.org/wiki/Arithmetic_shift
http://en.wikipedia.org/wiki/Logical_shift

Edit: AFAIK, nothing undefined happens if the number of shifts exceeds the size of the data type, it does what you would expect.

[Sebastiani]

right, thanks. I'm wondering if the two shifts were just optimized out? I'll check it out.

[matsp]

right, thanks. I'm wondering if the two shifts were just optimized out? I'll check it out.

Whilst it's possible that some compiler optimizes the shifts out, I wouldn't think that's really appropriate, as a right shift on an unsigned value should shift in zero's, and a right shift should always shift in zero's (signed or unsigned).

But check the code to make sure.

--
Mats

[CornedBee]

My gcc 4.1 gives the right result.

[Sebastiani]

o.k., I'm back with a working example of this wierd behaviour. =)

template <typename Unsigned>
inline
Unsigned
half_max(void)
{
    static
    Unsigned
    value = ~Unsigned() >> 1;
    return value;
}

when called like this:

int
main(void)
{
       std::cout << (int)half_max<unsigned char>() << std::endl;
}

the output is: 255

however, when I employ a temporary during the initialization:

template <typename Unsigned>
inline
Unsigned
half_max(void)
{
    static
    Unsigned
    value = Unsigned(~Unsigned()) >> 1;
    return value;
}

the output is: 127

any ideas as to what is causing this to happen?

[twomers]

You try the debugger? There's a lot of that going around these days.

[brewbuck]

When you use ~ to invert bits, the result is not the same type as what you put in -- the result is AN INT. Given this information, you can probably figure out what's happening with that temporary.

EDIT: In other words, the type of "~Unsigned()" is NOT "Unsigned."

[Sebastiani]

you're right! and all along I thought it was a compiler bug, when in fact it was just another backward idiosyncrasy of the language. thank you very much, brewbuck.

[Sebastiani]

o.k. so considering the following code:

template <typename Integer>
Integer
generate_inversion_mask_(void)
{
        Integer
        zero = 0,
        one = 1,
        mask = zero;
        for(Integer bit = one; bit != zero; bit <<= one)
        {
                mask |= bit;
        }
        return mask;
}
 
template <typename Integer>
inline
Integer
inverse(Integer value)
{
        static
        Integer
        mask = generate_inversion_mask_<Integer>();
        return value ^ mask;
}
 
template <typename Unsigned>
inline
Unsigned
half_max(void)
{
    static
    Unsigned
    value = inverse(Unsigned()) >> 1;
    return value;
}

is that a guaranteed solution?

[edit]
come to think of it, I may be over-thinking this. the standard probably guarantees the result of a bitwise operations to fit into the largest integral type, which would mean the simplest solution would be to use a temporary - is that correct?
[/edit]

[CornedBee]

It looks guaranteed, but have you tried:

template <typename Unsigned>
inline Unsigned half_max()
{
  return std::numeric_limit<Unsigned>::max() >> 1;
}

?