hongyu xiao
hongyu xiao

Reputation: 239

C++ avoid full shift in bit operation

template<class _Diff,
        class _Urng>
        class _Rng_from_urng
    {   // wrap a URNG as an RNG
    public:
        explicit _Rng_from_urng(_Urng& _Func)
            : _Ref(_Func), _Bits(CHAR_BIT * sizeof(_Udiff)), _Bmask(_Udiff(-1))
        {   // construct from URNG
            for (; (_Urng::max)() - (_Urng::min)() < _Bmask; _Bmask >>= 1)
                --_Bits;
        }

        _Diff operator()(_Diff _Index)
        {   // adapt _Urng closed range to [0, _Index)
            for (;;)
            {   // try a sample random value
                _Udiff _Ret = 0;    // random bits
                _Udiff _Mask = 0;   // 2^N - 1, _Ret is within [0, _Mask]

                while (_Mask < _Udiff(_Index - 1))
                {   // need more random bits
                    _Ret <<= _Bits - 1; // avoid full shift
                    _Ret <<= 1;
                    _Ret |= _Get_bits();
                    _Mask <<= _Bits - 1;    // avoid full shift
                    _Mask <<= 1;
                    _Mask |= _Bmask;
                }

                // _Ret is [0, _Mask], _Index - 1 <= _Mask, return if unbiased
                if (_Ret / _Index < _Mask / _Index
                    || _Mask % _Index == _Udiff(_Index - 1))
                    return (_Ret % _Index);
            }
        }
    };
}

The above code is pasted from stl. What the "avoid full shift" means? I think the two bit shift can be intecoplated into single operation.

_Ret <<= _Bits - 1; // avoid full shift 
_Ret <<= 1;

I change the codes as:

_Ret<<=_Bits;

What differs here?

Upvotes: 0

Views: 69

Answers (1)

Swordfish
Swordfish

Reputation: 13144

[expr.shift]/1

7.6.7 Shift operators

  1. The shift operators << and >> group left-to-right.

    shift-expression:

    additive-expression

    shift-expression << additive-expression

    shift-expression >> additive-expression

    The operands shall be of integral or unscoped enumeration type and integral promotions are performed. The type of the result is that of the promoted left operand. The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

Upvotes: 5

Related Questions