data_structure/bitVector.hpp

• View this file on GitHub
• Last update: 2023-12-28 15:52:36+09:00
• Include: #include "data_structure/bitVector.hpp"
• Link: https://misteer.hatenablog.com/entry/bit-vector

Depends on

• template/int_alias.hpp

Required by

• Wavelet Matrix (data_structure/WaveletMatrix.hpp)

Verified with

• test/data_structure/Range_Kth_Smallest.test.cpp
• test/data_structure/Static_Range_Frequency.test.cpp

Code

#pragma once

#include "../template/int_alias.hpp"


/*
    reference: https://misteer.hatenablog.com/entry/bit-vector
*/

#include <vector>


namespace ebi {

struct bitVector {
    u32 length, cn, bn;
    static u32 cw,
        bw;  // chunk, block の長さ cw = (lg N)^2, bw = (lg N)/2 とする.

    std::vector<u16> bit;
    std::vector<u32> chunk;
    std::vector<std::vector<u16>> blocks;

    bitVector(int n) : length(n) {
        cn = (length + cw - 1) / cw;
        bn = cw / bw;
        bit.assign(cn * bn, 0);
        chunk.assign(cn + 1, 0);
        blocks.assign(cn, std::vector<u16>(bn, 0));
    }

    void set(int k, int b) {
        u32 i = k / bw;
        u32 j = k % bw;
        if (b == 0) {
            bit[i] &= ~(1 << j);
        } else if (b == 1) {
            bit[i] |= (1 << j);
        }
    }

    int access(int k) {
        u32 i = k / bw;
        u32 j = k % bw;
        return bit[i] >> j & 1;
    }

    void build() {
        chunk[0] = 0;
        for (u32 i = 0; i < cn; i++) {
            blocks[i][0] = 0;
            for (u32 j = 0; j < bn - 1; j++) {
                blocks[i][j + 1] =
                    blocks[i][j] + __builtin_popcount(bit[i * bn + j]);
            }
            chunk[i + 1] = chunk[i] + blocks[i][bn - 1] +
                           __builtin_popcount(bit[(i + 1) * bn - 1]);
        }
    }

    // [0, r)に存在する1の数をO(1)で計算する.

    int rank(int r) {
        u32 i = r / cw;
        u32 j = (r % cw) / bw;
        u32 k = r % bw;
        u32 leftover = bit[i * bn + j] & ((1 << k) - 1);
        if (i == cn) return chunk[i];
        return chunk[i] + blocks[i][j] + __builtin_popcount(leftover);
    }

    int select(int k) {
        if (k == 0) return 0;
        if (rank(length) < k) return -1;
        u32 l = 0;
        u32 r = length;
        while (r - l > 1) {
            u32 mid = (r + l) / 2;
            if (rank(mid) >= k) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }

    int select0(int k) {
        if (k == 0) return 0;
        if (length - rank(length) < (u32)k) return -1;
        u32 l = 0;
        u32 r = length;
        while (r - l > 1) {
            u32 mid = (r + l) / 2;
            if (mid - rank(mid) >= (u32)k) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
};

u32 bitVector::cw = 1024;
u32 bitVector::bw = 16;

}  // namespace ebi

#line 2 "data_structure/bitVector.hpp"

#line 2 "template/int_alias.hpp"

#include <cstdint>

namespace ebi {

using ld = long double;
using std::size_t;
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using u16 = std::uint16_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

}  // namespace ebi
#line 4 "data_structure/bitVector.hpp"

/*
    reference: https://misteer.hatenablog.com/entry/bit-vector
*/

#include <vector>


namespace ebi {

struct bitVector {
    u32 length, cn, bn;
    static u32 cw,
        bw;  // chunk, block の長さ cw = (lg N)^2, bw = (lg N)/2 とする.

    std::vector<u16> bit;
    std::vector<u32> chunk;
    std::vector<std::vector<u16>> blocks;

    bitVector(int n) : length(n) {
        cn = (length + cw - 1) / cw;
        bn = cw / bw;
        bit.assign(cn * bn, 0);
        chunk.assign(cn + 1, 0);
        blocks.assign(cn, std::vector<u16>(bn, 0));
    }

    void set(int k, int b) {
        u32 i = k / bw;
        u32 j = k % bw;
        if (b == 0) {
            bit[i] &= ~(1 << j);
        } else if (b == 1) {
            bit[i] |= (1 << j);
        }
    }

    int access(int k) {
        u32 i = k / bw;
        u32 j = k % bw;
        return bit[i] >> j & 1;
    }

    void build() {
        chunk[0] = 0;
        for (u32 i = 0; i < cn; i++) {
            blocks[i][0] = 0;
            for (u32 j = 0; j < bn - 1; j++) {
                blocks[i][j + 1] =
                    blocks[i][j] + __builtin_popcount(bit[i * bn + j]);
            }
            chunk[i + 1] = chunk[i] + blocks[i][bn - 1] +
                           __builtin_popcount(bit[(i + 1) * bn - 1]);
        }
    }

    // [0, r)に存在する1の数をO(1)で計算する.

    int rank(int r) {
        u32 i = r / cw;
        u32 j = (r % cw) / bw;
        u32 k = r % bw;
        u32 leftover = bit[i * bn + j] & ((1 << k) - 1);
        if (i == cn) return chunk[i];
        return chunk[i] + blocks[i][j] + __builtin_popcount(leftover);
    }

    int select(int k) {
        if (k == 0) return 0;
        if (rank(length) < k) return -1;
        u32 l = 0;
        u32 r = length;
        while (r - l > 1) {
            u32 mid = (r + l) / 2;
            if (rank(mid) >= k) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }

    int select0(int k) {
        if (k == 0) return 0;
        if (length - rank(length) < (u32)k) return -1;
        u32 l = 0;
        u32 r = length;
        while (r - l > 1) {
            u32 mid = (r + l) / 2;
            if (mid - rank(mid) >= (u32)k) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
};

u32 bitVector::cw = 1024;
u32 bitVector::bw = 16;

}  // namespace ebi

Back to top page