Changeset View
Changeset View
Standalone View
Standalone View
source/lib/bits.h
/* Copyright (C) 2010 Wildfire Games. | /* Copyright (C) 2022 Wildfire Games. | ||||
* | * | ||||
* Permission is hereby granted, free of charge, to any person obtaining | * Permission is hereby granted, free of charge, to any person obtaining | ||||
* a copy of this software and associated documentation files (the | * a copy of this software and associated documentation files (the | ||||
* "Software"), to deal in the Software without restriction, including | * "Software"), to deal in the Software without restriction, including | ||||
* without limitation the rights to use, copy, modify, merge, publish, | * without limitation the rights to use, copy, modify, merge, publish, | ||||
* distribute, sublicense, and/or sell copies of the Software, and to | * distribute, sublicense, and/or sell copies of the Software, and to | ||||
* permit persons to whom the Software is furnished to do so, subject to | * permit persons to whom the Software is furnished to do so, subject to | ||||
* the following conditions: | * the following conditions: | ||||
▲ Show 20 Lines • Show All 132 Lines • ▼ Show 20 Lines | |||||
* @return number of 1-bits in mask. | * @return number of 1-bits in mask. | ||||
* execution time is logarithmic in the total number of bits. | * execution time is logarithmic in the total number of bits. | ||||
* supports up to 128-bit integers (if their arithmetic operators are defined). | * supports up to 128-bit integers (if their arithmetic operators are defined). | ||||
* [http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel] | * [http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel] | ||||
**/ | **/ | ||||
template<typename T> | template<typename T> | ||||
static inline size_t PopulationCount(T x) | static inline size_t PopulationCount(T x) | ||||
{ | { | ||||
cassert(!std::numeric_limits<T>::is_signed); | static_assert(!std::numeric_limits<T>::is_signed); | ||||
const T mask = T(~T(0)); | const T mask = T(~T(0)); | ||||
x -= (x >> 1) & (mask/3); // count 2 bits | x -= (x >> 1) & (mask/3); // count 2 bits | ||||
x = (x & (mask/15*3)) + ((x >> 2) & (mask/15*3)); // count 4 bits | x = (x & (mask/15*3)) + ((x >> 2) & (mask/15*3)); // count 4 bits | ||||
x = (x + (x >> 4)) & (mask/255*15); // count 8 bits | x = (x + (x >> 4)) & (mask/255*15); // count 8 bits | ||||
return T(x * (mask/255)) >> ((sizeof(T)-1)*CHAR_BIT); | return T(x * (mask/255)) >> ((sizeof(T)-1)*CHAR_BIT); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 144 Lines • Show Last 20 Lines |
Wildfire Games · Phabricator