// The five basic moves for working with bits.
// All of them on unsigned types, with the width written into the type name.
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

static void show(const char *label, uint32_t v)
{
    printf("  %-28s 0x%08" PRIX32 "\n", label, v);
}

int main(void)
{
    uint32_t v = 0x00F0'0000;          // C23's digit separator
    show("start", v);

    // (1) set --- put a 1 in that place
    v |= UINT32_C(1) << 3;
    show("set bit 3        (|=)", v);

    // (2) clear --- AND with a mask that is 0 only there
    v &= ~(UINT32_C(1) << 20);
    show("clear bit 20     (&= ~)", v);

    // (3) test --- the result is 0 or *the value of that bit*, not 1
    printf("  is bit 3 on?  %s\n", (v & (UINT32_C(1) << 3)) ? "yes" : "no");
    printf("  the value of v & (1<<3) is %" PRIu32 ", not 1\n",
           v & (UINT32_C(1) << 3));

    // (4) flip --- XOR inverts exactly where the mask has 1s
    v ^= UINT32_C(0xF0);
    show("flip bits 4..7   (^=)", v);

    // (5) replace a field --- clear it, then shift the new value in
    // Treat bits 8..15 as one eight-bit field.
    uint32_t field = 0xAB;
    uint32_t mask  = UINT32_C(0xFF) << 8;
    v = (v & ~mask) | ((field << 8) & mask);
    show("put 0xAB into bits 8..15", v);

    // Reading it back is the reverse --- shift down, then mask
    printf("  reading it back gives 0x%02" PRIX32 "\n", (v >> 8) & 0xFF);
    return 0;
}

// The idioms one meets most often --- and why they work.
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

// Keep only the lowest set bit of x.
// On unsigned values 0u - x equals (~x + 1). Below the lowest set bit nothing
// changes and above it everything flips, so the AND leaves just that one bit.
static uint32_t lowest_one(uint32_t x) { return x & (0u - x); }

// Clear the lowest set bit. x-1 turns that bit into 0 and all below it into 1s.
static uint32_t clear_lowest_one(uint32_t x) { return x & (x - 1u); }

// Is it a power of two --- the same question as "is exactly one bit set".
static int is_power_of_two(uint32_t x) { return x != 0 && (x & (x - 1u)) == 0; }

// Round up to a multiple of a, where a is a power of two.
static uint32_t align_up(uint32_t x, uint32_t a) { return (x + a - 1u) & ~(a - 1u); }

// Rotate left by n. Safe when n == 0 as well --- see below.
static uint32_t rotate_left(uint32_t x, unsigned n)
{
    return (x << (n & 31)) | (x >> ((32u - n) & 31));
}

// How many 1 bits --- loops once per set bit (Kernighan's way).
static unsigned count_ones(uint32_t x)
{
    unsigned n = 0;
    while (x) { x &= x - 1u; n++; }
    return n;
}

