Tại sao uniform_int_distribution <uintmax_t> hoạt động với số 62 bit nhưng không hoạt động với 63 bit hoặc 64 bit?

Question

Tôi gặp khó khăn khi hiểu tại sao mã này, nỗ lực sử dụng tiêu đề <random> mới trong C++ 11, tạo đúng số ngẫu nhiên trong [0, 2**62 - 1] nhưng không phải là [0, 2**63 - 1] hoặc [0, 2**64 - 1].

#include <iostream> 
#include <stdint.h> 
#include <random> 
#include <functional> 
#include <ctime> 

static std::mt19937 engine; // Mersenne twister MT19937 

void print_n_random_bits (unsigned int n); 

int main (void) { 
    engine.seed(time(0)); 
    print_n_random_bits(64); 
    print_n_random_bits(63); 
    print_n_random_bits(62); 
    return 0; 
} 

void print_n_random_bits (unsigned int n) 
{ 
    uintmax_t max; 

    if (n == 8 * sizeof(uintmax_t)) { 
    max = 0; 
    } else { 
    max = 1; 
    max <<= n; 
    } 
    --max; 

    std::uniform_int_distribution<uintmax_t> distribution(0, max); 

    std::cout << n << " bits, max: " << max << std::endl; 
    std::cout << distribution(engine) << std::endl; 
} 

Bây giờ, đào sâu thêm một chút tiết lộ std::mt19937_64, trong đó có hành vi đúng, nhưng ai cũng có thể giải thích cho tôi lý do tại sao một cái gì đó mà làm việc cho một số 62 bit không làm việc cho một 64 bit?

Chỉnh sửa: Rất tiếc, tôi thậm chí không chỉ định sự cố. Vấn đề là cho 63 và 64 giá trị max bit, đầu ra là một cách nhất quán một số trong khoảng [0, 2**32 - 1], ví dụ:

% ./rand      
64 bits, max: 18446744073709551615 
1803260654 
63 bits, max: 9223372036854775807 
3178301365 
62 bits, max: 4611686018427387903 
2943926730538475327 

% ./rand         
64 bits, max: 18446744073709551615 
1525658116 
63 bits, max: 9223372036854775807 
2093351390 
62 bits, max: 4611686018427387903 
1513326512211312260 

% ./rand              
64 bits, max: 18446744073709551615 
884934896 
63 bits, max: 9223372036854775807 
683284805 
62 bits, max: 4611686018427387903 
2333288494897435595  

Chỉnh sửa 2: Tôi đang sử dụng clang++ (Apple clang version 2.1 (tags/Apple/clang-163.7.1)) và "libC++ ". Tôi không thể dễ dàng kiểm tra ở trên với GCC vì phiên bản của tôi không có hỗ trợ c++0x.

Answer 1

Bạn đã tìm thấy lỗi trong libC++. Cảm ơn!!!

tôi đã cam kết sửa chữa sau đấm-of-cốp sửa đổi 143.104:

Index: include/algorithm 
=================================================================== 
--- include/algorithm (revision 143102) 
+++ include/algorithm (working copy) 
@@ -2548,7 +2548,7 @@ 
     { 
      __u = __e_() - _Engine::min(); 
     } while (__u >= __y0_); 
-  if (__w0_ < _EDt) 
+  if (__w0_ < _WDt) 
      _S <<= __w0_; 
     else 
      _S = 0; 
@@ -2561,7 +2561,7 @@ 
     { 
      __u = __e_() - _Engine::min(); 
     } while (__u >= __y1_); 
-  if (__w0_ < _EDt - 1) 
+  if (__w0_ < _WDt - 1) 
      _S <<= __w0_ + 1; 
     else 
      _S = 0; 

sửa chữa này không đòi hỏi một biên dịch lại của libc nhị phân ++ dylib..

Answer 2

Kể từ khi std::mt19937 là phiên bản 32 bit, rất có thể điều đang xảy ra là nó đưa ra giả định về bit nào và không quan trọng trong "không gian làm việc" khi tạo số tiếp theo. Điều này sau đó dẫn đến tràn khi tạo ra các số có thể bao gồm hai bit cuối cùng. Tôi nghi ngờ rằng bạn sẽ thấy phân phối thực sự không thực sự đồng nhất với số tối đa cao hơn 2**32 - 1 trên công cụ 32 bit.