# Useful algorithm tricks

Hi

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;
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;
printf ("%d\n", (&arr) - arr);
return 0;
}
``````

Help me in adding more of these …

17 Likes

For c++ user

To avoid many #include just write

``````      #include <bits/stdc++.h>
``````

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.

8 Likes

Swaps can be performed in another way;
If you have 2 variables a and b, you can swap them by using the following:

``a = a + b - (b = a);``
16 Likes

Btw, in C++, you can use `swap(a, b)` to swap to integers a, b.

11 Likes

A Developer Community Forum for Beginners, Professionals, Experts and Researchers.
http://www.codetheta.com/

1 Like

Some other programming tricks

1. Find the power of 2 without using inbuilt function

`````` (1<<n)is  equal to pow(2,n)
``````

For Ex:
(1<<3) --> (00000001)<<3 = 00000100 = 8

2. Find if a number is even or odd
For odd numbers, (n&1) is equal to 1
For even numbers, (n&1) is equal to 0

if(n&1){
//…Odd
}else{
//Even…
}

3. Find mid point without overflow

int mid = (s+e)/2 may sometimes cause overflow

It is better to use mid = s + (e-s)/2

4 Likes

Always use built in function of C++, Usefull for binary manupulation like…

Number of trailing zeroes : builtin_ctz(x)

Number of 1-bits: __builtin_popcount(x)

Use template of C++, as much as you can, even in taking input or output…

FOR INPUT

template inline void fi(T &a) { register char c=0; while (c<33) c=getchar(); a=0; int tmp = 0; while (c>33) { if ( c == 45 ) tmp = 1; else a=a*10+c-‘0’; c=getchar(); } if ( tmp == 1 ) a = 0-(a); }

FOR OUTPUT

template void outpos(T n){if(n<0){outchar(’-’);n*=-1;}char snum;int i=0;do {snum[i++]=n%10+‘0’;n/=10;}
while(n);i=i-1;while(i>=0)outchar(snum[i–]);outchar(’\n’);}

4 Likes
2 Likes

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.

Ability to equate two arrays (using structs) : http://stackoverflow.com/a/744556

1 Like

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:

A = A ^ B

B = A ^ B;

A = A ^ B;

or A ^= B ^= A ^= B;

swap two variables using xor operator
Bitwise operator trick: Here is another trick to efficiently multiply a number with 7 using bitwise operator.

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.

N x 7 = (N << 3) - N

yes … i have just provided how it can be done …

Thanks for posting this. I have made a post to check for power of 2. Have a look at it.

Checking if a no is power of 2 - general - CodeChef Discuss

Happy Coding …

1 Like

Thanks for posting this. Have provided this link in source already …
Happy Coding …

Thanks for posting this. I have made a post to check for power of 2. Have a look at it.

https://discuss.codechef.com/questions/85703/checking-if-a-no-is-power-of-2

Happy Coding …

we can also use xor(^) operator to check the presence of a number odd times in an array when given all no except that are even times…

xor has property that if we xor same no it will give zero .

10^10=0;
int arr[]={2,2,5,6,6,9,5,9,9}
int odd=0; //xor of any no with 0 gives n
for(int i=0 —> arraylength)
odd^=arr[i];