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[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;
          }

Source- link text and link text

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.

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 leading zeroes: builtin_clz(x)

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[65];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

Click for C++ tricks

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) : C array declaration and assignment? - Stack Overflow

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];

answer will be 9

2 Likes

what is the reason behind using template as much as we can, I am learning c++ so it will help me.

Can you post some tricks.

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