Friday, July 28, 2017

Bitwise operations in C

& bitwise AND
| bitwise inclusive OR
^ bitwise XOR (eXclusive OR)
<< left shift
>> right shift
~ bitwise NOT (one's complement) (unary)

Masking operation:
To get the k-th bit of number n,
(n & ( 1 << k )) >> k
or
int mask =  1 << k;
int masked_n = n & mask;
int thebit = masked_n >> k;

Swap two variables without a temporary variable:
int x = 10, y = 5;
Method 1. XOR
// Code to swap 'x' (1010) and 'y' (0101)
x = x ^ y; // x now becomes 15 (1111)
y = x ^ y; // y becomes 10 (1010)
x = x ^ y; // x becomes 5 (0101)

note: XOR is both commutative and associative
y = (x^y)^y = x^(y^y) = x^0 = x
x = (x^y)^(x^y)^y = x^y^x = y

Method 2. arithmetic // may cause overflow
// Code to swap 'x' and 'y'
x = x + y; // x now becomes 15
y = x - y; // y becomes 10
x = x - y; // x becomes 5