int main(void)
{
    uint32_t x = 0x0000'0B40;          // …1011 0100 0000
    printf("x = 0x%08" PRIX32 "\n", x);
    printf("  lowest set bit  (x & -x)     = 0x%08" PRIX32 "\n", lowest_one(x));
    printf("  clear lowest    (x & (x-1))  = 0x%08" PRIX32 "\n", clear_lowest_one(x));
    printf("  number of 1 bits             = %u\n", count_ones(x));

    puts("powers of two:");
    for (uint32_t v = 0; v <= 5; v++)
        printf("  %" PRIu32 " -> %s\n", v, is_power_of_two(v) ? "yes" : "no");
    printf("  1024 -> %s, 1000 -> %s\n",
           is_power_of_two(1024) ? "yes" : "no", is_power_of_two(1000) ? "yes" : "no");

    puts("rounding up to a multiple of 16:");
    for (uint32_t v = 0; v <= 33; v += 16)
        printf("  align_up(%2" PRIu32 ", 16) = %" PRIu32 "\n", v, align_up(v, 16));
    printf("  align_up(17, 16) = %" PRIu32 "\n", align_up(17, 16));

    puts("rotation keeps every bit --- nothing falls off the end:");
    printf("  rotate_left(0x80000001, 1) = 0x%08" PRIX32 "\n", rotate_left(0x8000'0001u, 1));
    printf("  rotate_left(0x80000001, 0) = 0x%08" PRIX32 "  (n = 0 is safe here)\n",
           rotate_left(0x8000'0001u, 0));
    return 0;
}

// C23 gave the idioms names --- <stdbit.h>.
// Put the hand-written version and the standard function side by side and check.
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdbit.h>

static unsigned count_by_hand(uint32_t x)
{
    unsigned n = 0;
    while (x) { x &= x - 1u; n++; }
    return n;
}

static unsigned width_by_hand(uint32_t x)          // bits needed to hold x
{
    unsigned n = 0;
    while (x) { x >>= 1; n++; }
    return n;
}

int main(void)
{
    printf("__STDC_VERSION_STDBIT_H__ = %ld\n", (long)__STDC_VERSION_STDBIT_H__);
    printf("byte order is %s\n",
           __STDC_ENDIAN_NATIVE__ == __STDC_ENDIAN_LITTLE__ ? "little endian"
           : __STDC_ENDIAN_NATIVE__ == __STDC_ENDIAN_BIG__  ? "big endian"
                                                            : "neither");

    uint32_t samples[] = { 0u, 1u, 0x0000'0B40u, 300u, 0xFFFF'FFFFu };
    puts("value       ones(hand/std)  width(hand/std)  bit_ceil   leading zeros");
    for (size_t i = 0; i < sizeof samples / sizeof samples[0]; i++) {
        uint32_t x = samples[i];
        printf("0x%08" PRIX32 "   %2u / %-2u        %2u / %-2u         %-10" PRIu32 " %u\n",
               x,
               count_by_hand(x), (unsigned)stdc_count_ones(x),
               width_by_hand(x), (unsigned)stdc_bit_width(x),
               (uint32_t)stdc_bit_ceil(x),
               (unsigned)stdc_leading_zeros(x));
    }

    // The position-finding functions count from 1, and 0 means "there is none".
    printf("first_leading_one(0x00F0) = %u  (counted from the top, 1-based)\n",
           (unsigned)stdc_first_leading_one(UINT32_C(0x00F0)));
    printf("first_trailing_one(0x00F0) = %u  (counted from the bottom)\n",
           (unsigned)stdc_first_trailing_one(UINT32_C(0x00F0)));
    printf("first_trailing_one(0) = %u  (zero means 'there is none')\n",
           (unsigned)stdc_first_trailing_one(UINT32_C(0)));

    // The power-of-two test got a name too.
    printf("has_single_bit(1024) = %d, has_single_bit(1000) = %d\n",
           (int)stdc_has_single_bit(UINT32_C(1024)),
           (int)stdc_has_single_bit(UINT32_C(1000)));
    return 0;
}

// The place bit work burns people most often --- integer promotion.
// Anything narrower than int is widened to int before the operation, so what
// you thought was "eight bits flipped" comes out thirty-two bits wide.
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main(void)
{
    uint8_t c = 0x0F;

    // The type of ~c is int, not uint8_t.
    printf("c             = 0x%02X\n", c);
    printf("~c            = 0x%08X   <- not eight bits\n", (unsigned)~c);
    printf("(uint8_t)~c   = 0x%02X         <- narrow it back yourself\n",
           (unsigned)(uint8_t)~c);
    // Writing (~c == 0xF0) here is stopped by gcc with -Wsign-compare.
    printf("((uint8_t)~c == 0xF0) is %s\n", ((uint8_t)~c == 0xF0) ? "true" : "false");

    // Where char is signed, a byte of 0x80 or more becomes negative when widened,
    // which is why bytes are held in unsigned char.
    char signed_byte = (char)0x80;
    unsigned char plain_byte = 0x80;
    printf("a char holding 0x80, widened  : %d\n", (int)signed_byte);
    printf("an unsigned char holding 0x80 : %d\n", (int)plain_byte);
    printf("masking with 0xFF fixes it    : %d\n", (int)(signed_byte & 0xFF));

    // A mask has a width too --- the width of its type.
    uint64_t wide = 0xFFFF'FFFF'FFFF'FFFFu;
    printf("wide & ~0u          = 0x%016" PRIX64 "   <- ~0u is 32 bits wide\n",
           wide & ~0u);
    printf("wide & ~UINT64_C(0) = 0x%016" PRIX64 "\n", wide & ~UINT64_C(0));
    return 0;
}

// A bitmap --- the shape bit work most often takes in real programs.
// There is no reason to spend a million bytes on a million true/false answers.
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbit.h>

#define BITS_PER_WORD 64
#define WORDS(n)      (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD)

#define N 1000
static uint64_t set[WORDS(N)];

// Which word, and which bit inside it, does index i live in?
// The word size is a power of two, so the division and remainder become a shift and a mask.
static size_t   word_of(size_t i) { return i >> 6; }        // i / 64
static unsigned bit_of (size_t i) { return i & 63u; }       // i % 64

static void bit_set   (size_t i) { set[word_of(i)] |=  UINT64_C(1) << bit_of(i); }
static void bit_clear (size_t i) { set[word_of(i)] &= ~(UINT64_C(1) << bit_of(i)); }
static int  bit_test  (size_t i) { return (set[word_of(i)] >> bit_of(i)) & 1u; }

static size_t bit_count(void)
{
    size_t total = 0;
    for (size_t w = 0; w < WORDS(N); w++)
        total += stdc_count_ones(set[w]);          // one whole word at a time
    return total;
}

int main(void)
{
    printf("%d flags need %zu bytes as a bitmap, %d bytes as one char each\n",
           N, sizeof set, N);

    // The sieve of Eratosthenes --- the textbook use of a bitmap
    memset(set, 0, sizeof set);
    for (size_t i = 2; i < N; i++)
        bit_set(i);                                // everything is "maybe prime" to start
    for (size_t p = 2; p * p < N; p++)
        if (bit_test(p))
            for (size_t m = p * p; m < N; m += p)
                bit_clear(m);

    // Clear the spare bits at the end of the last word so they are not counted ---
    for (size_t i = N; i < WORDS(N) * BITS_PER_WORD; i++)
        bit_clear(i);

    printf("primes below %d: %zu\n", N, bit_count());
    printf("  is 997 prime? %s\n", bit_test(997) ? "yes" : "no");
    printf("  is 999 prime? %s\n", bit_test(999) ? "yes" : "no");

    printf("the first ten:");
    size_t shown = 0;
    for (size_t i = 0; i < N && shown < 10; i++)
        if (bit_test(i)) { printf(" %zu", i); shown++; }
    puts("");
    return 0;
}