Work Plan

1. Introduction, types of programming languages, pseudo-code
2. Variables, data types
3. Pointers and arrays
4. Simple instructions and tricks
5. Functions and procedures
6. Data structures
7. Input / Output
8. Debug
9. Operators, Iterators
10. Polymorphism
11. Functional / object oriented programming
12. Advanced topics, threads
13. Software development process, agile, tdd
14. Final Test during last classes: about 30 open/close questions - mostly closed.

Loops

There are three types of loops for, while and do while.

for ( init-statement(optional) ;  condition(optional) ; iteration_expression(optional) ) 

Any "while" loop can be trivially re-written as a "for"

while (number <= 126)

is the same as

for ( ; number <= 126 ; )

If statement

The "if ... else ..." branching mechanism is a familiar construct in many procedural programming languages. In C++, it is simply called an if statement, and the general syntax is

if (condition) {
    Statement1;
    ...
    ...
    StatementN;
} else {
    StatementN+1;
    ...
    ...
    StatementN+M;
}

Ternary if

In computer programming, ?: is a ternary operator that is part of the syntax for basic conditional expressions.

(condition) ? (if_true) : (if_false)

Example

largest = ((a > b) ? a : b);

The main fundamental difference is that the ternary operator is an expression whereas the if structure is a statement. A ternary operator expression's result can be assigned to a variable -- the results of an if statement cannot.

Ternary operator does not support block of code as the block of code does not return a value (is not an expression).

Test

What will happen?

int x,y;
cin>>x>>y;

((x<y)?x:y) = -((x>y)?x:y);

Switch

For choosing out of more than two options we can use switch

switch (selector)
{
    case label1:    <statements 1>
                    break;
    ...
    ...
    ...

    case labelN:    <statements N>
                    break;

    default:        <statements>
}

The statements which are executed are exactly those between the first label which matches the value of selector and the first "break" after this matching label.

When a "break" is encountered within a case's statement, control is transferred immediately to the first program statement following the entire "switch" statement. Otherwise, execution continues.

Switch

Without breaks all code under given case will be executed.

Regular switch statements, by default, have a unique scope for the whole switch (as shown by the {}).

However this given an error:

switch( x ) {
    case 0:
        int y = 0;
        printf("int: %d\n",y);
    case 1:
        char y = 'A'; // Error: y is already an int
        printf("char: %c\n",y);
    case 2:
        float y = 1.66;
        printf("float: %f\n",y);
    default:
        // do nothing
    break;
}

Solution:

switch(x) {
    case 0: {
        int y = 0;
        printf("int: %d\n",y);
    }
    case 1: {
        char y = 'A'; // Error: y is already an int
        printf("char: %c\n",y);
    }
    case 2: {
        float y = 1.66;
        printf("float: %f\n",y);
    }
    default: {
        // do nothing
        break;
    }
}

Special types

Type pair

The pair container is a simple container consisting of two data elements or objects.

The first element is referenced as ‘first’ and the second element as ‘second’ and the order is fixed (first, second).

Pair is used to combine together two values which may be different in type.

To access the elements, we use variable name followed by dot operator followed by the keyword first or second.

#include <iostream>
#include <utility>
using namespace std;

int main()
{
    pair <int, char> PAIR1 ;
    pair <string, double> PAIR2 ("GeeksForGeeks", 1.23) ;
    pair <string, double> PAIR3 ;

    PAIR1.first = 100;
    PAIR1.second = 'G' ;

    PAIR3 = make_pair ("GeeksForGeeks is Best",4.56);

    cout << PAIR1.first << " " ;
    cout << PAIR1.second << endl ;

    cout << PAIR2.first << " " ;
    cout << PAIR2.second << endl ;

    cout << PAIR3.first << " " ;
    cout << PAIR3.second << endl ;

    return 0;
}

Type tuple

std::tuple is a fixed-size collection of different values.

// Declaring tuple
tuple <char, int, float> geek;

// Assigning values to tuple using make_tuple()
geek = make_tuple('a', 10, 15.5);

// Printing initial tuple values using get()
cout << "The initial values of tuple are : ";
cout << get<0>(geek) << " " << get<1>(geek);
cout << " " << get<2>(geek) << endl;

// Use of get() to change values of tuple
get<0>(geek) = 'b';
get<2>(geek) =  20.5;

Operators

Operators

Operators precedence

Operators precedence

Example:

x = -a * b;

Precedence levels = has level 15, * has level 5 and - has level 3.

Thus it is equivalent to:

x = ((-a) * b);

Operators precedence

