Random
(random/base.hpp)

• View this file on GitHub
• Last update: 2026-01-26 01:12:37+09:00
• Include: #include "random/base.hpp"
• Link: http://xorshift.di.unimi.it/splitmix64.c

乱数生成用のライブラリです。 random/ 以下の他のライブラリなどで利用できるように RandomAuto rng_auto が定義されています。 また、固定シードと実行時シードを切り替えることができます。

コンストラクタ

(1) RandomFixed rng(uint64_t seed = 0)
(2) RandomAuto rng()

(1)

乱数のシード値は seed で初期化されます。

(2)

乱数のシード値は実行時刻をもとに初期化されます。

rand_int

(1) uint64_t rng.rand_int()
(2) uint64_t rng.rand_int(uint64_t mod)
(3) template <class T> T rng.rand_int(T l, T r)

(1)

$[0, 2^{64} - 1]$ の一様乱数（整数）を返します。

(2)

$[0, \bmod - 1]$ の一様乱数（整数）を返します。

(3)

$[l, r]$ の一様乱数（整数）を返します。

制約

(2)

• $\bmod > 0$

(3)

• $l \leq r$
• $r - l + 1$ が型 T でオーバーフローしない

rand_double

double rng.rand_double()
double rng.rand_double(double l, double r)

(1)

$[0.0, 1.0]$ の一様乱数（浮動小数点数）を返します。

(2)

$[l, r]$ の一様乱数（浮動小数点数）を返します。

制約

(2)

• $l \leq r$

Depends on

• Countl Zero (misc/countl_zero.hpp)
• Topbit (misc/topbit.hpp)

Verified with

• dp/test/inversion_number.test.cpp
• random/test/base.test.cpp

Code

#pragma once

#include <cassert>
#include <chrono>
#include <cstdint>

#include "../misc/topbit.hpp"

template <bool auto_seed> struct Random {
    uint64_t x_seed;

    Random(uint64_t seed = 0) {
        if (auto_seed) {
            // set random seed
            assert(seed == 0);
            x_seed =
                std::chrono::steady_clock::now().time_since_epoch().count();
        } else {
            // set seed
            x_seed = seed;
        }
    }

    // http://xorshift.di.unimi.it/splitmix64.c
    // [0, 2^64 - 1]
    uint64_t rand_int() {
        uint64_t z = (x_seed += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }

    // [0, mod - 1]
    // rand_int() % mod だと mod が 2 べきでないときに偏る
    uint64_t rand_int(uint64_t mod) {
        assert(mod > 0);
        if ((mod & (mod - 1)) == 0) {
            // mod = 2^p
            // (mod - 1) = 0...01...1
            return rand_int() & (mod - 1);
        }
        // mod >= 3 (1 = 2^0, 2 = 2^1)
        int lg = topbit((unsigned long long)mod);
        uint64_t mask = (lg == 63) ? ~0ULL : (1ULL << (lg + 1)) - 1;
        while (true) {
            uint64_t r = rand_int() & mask;
            if (r < mod) return r;
        }
    }

    // [l, r]
    template <class T> T rand_int(T l, T r) {
        assert(l <= r);
        return T(l + rand_int(uint64_t(r - l + 1)));
    }

    // [0.0, 1.0]
    double rand_double() {
        uint64_t v = rand_int(1ULL << 63);
        return double(v) / ((1ULL << 63) - 1);
    }

    // [l, r]
    double rand_double(double l, double r) {
        assert(l <= r);
        return l + rand_double() * (r - l);
    }
};

using RandomFixed = Random<false>;
using RandomAuto = Random<true>;

RandomAuto rng_auto;

#line 2 "random/base.hpp"

#include <cassert>
#include <chrono>
#include <cstdint>

#line 2 "misc/topbit.hpp"

#line 2 "misc/countl_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countl_zero
// (000, 001, 010, 011, 100) -> (32, 31, 30, 30, 29)
#if __cplusplus >= 202002L
using std::countl_zero;
#else
int countl_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_clz(x);
}
int countl_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_clzll(x);
}
#endif
int countl_zero(int x) { return countl_zero((unsigned int)(x)); }
int countl_zero(long long int x) {
    return countl_zero((unsigned long long int)(x));
}
#line 4 "misc/topbit.hpp"

// topbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - countl_zero(x); }
int topbit(unsigned int x) { return 31 - countl_zero(x); }
int topbit(long long int x) { return 63 - countl_zero(x); }
int topbit(unsigned long long int x) { return 63 - countl_zero(x); }
#line 8 "random/base.hpp"

template <bool auto_seed> struct Random {
    uint64_t x_seed;

    Random(uint64_t seed = 0) {
        if (auto_seed) {
            // set random seed
            assert(seed == 0);
            x_seed =
                std::chrono::steady_clock::now().time_since_epoch().count();
        } else {
            // set seed
            x_seed = seed;
        }
    }

    // http://xorshift.di.unimi.it/splitmix64.c
    // [0, 2^64 - 1]
    uint64_t rand_int() {
        uint64_t z = (x_seed += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }

    // [0, mod - 1]
    // rand_int() % mod だと mod が 2 べきでないときに偏る
    uint64_t rand_int(uint64_t mod) {
        assert(mod > 0);
        if ((mod & (mod - 1)) == 0) {
            // mod = 2^p
            // (mod - 1) = 0...01...1
            return rand_int() & (mod - 1);
        }
        // mod >= 3 (1 = 2^0, 2 = 2^1)
        int lg = topbit((unsigned long long)mod);
        uint64_t mask = (lg == 63) ? ~0ULL : (1ULL << (lg + 1)) - 1;
        while (true) {
            uint64_t r = rand_int() & mask;
            if (r < mod) return r;
        }
    }

    // [l, r]
    template <class T> T rand_int(T l, T r) {
        assert(l <= r);
        return T(l + rand_int(uint64_t(r - l + 1)));
    }

    // [0.0, 1.0]
    double rand_double() {
        uint64_t v = rand_int(1ULL << 63);
        return double(v) / ((1ULL << 63) - 1);
    }

    // [l, r]
    double rand_double(double l, double r) {
        assert(l <= r);
        return l + rand_double() * (r - l);
    }
};

using RandomFixed = Random<false>;
using RandomAuto = Random<true>;

RandomAuto rng_auto;

Back to top page