Some useful tricks in bit manipulation

1. a + b = (a ^ b) + (a & b) << 1

Example: add a and b without the add operation.

public int add(int a, int b){ while(b != 0){ int newA = a ^ b; int newB = (a & b) << 1; a = newA; b = newB; } } 2. remove the last 1.

x1 = 1100, x - 1 = 1011,    x & (x - 1) = 1000.

3. i & -i

i =                                  0000....1100;

- i =  1111.....0011 + 1 = 1111....0100;

i & -i = 0000....0100.

get the number only have the last digit of 1. used in BIT