Operators that have the same precedence are bound to their arguments in the direction of their associativity. For example, the expression a = b = c is parsed as a = (b = c), and not as (a = b) = c because of right-to-left associativity of assignment, but a + b - c is parsed (a + b) - c and not a + (b - c) because of left-to-right associativity of addition and subtraction.

Unary operators

The Operators which operate on Single Operand known as Unary Operators, some of the unary operators are:

++ Increment Operator -- Decrement Operator & Address Of Operator * Dereference operator - Unary Minus Operators ~ (One’s Compliment) Negation Operator ! Logical NOT

Increment operator "++"

The program fragment

x = 4;
y = x++;

results in "x" having the value 5 and "y" having the value 4, whereas

x = 4;
y = ++x;

results in both variables having value 5.

Why is it so?

Increment operator "++"

i++ makes a copy, increases i, and returns the copy (old value).

++i increases i, and returns i.

// ++i
function pre_increment(i) {
    i += 1;
    return i;
}
// i++
function post_increment(i) {
    copy = i;
    i += 1;
    return copy;
}

++i will be the faster than i++ since it doesn't make a copy.

Assignment statements

In general, assignment statements have a value equal to the value of the left hand side after the assignment. Hence the following is a legal expression which can be included in a program and which might be either evaluated as true or as false:

(y = ++x) == 5

That is why this does not create compilation error

if (a = b)
    cout << "a is equal to b.";

Test

What will be the value of b?

int a = 5;
int b = a++ + ++a;

(At least according to the things that we have just mentioned)

Coma operator

Comma operator (represented by the token ,) is a binary operator that evaluates its first operand and discards the result, and then evaluates the second operand and returns this value (and type).

Example:

/**
*  Assigns value of b into i.
*  Results: a=1, b=2, c=3, i=2
*/
int a=1, b=2, c=3;              
int i = (a, b);           

And another one:

/**
*  Increases value of a by 2, then assigns value of resulting operation a+b into i .
*  Results: a=3, b=2, c=3, i=5
*/
int a=1, b=2, c=3;
int i = (a += 2, a + b);

Coma operator

Last example:

int x=0;
if(cin>>x,x*=2,x<8) { /*do stuff*/}

What will be printed on the screen?

int main()
{
    int x = 10, y;

    y = (x++, printf("x = %d\n", x), ++x, printf("x = %d\n", x), x++);

    printf("y = %d\n", y);
    printf("x = %d\n", x);

    return 0;
}

Mod on negative values

std::cout << (-7 % 3) << std::endl;
std::cout << (7 % -3) << std::endl;)

Gives -1 and 1. In general if a % b = x then

(a/b)*b + x = a    

thus

(-7/3) => -2
-2 * 3 => -6
so a%b => -1

(7/-3) => -2
-2 * -3 => 6
so a%b => 1

Binary operators

Logical operators

Logical operators "&&" ("and"), "||" ("or") and "!" ("not"),

The operator "&&" has a higher precedence than the operator "||".

NOT ( ~ ): Bitwise NOT is an unary operator that flips the bits of the number i.e., if the ith bit is 0, it will change it to 1 and vice versa.

N = 5 = (101)
~N = ~5 = ~(101) = (010) = 2

AND ( & ): Bitwise AND is a binary operator that operates on two equal-length bit patterns. If both bits in the compared position of the bit patterns are 1, the bit in the resulting bit pattern is 1, otherwise 0.

OR ( | ): Bitwise OR is also a binary operator that operates on two equal-length bit patterns, similar to bitwise AND. If both bits in the compared position of the bit patterns are 0, the bit in the resulting bit pattern is 0, otherwise 1.

Shift operators

There are two shift operators a << b and a >> b.

The former shifts all the bits in a to the left by b positions; the latter does the same but shifts right.

You can think of left-shifting by b as multiplication by 2^b and right-shifting as integer division by 2^b.

The most common use for shifting is to access a particular bit, for example, 1 << x is a binary number with bit x set and the others clear

1 << 1 = 2 = 21
1 << 2 = 4 = 22 
1 << 4 = 16 = 24
1 << n = 2n

4 >> 1 = 2
6 >> 1 = 3
5 >> 1 = 2
16 >> 4 = 1 

Enumerate power set

Power set is a set of all subsets of a given set.

void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
    n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;

    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
    for(j = 0; j < set_size; j++)
    {
        /* Check if jth bit in the counter is set
            If set then print jth element from set */
        if(counter & (1<<j))
            printf("%c", set[j]);
    }
    printf("\n");
    }
}

Count ones in a number

Count bits which are one in a given number.

int count_ones(int num)
{
    int count = 0;
    int mask = 0x1;
    while (num) {
        if (num & mask)
        count++;
        num >>= 1;
    }
    return count;
}

