Bit Manipulation

#include <stdio.h>

// SET bit i (porta a 1)
#define SET_BIT(n, i)    ((n) |= (1 << (i)))

// CLEAR bit i (porta a 0)
#define CLEAR_BIT(n, i)  ((n) &= ~(1 << (i)))

// TOGGLE bit i (inverte)
#define TOGGLE_BIT(n, i) ((n) ^= (1 << (i)))

// CHECK bit i (1 se settato, 0 altrimenti)
#define CHECK_BIT(n, i)  (((n) >> (i)) & 1)

void stampa_binario(unsigned int n, int bits) {
    for (int i=bits-1; i>=0; i--) {
        printf("%d", (n >> i) & 1);
        if (i % 4 == 0 && i > 0) printf("_");
    }
}

int main() {
    unsigned int x = 0b0000_1010;  // C++14: binary literals con separatori

    printf("Iniziale: "); stampa_binario(x, 8); printf(" (%d)\n", x);

    SET_BIT(x, 0);
    printf("Set bit0: "); stampa_binario(x, 8); printf(" (%d)\n", x);

    CLEAR_BIT(x, 1);
    printf("Clear b1: "); stampa_binario(x, 8); printf(" (%d)\n", x);

    TOGGLE_BIT(x, 3);
    printf("Toggle 3: "); stampa_binario(x, 8); printf(" (%d)\n", x);

    printf("Bit 2 = %d\n", CHECK_BIT(x, 2));
    printf("Bit 3 = %d\n", CHECK_BIT(x, 3));

    // Bitmask per permessi (stile Unix)
    #define READ    0b100  // 4
    #define WRITE   0b010  // 2
    #define EXECUTE 0b001  // 1

    int permessi = 0;
    permessi |= READ;    // Aggiungi lettura
    permessi |= WRITE;   // Aggiungi scrittura
    printf("\nPermessi: %d (rwx = %d%d%d)\n",
           permessi,
           !!(permessi & READ),
           !!(permessi & WRITE),
           !!(permessi & EXECUTE));

    permessi &= ~WRITE;  // Rimuovi scrittura
    printf("Senza W: %d (r-x = %d%d%d)\n",
           permessi,
           !!(permessi & READ),
           !!(permessi & WRITE),
           !!(permessi & EXECUTE));

    return 0;
}

#include <stdio.h>

// Verifica se n è potenza di 2
// Potenze di 2 hanno esattamente 1 bit a 1: es. 8=1000, 16=10000
// n & (n-1) azzera il bit meno significativo: se n è pwr2 → risulta 0
int e_potenza_di_2(int n) { return n > 0 && (n & (n-1)) == 0; }

// Swap senza variabile temporanea (con XOR)
// a = a^b, b = a^b = a^b^b = a, a = a^b = a^b^a = b
void swap_xor(int *a, int *b) { *a ^= *b; *b ^= *a; *a ^= *b; }

// Conta i bit a 1 (population count)
int popcount(unsigned int n) {
    int count = 0;
    while (n) { count += n & 1; n >>= 1; }
    return count;
}
// Versione veloce (Brian Kernighan)
int popcount_fast(unsigned int n) {
    int c=0; while(n) { n &= n-1; c++; } return c;
    // n &= n-1 azzera il bit meno significativo ogni iterazione
}
// Versione built-in GCC (una sola istruzione CPU)
int popcount_gcc(unsigned int n) { return __builtin_popcount(n); }

// Trova il bit meno significativo (LSB)
int lsb(int n) { return n & (-n); }  // -n = ~n + 1 (complemento a 2)

// Conta gli zeri iniziali (leading zeros)
int leading_zeros(unsigned int n) { return n ? __builtin_clz(n) : 32; }

// Floor(log2(n)) usando bit tricks
int floor_log2(unsigned int n) { return 31 - __builtin_clz(n); }

// Inverti i bit di un byte
unsigned char inverti_byte(unsigned char b) {
    b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;  // Scambia nibble
    b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
    b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
    return b;
}

// Numero con tutti i bit a 1 nei primi n bit
unsigned int maschera_n_bit(int n) { return (1u << n) - 1; }

