Bit Manipulation

uint32_t a = 0b1100u, b = 0b1010u;  // binary literals: C++14

a & b    // 0b1000  — AND:  bits set in both
a | b    // 0b1110  — OR:   bits set in either
a ^ b    // 0b0110  — XOR:  bits set in exactly one
~a       // bitwise NOT (all bits flipped)

a << 2   // 0b110000 — left shift: multiply by 4
a >> 1   // 0b0110   — right shift (unsigned: logical shift, zero-fill)

// Digit separators (C++14) aid readability:
uint32_t mask = 0b1010'0101'1100'0011u;

// Compound assignment forms (C++98):
a &= b;   a |= b;   a ^= b;   a <<= 2;   a >>= 1;

#include <bit>      // C++20
#include <cstdint>

// ── Population count ──────────────────────────────────────────────────────
// Returns the number of 1-bits in the value.
std::popcount(uint32_t{0b0110'1001u})  // 4
std::popcount(uint16_t{0xFF})          // 8
std::popcount(uint64_t{0})             // 0

// ── Has single bit (exact power of two) ───────────────────────────────────
// True iff exactly one bit is set (equivalent to n != 0 && (n & (n-1)) == 0).
std::has_single_bit(uint32_t{64})   // true  — 0b0100'0000
std::has_single_bit(uint32_t{0})    // false — 0 has no set bits
std::has_single_bit(uint32_t{3})    // false — 0b11 has two set bits

// ── Bit width ─────────────────────────────────────────────────────────────
// Returns 1 + floor(log2(n)) for n > 0; 0 for n == 0.
// Equivalently: minimum number of bits to represent n.
std::bit_width(uint32_t{0})    // 0
std::bit_width(uint32_t{1})    // 1
std::bit_width(uint32_t{7})    // 3   (0b111 needs 3 bits)
std::bit_width(uint32_t{100})  // 7   (2^6=64 < 100 ≤ 2^7=128)
std::bit_width(uint32_t{128})  // 8   (2^7=128, needs 8 bits to fit)

// ── Round to power of two ─────────────────────────────────────────────────
// bit_ceil: smallest power of 2 >= n. UB if result is not representable.
std::bit_ceil(uint32_t{1})   // 1   (already a power of two)
std::bit_ceil(uint32_t{5})   // 8
std::bit_ceil(uint32_t{8})   // 8
std::bit_ceil(uint32_t{9})   // 16

// bit_floor: largest power of 2 <= n. Returns 0 for n == 0.
std::bit_floor(uint32_t{0})  // 0   (special case)
std::bit_floor(uint32_t{1})  // 1
std::bit_floor(uint32_t{9})  // 8
std::bit_floor(uint32_t{8})  // 8

// ── Leading/trailing zero counts ──────────────────────────────────────────
// countl_zero: number of consecutive 0-bits starting from the MSB.
// Returns the full bit-width of the type when the value is 0.
std::countl_zero(uint32_t{1})         // 31  — only bit 0 is set
std::countl_zero(uint32_t{0x80000000u}) // 0   — MSB is set
std::countl_zero(uint32_t{0})         // 32  — all zeros
std::countl_zero(uint8_t{0b00011000}) // 3

// countr_zero: number of consecutive 0-bits starting from the LSB.
std::countr_zero(uint32_t{8})         // 3   (8 = 0b1000; three trailing zeros)
std::countr_zero(uint32_t{1})         // 0
std::countr_zero(uint32_t{0})         // 32

// ── Leading/trailing one counts ───────────────────────────────────────────
// countl_one: consecutive 1-bits from MSB.
std::countl_one(uint8_t{0b11100000u}) // 3
std::countl_one(uint8_t{0xFF})        // 8
std::countl_one(uint8_t{0x7F})        // 0   — MSB is 0

// countr_one: consecutive 1-bits from LSB.
std::countr_one(uint8_t{0b00000111u}) // 3
std::countr_one(uint8_t{0xFF})        // 8
std::countr_one(uint8_t{0xFE})        // 0   — LSB is 0

// ── Rotation ──────────────────────────────────────────────────────────────
// Bits rotate through the type width; no bits are lost.
// Negative shift count reverses direction (rotl(-n) == rotr(n)).
std::rotl(uint8_t{0b00001111u}, 2)  // 0b00111100 — shifted left, wrap to right
std::rotr(uint8_t{0b11110000u}, 2)  // 0b00111100 — shifted right, wrap to left
std::rotl(uint8_t{0b10000001u}, 1)  // 0b00000011 — MSB wraps to bit 0
std::rotl(uint32_t{1u}, 31)         // 0x80000000u

#include <bit>
#include <cstdint>

bool     test_bit(uint32_t x, int n)    { return (x >> n) & 1u; }
uint32_t set_bit(uint32_t x, int n)     { return x | (1u << n); }
uint32_t clear_bit(uint32_t x, int n)   { return x & ~(1u << n); }
uint32_t toggle_bit(uint32_t x, int n)  { return x ^ (1u << n); }

// Contiguous field extraction [hi:lo] inclusive
uint32_t extract_bits(uint32_t x, int lo, int hi) {
    return (x >> lo) & ((1u << (hi - lo + 1)) - 1u);
}

// Isolate / clear the lowest set bit
uint32_t lsb(uint32_t x)        { return x & -x; }      // -x wraps (unsigned arithmetic)
uint32_t clear_lsb(uint32_t x)  { return x & (x - 1u); }

// Integer floor-log2 — portable C++20
int ilog2(uint32_t n) { return static_cast<int>(std::bit_width(n)) - 1; }

#include <bit>
#include <cstdint>

constexpr uint32_t float_bits(float f) noexcept {
    return std::bit_cast<uint32_t>(f);  // C++20
}

constexpr bool float_is_negative(float f) noexcept {
    return (float_bits(f) >> 31u) == 1u;
}

static_assert(float_bits(0.0f)  == 0x00000000u);
static_assert(float_bits(-1.0f) == 0xBF800000u);
static_assert(float_is_negative(-3.14f));

#include <bit>
#include <cstdint>

// Quake's fast inverse square root — safely rewritten with bit_cast (C++20).
// Original used: i = *(uint32_t*)&y;  // UB: violates strict aliasing
float fast_inv_sqrt(float number) noexcept {
    float y = number;
    float x2 = number * 0.5f;

    uint32_t i = std::bit_cast<uint32_t>(y);   // safe: same size, trivially copyable
    i  = 0x5f3759dfu - (i >> 1);               // bit-level Newton's method seed
    y  = std::bit_cast<float>(i);              // convert back
    y  = y * (1.5f - (x2 * y * y));            // one Newton-Raphson iteration
    return y;
}

// std::bit_cast constraints (checked at compile time):
//   sizeof(To) == sizeof(From)   — float and uint32_t are both 4 bytes
//   std::is_trivially_copyable_v<To>   — uint32_t: yes
//   std::is_trivially_copyable_v<From> — float:    yes

#include <bit>      // C++23
#include <cstdint>

static_assert(std::byteswap(uint32_t{0x12345678u}) == 0x78563412u);
static_assert(std::byteswap(uint16_t{0xABCDu})     == 0xCDABu);
static_assert(std::byteswap(uint64_t{0x0102030405060708ULL})
                                                == 0x0807060504030201ULL);
static_assert(std::byteswap(uint8_t{0xFFu})    == 0xFFu);  // no-op for single byte

#include <bit>
#include <cstdint>
#include <cstring>  // memcpy

// Read a big-endian uint32 from a network packet on a little-endian machine.
// Protocol spec says bytes arrive MSB first (big-endian / network byte order).
uint32_t read_be_u32(const uint8_t* buf) noexcept {
    uint32_t raw{};
    std::memcpy(&raw, buf, 4);            // safe byte copy, avoids alignment UB

    if constexpr (std::endian::native == std::endian::little)
        return std::byteswap(raw);        // C++23
    return raw;
}

// Write a host-order value into a big-endian packet field.
void write_be_u32(uint8_t* buf, uint32_t host_val) noexcept {
    uint32_t net_val = host_val;
    if constexpr (std::endian::native == std::endian::little)
        net_val = std::byteswap(net_val); // C++23
    std::memcpy(buf, &net_val, 4);
}

#include <bit>    // C++20

// Compile-time branch — zero runtime overhead.
if constexpr (std::endian::native == std::endian::little) {
    // x86, x86-64, ARM (typical LE configuration), RISC-V LE
} else if constexpr (std::endian::native == std::endian::big) {
    // SPARC, MIPS (BE mode), s390x, network byte order machines
} else {
    // Mixed/unusual endianness — add explicit handling
}

#include <bit>
#include <cstdint>

// C++20-compatible manual swap (no std::byteswap yet):
constexpr uint32_t bswap32(uint32_t n) noexcept {
    return ((n & 0xFF000000u) >> 24u)
         | ((n & 0x00FF0000u) >>  8u)
         | ((n & 0x0000FF00u) <<  8u)
         | ((n & 0x000000FFu) << 24u);
}

// Generic "to big-endian" helper — use std::byteswap on C++23 targets.
constexpr uint32_t to_big_endian(uint32_t host) noexcept {
    if constexpr (std::endian::native == std::endian::big)
        return host;           // already big-endian, nothing to do
    else
        return bswap32(host);  // swap on little-endian (C++20)
        // return std::byteswap(host);  // preferred on C++23
}

constexpr uint32_t from_big_endian(uint32_t net) noexcept {
    return to_big_endian(net);  // same operation: swap is its own inverse
}

#include <bitset>
#include <iostream>
#include <string>

// Construction
std::bitset<8> a;                    // all zeros: 00000000
std::bitset<8> b{0b10110100u};       // from unsigned long
std::bitset<8> c{"10110100"};        // from string (MSB first in string)
std::bitset<8> d{"xyxyyxyy", 8, 'x', 'y'}; // custom zero/one chars

// Element access and modification
std::bitset<8> flags;
flags[3] = true;          // set bit 3 via reference proxy
flags.set(5);             // set bit 5
flags.set(7);             // set bit 7
flags.reset(5);           // clear bit 5
flags.flip(3);            // toggle bit 3 — now 0 again
flags.flip();             // flip all bits

// Queries
std::bitset<8> perms{0b00000101u};   // bits 0 and 2 set
perms.test(0);   // true  — throws std::out_of_range if index >= N
perms[0];        // true  — no bounds check
perms.any();     // true  — at least one bit set
perms.none();    // false — not all zero
perms.all();     // false — not all one
perms.count();   // 2     — number of set bits
perms.size();    // 8     — always N (compile-time constant)

// Conversion
uint64_t raw = perms.to_ulong();   // 5  (throws std::overflow_error if N > 64)
std::string s = perms.to_string(); // "00000101"  (MSB first)

// Bitwise operators between same-size bitsets
std::bitset<8> x{0b11001100u}, y{0b10101010u};
auto combined = x | y;  // 0b11101110
auto shared   = x & y;  // 0b10001000
auto diff     = x ^ y;  // 0b01100110
auto flipped  = ~x;     // 0b00110011

#include <bitset>

enum PermBit : size_t {
    OtherExec  = 0,
    OtherWrite = 1,
    OtherRead  = 2,
    GroupExec  = 3,
    GroupWrite = 4,
    GroupRead  = 5,
    OwnerExec  = 6,
    OwnerWrite = 7,
    OwnerRead  = 8,
};

std::bitset<9> perm;
perm.set(OwnerRead);
perm.set(OwnerWrite);
perm.set(GroupRead);
perm.set(OtherRead);

// Unix octal 0644 == 110 100 100 binary
std::cout << perm.to_string() << '\n';  // "110100100"
std::cout << std::oct << perm.to_ulong() << '\n';  // 644

enum class Perm : uint32_t {
    None    = 0,
    Read    = 1u << 0,
    Write   = 1u << 1,
    Execute = 1u << 2,
    All     = Read | Write | Execute,
};

constexpr Perm operator|(Perm a, Perm b) noexcept {
    return static_cast<Perm>(static_cast<uint32_t>(a) | static_cast<uint32_t>(b));
}
constexpr Perm operator&(Perm a, Perm b) noexcept {
    return static_cast<Perm>(static_cast<uint32_t>(a) & static_cast<uint32_t>(b));
}
constexpr Perm operator~(Perm a) noexcept {
    return static_cast<Perm>(~static_cast<uint32_t>(a));
}
constexpr bool has_perm(Perm set, Perm flag) noexcept {
    return (set & flag) == flag;
}

constexpr auto rw = Perm::Read | Perm::Write;
static_assert(has_perm(rw, Perm::Read));
static_assert(!has_perm(rw, Perm::Execute));

#include <bit>
#include <cstdint>

uint32_t n = 12u;  // 0b1100

// ── Power-of-two check ────────────────────────────────────────────────────
// Classic: works for n > 0; gives wrong answer for n == 0.
bool is_pow2_classic = (n > 0) && ((n & (n - 1u)) == 0u);
// C++20: handles n == 0 correctly (returns false).
bool is_pow2_modern  = std::has_single_bit(n);   // C++20

// ── Isolate the lowest set bit ────────────────────────────────────────────
// The expression n & (-n) exploits two's-complement: -n flips all bits then
// adds 1, so the result has exactly one bit — the lowest set bit of n.
uint32_t lsb_classic = n & (-n);            // 4  (0b0100)
// No direct <bit> equivalent; the trick remains idiomatic.

// ── Clear the lowest set bit ──────────────────────────────────────────────
// Subtracting 1 turns the LSB and all zeros below it into 1s; AND clears them.
uint32_t cleared_classic = n & (n - 1u);   // 8  (0b1000) — clears bit 2
// Use case: iterate over all set bits in O(popcount) steps:
uint32_t bits = 0b10110100u;
while (bits) {
    int pos = std::countr_zero(bits);  // C++20: index of LSB
    // process bit at position 'pos' ...
    bits &= bits - 1u;                 // clear it and continue
}

// ── Round up to next power of two ─────────────────────────────────────────
// Classic (32-bit only, breaks for n == 0):
uint32_t next_pow2_classic = n;
--next_pow2_classic;
next_pow2_classic |= next_pow2_classic >> 1;
next_pow2_classic |= next_pow2_classic >> 2;
next_pow2_classic |= next_pow2_classic >> 4;
next_pow2_classic |= next_pow2_classic >> 8;
next_pow2_classic |= next_pow2_classic >> 16;
++next_pow2_classic;  // 16
// C++20: one call, handles all cases, UB-safe for in-range values.
uint32_t next_pow2_modern = std::bit_ceil(n);  // 16   C++20

// ── Largest power of two <= n ─────────────────────────────────────────────
uint32_t prev_pow2_classic = 1u << (31u - std::countl_zero(n));  // 8
uint32_t prev_pow2_modern  = std::bit_floor(n);                  // 8   C++20

// ── Floor log2 ────────────────────────────────────────────────────────────
int ilog2_classic = 31 - std::countl_zero(n);  // 3
int ilog2_modern  = static_cast<int>(std::bit_width(n)) - 1;  // 3   C++20

#include <bit>

// std::endian: C++20. if constexpr: C++17.
if constexpr (std::endian::native == std::endian::little) {
    // x86, ARM (typical LE mode)
} else if constexpr (std::endian::native == std::endian::big) {
    // MIPS, SPARC, network byte order
}

// C++23: std::byteswap — single-instruction byte reversal
// C++20 and earlier: manual implementation
constexpr uint32_t bswap32(uint32_t n) noexcept {
    return ((n & 0xFF000000u) >> 24u)
         | ((n & 0x00FF0000u) >>  8u)
         | ((n & 0x0000FF00u) <<  8u)
         | ((n & 0x000000FFu) << 24u);
}

constexpr uint32_t to_network_order(uint32_t host) noexcept {
    if constexpr (std::endian::native == std::endian::little)
        return bswap32(host);
    return host;
}

uint32_t x = 1u;
x << 32;   // UB — amount equals type width
x << -1;   // UB — negative shift amount

uint8_t a = 0xFFu;
auto b = ~a;           // b is int{0xFFFFFF00} — NOT uint8_t{0x00}

uint8_t c = ~a;        // c == 0x00: truncation gives the correct final value,
                       // but relying on implicit narrowing is fragile

uint8_t d = static_cast<uint8_t>(~a);  // explicit and correct

// The hazard becomes visible here:
uint16_t mask = ~uint8_t{0x0Fu};  // mask == 0xFFF0, not 0x00F0 as intended
uint16_t safe = static_cast<uint8_t>(~uint8_t{0x0Fu});  // 0x00F0 — correct

std::bit_ceil(uint8_t{200})  // UB: next pow2 is 256, not representable in uint8_t

// Error: sizeof(double) == 8, sizeof(uint32_t) == 4
auto x = std::bit_cast<uint32_t>(3.14);  // compile error

// Correct: use uint64_t for double
auto y = std::bit_cast<uint64_t>(3.14);  // OK