Bit Hacks

bit_hacks.cpp

/**
 * Bit hacks
 *
 * Not as extensive as https://graphics.stanford.edu/~seander/bithacks.html
 * but I want a quick reference for myself
 */

// multiply x by 2^n
int mul_pow2(int x, int n) {
    return x << n;
}

// divide x by 2^n
int div_pow2(int x, int n) {
    return x >> n;
}

// set jth bit
int set_bit(int x, int j) {
    return x | (1 << j);
}

// check if jth bit is set
bool is_bit_set(int x, int j) {
    return (x & (1 << j)) != 0;
}

// unset jth bit
int unset_bit(int x, int j) {
    return x & ~(1 << j);
}

// flip jth bit
int flip_bit(int x, int j) {
    return x ^ (1 << j);
}

// get the lowest bit set
int lowest_bit(int x) {
    return x & -x;
}

// get the highest bit set
int highest_bit(int x) {
    x |= (x >>  1);
    x |= (x >>  2);
    x |= (x >>  4);
    x |= (x >>  8);
    x |= (x >> 16);
    return x ^ (x >> 1);
    // can also return x - (x >> 1)
}