https://llvm.org/bugs/show_bug.cgi?id=24267
Bug ID: 24267
Summary: uniform_int_distribution may not be uniform in certain
conditions
Product: libc++
Version: unspecified
Hardware: Other
OS: All
Status: NEW
Severity: normal
Priority: P
Component: All Bugs
Assignee: unassignedclangb...@nondot.org
Reporter: sne...@dei.uc.pt
CC: llvmbugs@cs.uiuc.edu, mclow.li...@gmail.com
Classification: Unclassified
The libc++ uniform_int_distribution algorithm works, essentially, by figuring
out the number of bits in the specified range [a, b], and then generating
numbers with that amount of bits until it hits one within range. It does this
by (details abridged)
const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
const size_t _Dt = numeric_limits<_UIntType>::digits;
size_t __w = _Dt - __clz(_Rp) - 1;
if ((_Rp & (_UIntType(~0) >> (_Dt - __w))) != 0)
++__w;
Suppose _UIntType = uint64_t, a = 0, and b = 2^32. Suppose further that we are
working in a one's complement architecture (unlikely, I know). Then, if
negative zero is accepted as a non-trapped representation, uint64_t(~0) =
uint64_t(-0) = 0, and the number of bits will be one less than intended. In
particular, the value 2^32 will never be selected.
The fix to this is simple and painless: replace _UIntType(~0) by _UIntType(-1),
which is guaranteed to always convert correctly, even outside two's complement.
Or even better, std::numeric_limits<_UIntType>::max().
--
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
LLVMbugs mailing list
LLVMbugs@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmbugs
