### CodingKnight's blog

By CodingKnight, 6 months ago,

Hello Codeforces Community,

In case that some members have not checked yet the new bitwise function templates in C++20 STL bit header, the following are the most relevant to competitive programming.

1. constexpr bool has_single_bit(T x): finds if $x$ is a positive integer $2^p$, for some integer $p \geq 0$.
2. constexpr T bit_ceil(T x): finds the smallest integer $2^p \geq x$ for some integer $p \geq 0$.
3. constexpr T bit_floor(T x): finds the largest integer $2^p \leq x$ for some integer $p \geq 0$.
4. constexpr T bit_width(T x): finds the smallest number of bits needed to represent $x$.
5. constexpr T rotl(T x, int s): finds the result of bitwise cyclic left-rotation of $x$ by $s$ positions.
6. constexpr T rotr(T x, int s): finds the result of bitwise cyclic right-rotation of $x$ by $s$ positions.
7. constexpr int countl_zero(T x): finds the number of consecutive 0 bits in $x$, starting from the most significant bit.
8. constexpr int countl_one(T x): finds the number of consecutive 1 bits in $x$, starting from the most significant bit.
9. constexpr int countr_zero(T x): finds the number of consecutive 0 bits in $x$, starting from the least significant bit.
10. constexpr int countr_one(T x): finds the number of consecutive 1 bits in $x$, starting from the least significant bit.
11. constexpr int popcount(T x): finds the number of 1 bits in $x$.

All function declarations are preceded by template<class T>, where T has to be bound at compile-time to unsigned-integer data-type with 8, 16, 32, or 64-bit width. Note that calling any of these functions with signed-integer data-type argument $x$ produces a compilation error, as it violates the unsigned-integer data-type requirement.

The following is an example program to test the operation of these functions.

Example

The following is the test program output for x = 11 and s = 1.

Output

More details can be found in the C++20 bit header documentation.

Finally, it should be noted that the only difference between interpreting a $w$-bit word $X_w = [x_{w-1},\ldots,x_1,x_0]$, where $x_i \in \{0,1\}$, as an unsigned-integer or as signed-integer is the multiplication factor of the most signification bit $x_{w-1}$, called the sign-bit when $X_w$ is interpreted as a signed integer, as it can be proved that $X_w < 0$ when $x_{w-1} = 1$ for any positive word-length $w \geq 1$.

In particular, the value of $X_w$ as an unsigned-integer can be expressed as:

$X_w = x_{w-1} 2^{w-1} + \sum\limits_{i = 0}^{w-2} x_i 2^i$

On the other hand, the value of $X_w$ as a signed-integer can be expressed as:

$X_w = -x_{w-1} 2^{w-1} + \sum\limits_{i = 0}^{w-2} x_i 2^i$

Therefore, $X_w \geq 0$ when $x_{w-1} = 0$, and the value of signed-integer $X_w$ in this case is equal to the value of the unsigned-integer $X_{w-1} = [x_{w-2},\ldots,x_1,x_0]$.

• +34

 » 6 months ago, # |   +35 One thing to keep in mind is that even though these are now C++ standard functions, their performance still depends on the compilation flags. For example, on Codeforces, this code runs in around 620ms with the pragma and around 2070ms without it. Code (C++20)#pragma GCC target("popcnt") #include using ull = unsigned long long; int main() { ull z = 0; for (ull i=0; i<(1<<30); i++) z += std::popcount(i); std::cout << z << '\n'; } 
•  » » 6 months ago, # ^ | ← Rev. 3 →   +11 Thanks for sharing this point. I checked the performance of your code on C++17 using the non-standard function __builtin_popcountll(), and found that the presence of the compilation flag popcnt improved the execution-time as well. Code (C++17)#pragma GCC target("popcnt") #include using namespace std; int main() { uint64_t z = 0; for (uint64_t n = 1ull<<30, i = 0; i < n; ++i) z += __builtin_popcountll(i); cout << z << '\n'; }