Bit lookout

The & and | operators have lower precedence than comparison operators. That means that x & 3 == 1 is interpreted as x & (3 == 1), which is probably not what you want.

Examples tricks

Commenting/testing values

If you need to change a value really quick to test something:

int x =
    //Actual_value
    Testing_value
    ;

String concatenation

Two string literals, placed "next to" each other, will be treated as one:

printf("abc" "def"); // same as printf("abcdef")

This is useful for long strings that you can extend onto more than one line

Check if number is odd or even

if (num & 1)
    cout << "ODD";
else
    cout << "EVEN";

Since last bit denotes the parity of the number.

Operations with bit manipulation

// Using shift operator 

// t is non zero (2^(i)) to be exact if ith bit is set else 0
int t= num & (1<<i); 

// Setting ith bit

num|=(1<<i);

// flipping ith bit

num ^ = (1<<i); // ^ is the xor operator

// clearing the ith bit

num=num & ~(1<<i);

Fast multiplication by 2

n = n << 1;   // Multiply n with 2
n = n >> 1;   // Divide n by 2

More efficient than

n = n * 2;   // Multiply n with 2
n = n / 2;   // Divide n by 2

Notice that

101 >> 1 == 10

So

5 / 2 == 2

Swap with swap function

There is special function in C++ which allows us to swap values of two variables

int c=3;
int d=4;
swap(c,d); // Now c=4 and d=3

Swap 2 numbers using XOR

a XOR b is equal 1 iff a and b has different bit value.

// A quick way to swap a and b
a ^= b;
b ^= a;
a ^= b;

This method is fast and doesn’t require the use of 3rd variable.

Avoid using strlen()

//  Use of strlen() can be avoided by:
for (i=0; s[i]; i++) 
{ 
    ...
}
// loop breaks when the character array ends.    

Because the last symbol in string is a zero in the array of chars.

Maximum size of an array

We must be knowing that the maximum size of array declared inside the main function is of the order of 10^6 but if you declare array globally then you can declare its size up to 10^7.

Efficiently check if the number is power of 2

/* Function to check if x is power of 2*/   
bool isPowerOfTwo (int x)
{   
/* First x in the below expression is 
    for the case when x is 0 */
return x && (!(x&(x-1)));
}

Function return zero for power of 2 and non-zero value otherwise (remind that every non-zero value means true).

iota()

This function is used to assign continuous values to array. This function accepts 3 arguments, the array name, size, and the starting number.

// C++ code to demonstrate working of iota()
#include<iostream>
#include<numeric> // for iota()
using namespace std;
int main()
{
    // Initializing array with 0 values
    int ar[6] =  {0};

    // Using iota() to assign values
    iota(ar, ar+6, 20);

    // Displaying the new array
    cout << "The new array after assigning values is : ";
    for (int i=0; i<6 ; i++)
    cout << ar[i] << " ";

    return 0;

}

Output:

The new array after assigning values is : 20 21 22 23 24 25

Test

What does it count?

int x;  
int y;   
int p1,p2;  // the result goes here 

p1 = y ^ ((x ^ y) & -(x < y));
p2 = x ^ ((x ^ y) & -(x < y))

Extra

Random numbers

The rand() function in <stdlib.h> returns a pseudo-random integer between 0 and RAND_MAX.

Pseudorandom number generator, is a function that produces numbers according to some deterministic formula that appear to be random but actually are not. The value of a sequence is determined by so called seed.

Pseudorandom number is a number that isn't truly random, but is "random enough" for most purposes.

Pseudorandom numbers are not safe in cryptographic settings!

bits/stdc++.h

Instead of using so many includes , we can simply include bits/stdc++.h in the code and it takes care of all.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <numeric>
#include <bitset>
#include <fstream>
#include <iomanip>

// Instead of all of that we can just use

#include <bits/stdc++.h>

References

http://www.geeksforgeeks.org/c-tricks-competitive-programming-c-11/

http://en.cppreference.com/w/cpp/language/operator_precedence

https://www.topcoder.com/community/data-science/data-science-tutorials/a-bit-of-fun-fun-with-bits/

https://www.doc.ic.ac.uk/~wjk/c++Intro/

https://pl.wikipedia.org/wiki/Alternatywa_roz%C5%82%C4%85czna

https://stackoverflow.com/questions/31300738/why-ternary-operator-does-not-support-blocks

https://medium.com/@nilotpalmrinal9797/useful-c-tricks-8f251276a53d

http://msoucy.me/seminars/evilC/

http://opensourceforu.com/2012/06/power-programming-bitwise-tips-tricks/

https://www.hackerearth.com/practice/notes/bit-manipulation/