m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Gray Code
(algo/enumeration/gray_code.hpp)

Overview

This header converts between nonnegative binary integers and binary-reflected Gray codes. Consecutive values in Gray-code order differ in exactly one bit, which is useful for subset enumeration when an update can be applied one bit at a time.

Functions

template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
constexpr UInt gray_encode(UInt value) noexcept;

template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
constexpr UInt gray_decode(UInt code) noexcept;

template <std::unsigned_integral UInt = std::uint64_t>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
std::vector<UInt> gray_code_sequence(int bit_count);

UInt may be any standard unsigned integral type except bool. The conversion functions do not mutate their arguments.

Function Description Complexity
gray_encode(value) Returns the binary-reflected Gray code of value. $O(1)$ time and memory.
gray_decode(code) Returns the binary value represented by code. $O(\log W)$ time and $O(1)$ memory.
gray_code_sequence<UInt>(bit_count) Returns all $2^\text{bit_count}$ codes in traversal order. $O(2^\text{bit_count})$ time and memory.

Here $W$ is the number of value bits in UInt. For sequence generation, bit_count must be nonnegative, must fit in UInt, and must be smaller than the number of value bits in std::size_t. The zero-bit sequence contains one value: zero. For every positive valid bit count, the sequence is cyclic: its last and first values also differ in exactly one bit.

Example

#include "algo/enumeration/gray_code.hpp"

#include <cstdint>
#include <iostream>
#include <vector>

int main() {
    std::vector<std::uint64_t> codes =
        m1une::algo::gray_code_sequence(3);
    for (std::uint64_t code : codes) std::cout << code << " ";
    std::cout << "\n"; // 0 1 3 2 6 7 5 4

    std::cout << m1une::algo::gray_decode(std::uint64_t(6)) << "\n"; // 4
}

Required by

Verified with

Code

#ifndef M1UNE_ALGO_ENUMERATION_GRAY_CODE_HPP
#define M1UNE_ALGO_ENUMERATION_GRAY_CODE_HPP 1

#include <cassert>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>

namespace m1une {
namespace algo {

// Converts a binary value to its binary-reflected Gray code.
template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
constexpr UInt gray_encode(UInt value) noexcept {
    return value ^ (value >> 1);
}

// Converts a binary-reflected Gray code to the corresponding binary value.
template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
constexpr UInt gray_decode(UInt code) noexcept {
    for (int shift = 1; shift < std::numeric_limits<UInt>::digits;
         shift <<= 1) {
        code ^= code >> shift;
    }
    return code;
}

// Returns all bit_count-bit binary-reflected Gray codes in traversal order.
template <std::unsigned_integral UInt = std::uint64_t>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
std::vector<UInt> gray_code_sequence(int bit_count) {
    constexpr int uint_digits = std::numeric_limits<UInt>::digits;
    constexpr int size_digits = std::numeric_limits<std::size_t>::digits;
    assert(0 <= bit_count);
    assert(bit_count <= uint_digits);
    assert(bit_count < size_digits);
    if (bit_count < 0 || uint_digits < bit_count || size_digits <= bit_count) {
        return {};
    }

    const std::size_t size = std::size_t(1) << bit_count;
    std::vector<UInt> result(size);
    for (std::size_t index = 0; index < size; ++index) {
        result[index] = gray_encode(static_cast<UInt>(index));
    }
    return result;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_ENUMERATION_GRAY_CODE_HPP
#line 1 "algo/enumeration/gray_code.hpp"



#include <cassert>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>

namespace m1une {
namespace algo {

// Converts a binary value to its binary-reflected Gray code.
template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
constexpr UInt gray_encode(UInt value) noexcept {
    return value ^ (value >> 1);
}

// Converts a binary-reflected Gray code to the corresponding binary value.
template <std::unsigned_integral UInt>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
constexpr UInt gray_decode(UInt code) noexcept {
    for (int shift = 1; shift < std::numeric_limits<UInt>::digits;
         shift <<= 1) {
        code ^= code >> shift;
    }
    return code;
}

// Returns all bit_count-bit binary-reflected Gray codes in traversal order.
template <std::unsigned_integral UInt = std::uint64_t>
requires(!std::same_as<std::remove_cv_t<UInt>, bool>)
std::vector<UInt> gray_code_sequence(int bit_count) {
    constexpr int uint_digits = std::numeric_limits<UInt>::digits;
    constexpr int size_digits = std::numeric_limits<std::size_t>::digits;
    assert(0 <= bit_count);
    assert(bit_count <= uint_digits);
    assert(bit_count < size_digits);
    if (bit_count < 0 || uint_digits < bit_count || size_digits <= bit_count) {
        return {};
    }

    const std::size_t size = std::size_t(1) << bit_count;
    std::vector<UInt> result(size);
    for (std::size_t index = 0; index < size; ++index) {
        result[index] = gray_encode(static_cast<UInt>(index));
    }
    return result;
}

}  // namespace algo
}  // namespace m1une
Back to top page