Useful algorithm tricks

c
c-plus-plus
strings

#1

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) { ... }
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

", (&arr)1 - arr);
return 0;
}

Source- link text and link text

Help me in adding more of these …


#2

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.


#3

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

#4

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


#5

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


#6

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


#7

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(’
');}


#8

Click for C++ tricks


#9

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


#10

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


#11

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


#12

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 …


#13

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


#14

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 …