Bit manipulation tricks

Bit Manipulation Guide

Bit Manipulation

Math

Core Concepts:

A comprehensive guide to bit manipulation operations including basic operations, masks, common patterns, and useful properties.

Categories:

1. Basic Bit Operations (get, set, clear, toggle)
2. Counting and Checking
3. Masks and Ranges
4. Common Applications
5. Helper Methods

Properties:

AND (&): 1 if both bits are 1
OR (|): 1 if either bit is 1
XOR (^): 1 if bits are different
NOT (~): Inverts all bits
Left Shift (<<): Multiplies by 2^n
Right Shift (>>): Divides by 2^n

Java Solution:

public class BitManipulation {
    public void commonBitOperations() {
        int num = 59;    // Example: 111011 in binary
        int i = 3;       // Position to manipulate (0-indexed from right)
        
        // 1. BASIC BIT OPERATIONS
        
        // Get bit at position i
        boolean isSet = (num & (1 << i)) != 0;
        
        // Set bit at position i to 1
        num = num | (1 << i);
        
        // Clear bit at position i
        num = num & ~(1 << i);
        
        // Toggle bit at position i
        num = num ^ (1 << i);
        
        // 2. COUNTING AND CHECKING
        
        // Count total set bits (1s)
        int count = Integer.bitCount(num);
        
        // Check if power of two
        boolean isPowerOfTwo = (num > 0) && (num & (num - 1)) == 0;
        
        // 3. MASKS AND RANGES
        
        // Get lowest set bit
        int lowestSetBit = num & -num;

        // Clear lowest set bit
        int clearlowestSetBit = num & (num - 1);

        
        // Clear bits after position i
        int clearedAfter = num & ~((1 << (i + 1)) - 1);
        
        // Clear bits before position i
        int clearedBefore = num & ((1 << i) - 1);
        
        // 4. COMMON APPLICATIONS
        
        // XOR Swap
        int a = 5, b = 10;
        a = a ^ b;
        b = a ^ b;    // (a^b)^b = a
        a = a ^ b;    // (a^b)^a = b
        
        // Get MSB position
        int msb = 31 - Integer.numberOfLeadingZeros(num);
        
        // Create k-bit mask
        int k = 3;
        int mask = (1 << k) - 1;  // Creates k ones: 111
        
        // Check if numbers differ by one bit
        boolean differByOneBit = ((a ^ b) > 0) && 
            ((a ^ b) & ((a ^ b) - 1)) == 0;
        
        // 5. ARITHMETIC SHORTCUTS
        
        // Multiply/Divide by 2
        int multiplyBy2 = num << 1;
        int divideBy2 = num >> 1;
    }
    
    // Helper method to reverse bits
    private int reverseBits(int n) {
        int ret = 0, power = 31;
        while (n != 0) {
            ret += (n & 1) << power;
            n = n >>> 1;
            power--;
        }
        return ret;
    }
    
    // Helper method for XOR up to n
    private int xorUptoN(int n) {
        if (n % 4 == 0) return n;
        if (n % 4 == 1) return 1;
        if (n % 4 == 2) return n + 1;
        return 0;
    }
}

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;
}