// 비트를 다루는 다섯 가지 기본 동작.
// 모두 부호 없는 타입 위에서, 폭을 이름에 적은 타입으로 한다.
#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 의 자릿수 구분자
    show("start", v);

    // ① 세우기 --- 그 자리에 1 을 넣는다
    v |= UINT32_C(1) << 3;
    show("set bit 3        (|=)", v);

    // ② 지우기 --- 그 자리에만 0 인 마스크와 AND
    v &= ~(UINT32_C(1) << 20);
    show("clear bit 20     (&= ~)", v);

    // ③ 읽기 --- 결과는 0 이거나 「그 비트의 값」이지 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));

    // ④ 뒤집기 --- XOR 은 마스크가 1 인 자리만 뒤집는다
    v ^= UINT32_C(0xF0);
    show("flip bits 4..7   (^=)", v);

    // ⑤ 필드 바꿔 넣기 --- 지우고, 밀어 넣는다
    // 비트 8~15 를 하나의 8비트 필드로 본다.
    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);

    // 꺼내는 것은 반대 순서다 --- 내리고, 남긴다
    printf("  reading it back gives 0x%02" PRIX32 "\n", (v >> 8) & 0xFF);
    return 0;
}

// 자주 쓰는 비트 관용구들 --- 그리고 왜 그렇게 되는지.
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

// x 에서 가장 낮은 1 비트만 남긴다.
// 무부호에서 0u - x 는 (~x + 1) 과 같다. 가장 낮은 1 비트 *아래*는 그대로이고
// 그 위는 전부 뒤집히므로, 둘을 AND 하면 그 한 비트만 살아남는다.
static uint32_t lowest_one(uint32_t x) { return x & (0u - x); }

// 가장 낮은 1 비트를 지운다. x-1 은 그 비트를 0 으로 만들고 아래를 전부 1 로 만든다.
static uint32_t clear_lowest_one(uint32_t x) { return x & (x - 1u); }

// 2 의 거듭제곱인가 --- 1 비트가 정확히 하나인가와 같은 말이다.
static int is_power_of_two(uint32_t x) { return x != 0 && (x & (x - 1u)) == 0; }

// a(2의 거듭제곱)의 배수로 올림한다.
static uint32_t align_up(uint32_t x, uint32_t a) { return (x + a - 1u) & ~(a - 1u); }

// 왼쪽으로 n 만큼 회전. n == 0 일 때도 안전하다 --- 아래를 보라.
static uint32_t rotate_left(uint32_t x, unsigned n)
{
    return (x << (n & 31)) | (x >> ((32u - n) & 31));
}

// 1 비트의 개수 --- 켜진 비트 수만큼만 돈다(커니핸 방식).
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 이 관용구에 이름을 붙였다 --- <stdbit.h>.
// 손으로 짠 것과 표준 함수를 나란히 놓고 답이 같은지 확인한다.
#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)          // 담는 데 필요한 비트 수
{
    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));
    }

    // 자리 번호를 세는 함수는 *1 부터* 세고, 0 은 「없다」는 뜻이다.
    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)));

    // 2 의 거듭제곱 판정도 이름을 얻었다.
    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;
}

// 비트 연산에서 가장 자주 데이는 자리 --- 정수 승격.
// int 보다 좁은 타입은 연산 전에 int 로 넓혀진다. 그래서 「8비트를 뒤집었다」고
// 생각한 결과가 32비트짜리로 나온다.
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

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

    // ~c 의 타입은 uint8_t 가 아니라 int 다.
    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);
    // 여기서 (~c == 0xF0) 이라 적으면 gcc 가 -Wsign-compare 로 막아 준다.
    printf("((uint8_t)~c == 0xF0) is %s\n", ((uint8_t)~c == 0xF0) ? "true" : "false");

    // char 가 부호 있는 기계에서 0x80 이상인 바이트를 int 로 넓히면 음수가 된다.
    // 그래서 바이트를 다룰 때는 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));

    // 마스크의 폭도 타입을 따라간다.
    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;
}

// 비트맵 --- 비트 연산이 실무에서 가장 자주 쓰이는 모습.
// 참·거짓 백만 개를 담는 데 바이트 백만 개를 쓸 이유가 없다.
#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)];

// 번호 i 는 몇 번째 워드의 몇 번째 비트인가.
// 워드 크기가 2 의 거듭제곱이므로 나눗셈과 나머지를 시프트와 마스크로 적을 수 있다.
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]);          // 워드 하나를 한 번에
    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);

    // 에라토스테네스의 체 --- 비트맵의 교과서적 쓰임
    memset(set, 0, sizeof set);
    for (size_t i = 2; i < N; i++)
        bit_set(i);                                // 일단 전부 「소수일 수 있다」
    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);

    // 워드 끝의 남는 비트는 세지 않도록 지운다 --- 잊기 쉬운 자리다.
    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;
}