Found some useful tricks which will be useful during programming contest.
Quickly divide or multiply by 2
Numbers are stored in memory as bits. So bitwise operations are quite fast.
So if you shift all bits to the left, you are multiplying a number by 2:
cout<<(3 << 1); //6 //shift bits to the left one time
cout<<(3 << 2); //12
Similarly if you shift bits to the right, you will be dividing them by 2:
cout<<(12 >> 1); //6
Swap two no without temporary.
Method 1 :
a = a + b;
b = a - b;
a = a - b;
Method 2 :
a ^= b;
b ^= a;
a ^= b;
Loop in C-string:
char s[100];
for (int i = 0; s[i]; ++i) { ... }
Quite useful (also avoids the strlen usage, that you could forget is O(n) and put on for condition.)
Testing if not negative 1:
if (~x) { ... }
In competitive programming we look to code fast and try to write as little as possible, so a simple
x ! = -1
can be shortened to 2 characters.
Last one:
Finding size of array without sizeof in c and c++
int main ()
{
int arr[100];
printf ("%d\n", (&arr)[1] - arr);
return 0;
}
This will include all standard c++ library including vectors , algorithm etc.
Faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
For faster I/O , which actually disables sync with scanf and printf , increasing speed of I/O. After writing this you cannot use scanf or printf , it will result in compilation error.
Using : ((x != 0) && !(x & (x - 1))) to check if x is a power of 2. (i.e x is of form 2^k)
Initializing array in compact form with additional flexibility:
int A[] = {[0 … 5] = 9, [6 … 9] = 0};
[Notice spaces between 0 and ‘…’ (ellipsis) and ‘…’ and 5)
Good list of bit manipulation tricks →
Finding minimum of 3 numbers using function with 2 args : k = min(a, min(b, c))
Exiting nested loops :
Either by using goto statement or by invalidating test condition for outer loop.
Here is few more C programming puzzles and tricks .Bitwise Xor of A and B(A^B) is equivalent to sum of A and B(A+B).
Hence algorithm can be re-written in terms of Xor operator as:
As we know that, left shifting any number by one bit multiply it by 2. Hence, multiplying any number with 8 is equivalent to right shifting it by 3 bits(For Example : NX3 = N << 3).
Replacing 8xN in above statement by 8 << 3.
template is generalized form of any function/class
if you use, then it will be free from data type and you can call a single function for different data type(for working on different data types) while if you don’t use then you have to define personalized function for each type of data