1. Bit Manipulation

From here.

Basics

At the heart of bit manipulation are the bit-wise operators & (and), | (or), ~ (not) and ^ (exclusive-or, xor) and shift operators a << b and a >> b.

There is no boolean operator counterpart to bitwise exclusive-or, but there is a simple explanation. The exclusive-or operation takes two inputs and returns a 1 if either one or the other of the inputs is a 1, but not if both are. That is, if both inputs are 1 or both inputs are 0, it returns 0. Bitwise exclusive-or, with the operator of a caret, ^, performs the exclusive-or operation on each pair of bits. Exclusive-or is commonly abbreviated XOR.

• 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 the number of ones in the binary representation of the given number, also known as the Hamming weight.

int countOne(int n) {
    int count = 0;
    while(n > 0) {
        n = n&(n-1);
        count++;
    }
    return count;
}

Is power of four (actually map-checking, iterative and recursive methods can do the same)

boolisPowerOfFour(int n) {
    return (n&(n-1) == 0) && (n&0x55555555); 
    //check the 1-bit location; 0x55555555 is (0101) which is 5 repeated for 8 times.
}

^tricks

Use ^ to remove even exactly same numbers and save the odd, or save the distinct bits and remove the same.

SUM OF TWO INTEGERS

Use ^ and & to add two integers

int getSum(int a,int b) {
    return b==0? a : getSum(a^b, (a&b)<<1); //be careful about the terminating condition;
}

MISSING NUMBER

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums = [0, 1, 3] return 2. (Of course, you can do this by math.) The appeared values will offset corresponding indexes by ^.

int missingNumber(int[] nums) {
    int ret = 0;
    for(int i = 0; i < nums.length; ++i) {
        ret ^= i;
        ret ^= nums[i];
    }
    return ret ^= nums.length;
}

|tricks

Keep as many 1-bits as possible

Find the largest power of 2 (most significant bit in binary form), which is less than or equal to the given number N.

long largestPower(long N) {
    //changing all right side bits to 1.
    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

Reverse bits of a given 32 bits unsigned integer.

int reverseBit(int n) {
    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

Just selecting certain bits

Reversing the bits in integer

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

BITWISE AND OF NUMBERS RANGE

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. when m != n, There is at least an odd number and an even number, so the last bit position result is 0.

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