Get this book -> Problems on Array: For Interviews and Competitive Programming

The `<bit>`

header was included in C++20.

# Introduction

The `<bit>`

header was included in the C++20. This header provides components such as types and functions to access, manipulate and process individual bits and bit sequences. It is included in the `<numeric>`

library.

### Binary representation

Binary representation uses `0`

's and `1`

's to represent values. For example an integer 52 is represented as `110100`

.

knowing the binary representation can be very useful. Certain properties of binary representation have many applications in programming. For example, A integral power of 2 always has a single `1`

in its representation, left-shifting the representation gives the effect of multiplying by 2 and similarly right-shifting will divide by 2.

Left shifting a `1`

bit thus allows multiplication by 2.

1 << 0 = 0b1 = 1 = 2^{0}

1 << 1 = 0b10 = 2 = 2^{1}

1 << 2 = 0b100 = 4 = 2^{2}

...

1 << k = 0b100... = 2^{k}

Thus we can see that a power of 2 always has a single `1`

bit in its representation.

For numbers the usual representation has a most significant bit (MSB) on the left hand side and the least significant bit (LSB) on the right hand side.

for example: 10 is represented in binary as `1010`

(`0b1010`

), here the leftmost `1`

bit is the MSB and the rightmost `0`

bit is the LSB.

### Byte ordering

A byte is made up of 8 bits. When more than one byte of memory is to be stored in memory, there are two orderings possible: big endian, where most significant byte is stored first, and the little endian, where least significant byte is stored first.

# Types

The header has one type: `endian`

, which defines the endianness or the byte ordering. A value of `std::endian::little`

means little-endian is used, `std::endian::big`

means big-endian is used. The value of `std::endian::native`

is used to find the endianness of the current implementation. All of these are implementation defined.

In C++, `endian`

is defined as an enum

```
if constexpr (endian::native == endian::big) {
cout << "big-endian" << endl;
}
else if constexpr (endian::native == endian::little) {
cout << "little-endian" << endl;
}
else {
cout << "mixed-endian" << endl;
}
```

# Functions

## std::bit_cast

This function allows us to reinterpret an object of one type as another. This is useful when we need to convert the underlying representation of an object.

```
double f64v = 19880124.0;
auto u64v = bit_cast<std::uint64_t>(f64v);
cout << fixed << f64v << "f64 == 0x" << hex << u64v << "u64" << endl;
// 19880124.000000f64 == 0x4172f58bc0000000u64
```

## std::has_single_bit

This function checks if the value has a single `1`

bit in its binary representation. Having a single bit implies that the value is a power of two. Thus this function returns true if the value is an integral power of two.

Consider the following example where we check if the value has a single `1`

bit

```
cout << boolalpha;
uint8_t a = 0b00001101;
uint8_t b = 0b00000010;
cout << has_single_bit(a) << endl; // false
cout << has_single_bit(b) << endl; // true
```

## std::bit_ceil, std::bit_floor

The `std::bit_ceil`

function finds the binary ceiling of a value. It finds a power of two that is not smaller than the value.

The `std::bit_floor`

function finds the binary floor of a value. It finds a power of two that is not larger than the value.

Example:

```
uint8_t a = 0b00000011; // 3
cout << (unsigned)(bit_ceil(a)) << endl; // 4
cout << (unsigned)(bit_floor(a)) << endl; // 2
```

## std::bit_width

The number of bits in an integer is given by the formula `1+floor(log2(x))`

. This function allows us to find this value. This value is the length of `x`

in binary when there are no preceding `0`

's. For example the value of 3 (0b00000011) would require 2 bits. For the input value 0, the function returns 0.

example:

```
unsigned int a = 55; // 110111
cout << bit_width(a) << endl; // 6
```

## std::rotl, std::rotr

`std::rotl`

performs a bitwise left rotation and returns the result, while the `std::rotr`

performs a bitwise right rotation. Each of these functions take the value and a number that indicates the number of positions to rotate.

example:

```
std::uint8_t a = 0b00011101;
cout << bitset<8>( rotl(a, 2) ) << endl; // 0b01110100
cout << bitset<8>( rotr(a, 3) ) << endl; // 0b10100011
```

## Counting consecutive bits

These functions count the number of consecutive bits starting from the LSB or MSB position. The input needs to be an unsigned number.

### Count starting from MSB

`std::countl_zero`

counts the number of consecutive `0`

bits, starting from the most significant bit and `std::countl_one`

counts the number of consecutive `1`

bits, starting from the most significant bit.

### Count starting from LSB

`std::countr_zero`

counts the number of consecutive `0`

bits, starting from the least significant bit and `std::countr_one`

counts the number of consecutive `1`

bits, starting from the least significant bit.

Consider the example:

```
uint8_t x = 0b00101111;
uint8_t y = 0b11010110;
cout << countl_zero(x) << endl; // 2
cout << countl_one(x) << endl; // 0
cout << countr_zero(y) << endl; // 1
cout << countr_one(y) << endl; // 0
```

## std::popcount

This function counts the number of `1`

bits in an unsigned integer.

for example:

```
uint8_t i = 0b01011101;
cout << popcount(i) << endl; // 5
```

# Conclusion

The `<bit>`

header, included in the C++20, provides components to access, manipulate and process individual bits and bit sequences. std::endian allows us to determine the endianness of the implementation. The header also include many other functions that allow us to reinterpret an object, check if a number is a power of two, count bits, etc.