BitHacks Notes.txt

http://graphics.stanford.edu/~seander/bithacks.html
Compute the minimum (min) or maximum (max) of two integers without branching
r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
--
Determining if an integer is a power of 2
f = v && !(v & (v - 1));
--
Conditionally set or clear bits without branching
bool f;         // conditional flag
unsigned int m; // the bit mask
unsigned int w; // the word to modify:  if (f) w |= m; else w &= ~m; 

w ^= (-f ^ w) & m;
--
Conditionally negate a value without branching
If you need to negate only when a flag is false, then use the following to avoid branching:
bool fDontNegate;  // Flag indicating we should not negate v.
int v;             // Input value to negate if fDontNegate is false.
int r;             // result = fDontNegate ? v : -v;

r = (fDontNegate ^ (fDontNegate - 1)) * v;
If you need to negate only when a flag is true, then use this:
bool fNegate;  // Flag indicating if we should negate v.
int v;         // Input value to negate if fNegate is true.
int r;         // result = fNegate ? -v : v;

r = (v ^ -fNegate) + fNegate;
--
Swapping values with XOR
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
--
Thus the following pseudocode prints all the subsets of a given set ( this set is known as a power set )
 //http://apps.topcoder.com/forums/;jsessionid=A2B903304231487272697FC9A2D20D05?module=Thread&threadID=671150&start=0&mc=18#1886133
String[] set={"apple", "banana", "carrot"};
int n=set.length;
 
// iterate over all the subsets
for (int i=0; i < (1<<n); i++)
{
    // generate the i-th subset
    Vector subset=new Vector();
    for (int k=0; k < n; k++)
    {
        if ((i&(1<<k)) > 0)
            subset.add(set[k]);
    }
            
    // perform an action over the subset, here just print it
    System.out.print("Subset "+i+":");
    for (int k=0; k<subset.size(); k++)
        System.out.print(" "+subset.get(k));
    System.out.println();
}

-----

Generating all subsets of a subset.
Consider a number 10110
The following numbers are subsets of this number
00000
00010
00100
00110
10000
10010
10100
10110
Now there's a nice and short way of generating them as shown below:
start
    N; //an integer
    X = N
    while true
        print X
        if( X == 0 )
            break;
        X = (X-1) & N;
    end while
end