// Estrai n bit a partire dalla posizione p
int estrai_bit(int num, int p, int n) {
    return (num >> p) & ((1 << n) - 1);
}

int main() {
    printf("Potenze di 2: ");
    for (int i=0; i<20; i++) if (e_potenza_di_2(i)) printf("%d ", i);
    printf("\n");

    int a=15, b=27;
    swap_xor(&a, &b);
    printf("Swap XOR: a=%d b=%d\n", a, b);

    printf("popcount(255) = %d\n", popcount(255));    // 8
    printf("popcount(256) = %d\n", popcount(256));    // 1
    printf("popcount(127) = %d\n", popcount_fast(127)); // 7

    printf("LSB(12) = %d  (12=1100, LSB=4=100)\n", lsb(12));
    printf("leading_zeros(1) = %d\n", leading_zeros(1));    // 31
    printf("floor_log2(16) = %d\n", floor_log2(16));        // 4
    printf("floor_log2(100) = %d\n", floor_log2(100));      // 6

    printf("Maschera 4 bit: %d (= %X)\n", maschera_n_bit(4), maschera_n_bit(4));  // 15, F
    printf("Estrai bit 2-4 di 0b11010110: %d\n", estrai_bit(0b11010110, 2, 3));   // 101=5

    return 0;
}

#include <stdio.h>
#include <string.h>

// ===== Bitset: insieme di interi compresso in bit =====
// Invece di int presente[1000000] → usiamo unsigned int bs[1000000/32]
#define BS_SIZE 1024

typedef unsigned int Bitset[BS_SIZE / 32 + 1];

void bs_set(Bitset bs, int i)    { bs[i/32] |= (1u << (i%32)); }
void bs_clear(Bitset bs, int i)  { bs[i/32] &= ~(1u << (i%32)); }
int  bs_check(Bitset bs, int i)  { return (bs[i/32] >> (i%32)) & 1; }

// Crivello di Eratostene con bitset
void crivello(int max) {
    Bitset non_primo = {0};
    printf("Numeri primi fino a %d: ", max);
    for (int i=2; i<=max; i++) {
        if (!bs_check(non_primo, i)) {
            printf("%d ", i);
            for (int j=i*i; j<=max; j+=i) bs_set(non_primo, j);
        }
    }
    printf("\n");
}

// ===== Flags in stile enum bitfield =====
typedef enum {
    OPZIONE_NESSUNA   = 0,
    OPZIONE_VERBOSE   = 1 << 0,  // 1
    OPZIONE_DEBUG     = 1 << 1,  // 2
    OPZIONE_LOG_FILE  = 1 << 2,  // 4
    OPZIONE_QUIET     = 1 << 3,  // 8
    OPZIONE_FORCE     = 1 << 4,  // 16
} Opzioni;

void stampa_opzioni(Opzioni o) {
    if (o & OPZIONE_VERBOSE)  printf("  verbose ");
    if (o & OPZIONE_DEBUG)    printf("  debug ");
    if (o & OPZIONE_LOG_FILE) printf("  log_file ");
    if (o & OPZIONE_QUIET)    printf("  quiet ");
    if (o & OPZIONE_FORCE)    printf("  force ");
    printf("\n");
}

// ===== Trucco: verifica se int ha tutti bit uguali =====
int tutti_uguali(int n) {
    return n == 0 || n == ~0;
}

int main() {
    crivello(50);

    // Flags
    Opzioni opt = OPZIONE_VERBOSE | OPZIONE_DEBUG | OPZIONE_LOG_FILE;
    printf("Opzioni attive:"); stampa_opzioni(opt);

    opt &= ~OPZIONE_DEBUG;  // Rimuove DEBUG
    printf("Senza debug:"); stampa_opzioni(opt);

    opt ^= OPZIONE_QUIET;   // Toggle QUIET
    printf("Toggle quiet:"); stampa_opzioni(opt);

    printf("Sono attive verbose E log_file? %s\n",
           (opt & (OPZIONE_VERBOSE | OPZIONE_LOG_FILE)) == (OPZIONE_VERBOSE | OPZIONE_LOG_FILE)
           ? "Sì" : "No");

    return 0;
}