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.

#include <bits/stdc++.h>
#define apply1(f,x)   cout << #f << "(x) = " << uint64_t(f(x)) << endl
#define apply2(f,x,s) cout << #f << "(x,s) = " << uint64_t(f(x,s)) << endl
using namespace std;

template<class T>
inline void test_bit(T x, int s) {
    cout << "test_bit: x = " << bitset<sizeof(T)<<3>(x) << ", s = " << s << endl << endl;
    apply1(has_single_bit<T>,x),
    apply1(bit_ceil<T>,x),
    apply1(bit_floor<T>,x),
    apply1(bit_width<T>,x),
    apply2(rotl<T>,x,s),
    apply2(rotr<T>,x,s),
    apply1(countl_zero<T>,x),
    apply1(countl_one<T>,x),
    apply1(countr_zero<T>,x),
    apply1(countr_one<T>,x),
    apply1(popcount<T>,x); }

int main() {
    uint16_t x; int s;
    cin >> x >> s, test_bit(x,s); 
    return 0; }

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

test_bit: x = 0000000000001011, s = 1

has_single_bit<T>(x) = 0
bit_ceil<T>(x) = 16
bit_floor<T>(x) = 8
bit_width<T>(x) = 4
rotl<T>(x,s) = 22
rotr<T>(x,s) = 32773
countl_zero<T>(x) = 12
countl_one<T>(x) = 0
countr_zero<T>(x) = 0
countr_one<T>(x) = 2
popcount<T>(x) = 3

=====
Used: 0 ms, 1188 KB

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]$$$.