# C++ Bit Manipulation Reference

This document contains:
- GCC / Clang built-in bit functions
- C++20 `<bit>` header utilities
- C++23 additions

---

# Part 1 — GCC / Clang Built-in Bit Functions

These are compiler-specific (GCC / Clang).
They are fast (usually O(1)) and often map to CPU instructions.

---

## 1. `__builtin_popcount`

Counts number of set bits (1s).

### Variants

```cpp
__builtin_popcount(x)     // → int
__builtin_popcountl(x)    // → long
__builtin_popcountll(x)   // → long long
```

### Example

```cpp
int x = 13; // 1101
int cnt = __builtin_popcount(x); // 3
```

---

## 2. `__builtin_clz`

Count Leading Zeros (from MSB).

### Variants

```cpp
__builtin_clz(x)
__builtin_clzl(x)
__builtin_clzll(x)
```

### Example

```cpp
int x = 8; // 000...1000
int zeros = __builtin_clz(x); // 28 (32-bit int)
```

### Notes

> ⚠️ Undefined if `x == 0`

```cpp
// Highest set bit index:
int highest = 31 - __builtin_clz(x);
```

---

## 3. `__builtin_ctz`

Count Trailing Zeros (from LSB).

### Variants

```cpp
__builtin_ctz(x)
__builtin_ctzl(x)
__builtin_ctzll(x)
```

### Example

```cpp
int x = 8; // 1000
int zeros = __builtin_ctz(x); // 3
```

> ⚠️ Undefined if `x == 0`

---

## 4. `__builtin_parity`

Returns `1` if odd number of set bits, `0` if even.

```cpp
int x = 7; // 111
int p = __builtin_parity(x); // 1
```

---

## 5. `__builtin_ffs`

Find First Set Bit (1-indexed from right). Returns `0` if input is `0`.

```cpp
int x = 10; // 1010
int pos = __builtin_ffs(x); // 2
```

---

# Part 2 — C++20 `<bit>` Header (Portable Standard)

```cpp
#include <bit>
```

> Works on **unsigned integer types** only.

---

## 1. `std::popcount`

Counts number of set bits.

```cpp
std::popcount(x);
```

---

## 2. `std::countl_zero`

Count leading zeros. Safe for `x == 0` (returns bit width).

```cpp
std::countl_zero(x);
```

---

## 3. `std::countl_one`

Count consecutive leading ones.

```cpp
std::countl_one(x);
```

---

## 4. `std::countr_zero`

Count trailing zeros. Safe for `x == 0` (returns bit width).

```cpp
std::countr_zero(x);
```

---

## 5. `std::countr_one`

Count consecutive trailing ones.

```cpp
std::countr_one(x);
```

---

## 6. `std::has_single_bit`

Returns `true` if exactly one bit is set (i.e., power of 2).

```cpp
std::has_single_bit(x);

// Equivalent to:
x > 0 && (x & (x - 1)) == 0;
```

---

## 7. `std::bit_width`

Number of bits required to represent `x`.

```cpp
std::bit_width(x);

// Equivalent to (for x > 0):
floor(log2(x)) + 1;
```

---

## 8. `std::bit_floor`

Largest power of 2 ≤ `x`.

```cpp
std::bit_floor(x);

// Example:
std::bit_floor(10); // → 8
```

---

## 9. `std::bit_ceil`

Smallest power of 2 ≥ `x`.

```cpp
std::bit_ceil(x);

// Example:
std::bit_ceil(10); // → 16
```

---

## 10. `std::rotl` — Rotate Left

Circular left rotation.

```cpp
std::rotl(x, s);
```

---

## 11. `std::rotr` — Rotate Right

Circular right rotation.

```cpp
std::rotr(x, s);
```

---

# Part 3 — C++23 Additions

---

## 1. `std::byteswap`

Swap byte order (endianness conversion).

```cpp
std::byteswap(x);

// Example:
// 0x12345678 → 0x78563412
```

---

## 2. `std::endian`

Detect system byte order.

```cpp
#include <bit>

if (std::endian::native == std::endian::little) {
    // little-endian system
}
```
# Applications
A number of the form 1 << k has a one bit in position k and all other bits are zero,
so we can use such numbers to access single bits of numbers. In particular, the
kth bit of a number is one exactly when x & (1 << k) is not zero. The following
code prints the bit representation of an int number x:
```
for (int i = 31; i >= 0; i--) {
if (x&(1<<i)) cout << "1";
else cout << "0";
}
```
It is also possible to modify single bits of numbers using similar ideas. For
example, the formula x | (1 << k) sets the kth bit of x to one, the formula x &
~(1 << k) sets the kth bit of x to zero, and the formula x ^ (1 << k) inverts the
kth bit of x.
The formula x & (x − 1) sets the last one bit of x to zero, and the formula x &
−x sets all the one bits to zero, except for the last one bit. The formula x | (x − 1)
inverts all the bits after the last one bit. Also note that a positive number x is a
power of two exactly when x & (x − 1) = 0.