CodingKnight's blog

By CodingKnight, 3 years ago, In English

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

  • Vote: I like it
  • +34
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

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)
  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    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)