Reputation: 239
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
Reputation: 13144
7.6.7 Shift operators
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