pasta_bit_vector  1.0.1
Bit Vector with Compact and Fast Rank and Select Support
All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
popcount.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * This file is part of pasta::bit_vector.
3 *
4 * Copyright (C) 2021 Florian Kurpicz <florian@kurpicz.org>
5 *
6 * pasta::bit_vector is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * pasta::bit_vector is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with pasta::bit_vector. If not, see <http://www.gnu.org/licenses/>.
18 *
19 ******************************************************************************/
20
21#pragma once
22
23#include <bit>
24#include <cstdint>
25#include <iostream>
26
27namespace pasta {
28
29/*! \file */
30
31/*!
32 * \brief Compute popcount of a specific number of 64-bit words.
33 *
34 * Note that there are no bound checks.
35 *
36 * \tparam Words Number of 64-bit words the popcount is computed for.
37 * \param buffer Pointer to the beginning of the 64-bit words.
38 * \return Popcount of the \c Words * 64 bits starting at \c buffer.
39 */
40template <size_t Words>
41[[nodiscard]] uint64_t popcount(uint64_t const* const buffer) {
42 uint64_t popcount = 0;
43 for (size_t i = 0; i < Words; ++i) {
44 popcount += std::popcount(buffer[i]);
45 }
46 return popcount;
47}
48
49/*!
50 * \brief Counts the number of zero bits in a specific number of 64-bit words.
51 *
52 * Note that there are no bound checks.
53 *
54 * \tparam Words Number of 64-bit words the zeros are counted in.
55 * \param buffer Pointer to the beginning of the 64-bit words.
56 * \return Number of zeros in the \c Words * 64 bits starting at \c buffer.
57 */
58template <size_t Words>
59[[nodiscard]] uint64_t popcount_zeros(uint64_t const* const buffer) {
60 uint64_t popcount = 0;
61 for (size_t i = 0; i < Words; ++i) {
62 popcount += std::popcount(~buffer[i]);
63 }
64 return popcount;
65}
66
67} // namespace pasta
68
69/******************************************************************************/
uint64_t popcount_zeros(uint64_t const *const buffer)
Counts the number of zero bits in a specific number of 64-bit words.
Definition popcount.hpp:59
uint64_t popcount(uint64_t const *const buffer)
Compute popcount of a specific number of 64-bit words.
Definition popcount.hpp:41