Bit manipulation Technieques

XXX. Bit Manipulation Techniques

Bit Operations

Optimization

Basics

Core operations: & (and), | (or), ~ (not), ^ (exclusive-or, xor), and shift operators << and >>

• Set union A | B
• Set intersection A & B
• Set subtraction A & ~B
• Set negation ALL_BITS ^ A or ~A
• Set bit A |= 1 << bit
• Clear bit A &= ~(1 << bit)
• Test bit (A & 1 << bit) != 0
• Extract last bit A&-A or A&~(A-1) or x^(x&(x-1))
• Remove last bit A&(A-1)
• Get all 1-bits ~0

Examples

// Count ones in binary representation
int count_one(int n) {
    while(n) {
        n = n&(n-1);
        count++;
    }
    return count;
}

// Check if number is power of four
bool isPowerOfFour(int n) {
    return !(n&(n-1)) && (n&0x55555555);
}

^ tricks

// Add two integers using XOR
int getSum(int a, int b) {
    return b==0? a:getSum(a^b, (a&b)<<1);
}

// Find missing number
int missingNumber(vector& nums) {
    int ret = 0;
    for(int i = 0; i < nums.size(); ++i) {
        ret ^= i;
        ret ^= nums[i];
    }
    return ret^=nums.size();
}

| tricks

// Find largest power of 2
long largest_power(long N) {
    N = N | (N>>1);
    N = N | (N>>2);
    N = N | (N>>4);
    N = N | (N>>8);
    N = N | (N>>16);
    return (N+1)>>1;
}

// Reverse bits
uint32_t reverseBits(uint32_t n) {
    unsigned int mask = 1<<31, res = 0;
    for(int i = 0; i < 32; ++i) {
        if(n & 1) res |= mask;
        mask >>= 1;
        n >>= 1;
    }
    return res;
}

& tricks

// Reverse bits using masks
x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);

// Range Bitwise AND
int rangeBitwiseAnd(int m, int n) {
    int a = 0;
    while(m != n) {
        m >>= 1;
        n >>= 1;
        a++;
    }
    return m<

Applications

// DNA Sequences
class Solution {
public:
    vector findRepeatedDnaSequences(string s) {
        int sLen = s.length();
        vector v;
        if(sLen < 11) return v;
        char keyMap[1<<21]{0};
        int hashKey = 0;
        for(int i = 0; i < 9; ++i) 
            hashKey = (hashKey<<2) | (s[i]-'A'+1)%5;
        for(int i = 9; i < sLen; ++i) {
            if(keyMap[hashKey = ((hashKey<<2)|(s[i]-'A'+1)%5)&0xfffff]++ == 1)
                v.push_back(s.substr(i-9, 10));
        }
        return v;
    }
};

Sets

// Generate all subsets
vector> subsets(vector& nums) {
    vector> vv;
    int size = nums.size(); 
    if(size == 0) return vv;
    int num = 1 << size;
    vv.resize(num);
    for(int i = 0; i < num; ++i) {
        for(int j = 0; j < size; ++j)
            if((1<

Bitset

// Bitset example
int main () {
    std::bitset<8> foo (std::string("10110011"));
    std::cout << foo << " has ";
    std::cout << foo.count() << " ones and ";
    std::cout << (foo.size()-foo.count()) << " zeros.\n";
    return 0;
}