Bittwiddling hacks

gistfile1.txt

1. Check if a number is even or odd 
An integer number N is even if its least significant bit is 0 otherwise it is odd

N AND 1

2. Divide by 2
Given an integer number N you can divide it by 2 by shifting all the bits to the right with one position.

N >> 1 

3. Multiply by 2
Given an integer number N you can multiply it by 2 by shifting all the bits to the left with one position.

N << 1 

4. Compute 2^N
Computing 2^N can be done by shifting the number 1 to the left N times.

1 << N

5. Determine if N is a power of 2
The fastest way to determine if N is a power of 2 is by checking if the result of the following operations is 0.

N AND (N - 1) 

6. Swap two integer values
Given two integer values A and B you can swap their values using the XOR algorithm.

A = A XOR B  
B = A XOR B  
A = A XOR B

7. Compute the average of two numbers
Given two integer values we can compute their average by suming them up and then shifting the result to the right one position.

(A + B) >> 1

8. Set the Nth bit
Given an integer number A you can set the Nth bit by computing the result of the OR operation between A and a number named "mask."

mask = 1 << N  
A OR mask  

9. Unset the Nth bit
Given an integer number A, we can unset the Nth bit by computing the result of the AND operation between A and a number named "mask".

mask = ~ ( 1 << N )  
A AND mask