Various Usage of B.I.T.

I’ve always imagined what BIT (I will omit the dots, but don't confuse it with binary bits) can do and can’t. I have seen numerous times, experienced solvers say “Oh it’s easily solvable using BIT” leaving me wondering, “BIT on this problem! How on earth!” Still I haven’t found quite a good answer for this question. Looks like BIT can do as much as you can imagine it to do (and obviously design it to do so).

However, I am not going to explain the structure of BIT or how it works etc. As there are lots of well documented articles available on the net. I can’t help putting one specific link here, which is a TopCoder algorithm tutorial for BIT. So, if you are not familiar with BIT yet, first go ahead, and read that post.

In this post, we will discuss some of the most common application of BIT for solving data structure related problems, more specifically, where range sum updates and queries are involved.

Some methods used in this post:
Update(x, v): Adds V at the position x in BIT.
Query(x): Returns the cumulative value on position x in BIT.
Read the above tutorial to know how these methods are implemented.
We will be using 1-based indexing throughout the post.

(I) Point Update, Range Query:

This is the most common form of BIT, and just about 99% of online tutorials you will find on the net will describe this application. So here we don't have much to say. If your updates are like “Add v in the x position of the array”, and queries are like “What is the sum of elements in index range [a, b] in the array?”, then all you do for update is call Update(x, v) and answer queries by Query(b) - Query(a-1). Simple cumulative sum formula, nothing really astonishing. This problem is can be solved using BIT: SPOJ - MSE06H.

(II) Range Update, Point Query:

Although not something you see every now and then, but it's readily doable. Now you are required to update v over the range [a, b] and the query is performed on a single index x. So now you call update twice, first add v at index a, then remove v for indices larger than b, which is: Update(a, v); Update(b+1, -v); And for query, you simply call Query(x). Now to see why this works, the following reasoning can be made:

Lets consider, initially you have everything 0. So Query(x) will return 0, no matter what index you call it with. Suppose you have called Update(a, v) and Update(b+1, -v). Now what will happen if you call Query(x)? Three cases can arise:
1. if x < a, the query is not affected by the updates. So you get correct result.
2. if x > b, x will be affected by the update(a, v) since x ≥ a, and update(b+1, -v) since x ≥ b+1, therefore, v-v=0 so everything cancels out. Again, you get the correct result.
3. a ≤ x ≤ b. x is only affected by update(a, v), but not update(b+1, -v), therefore, Query(x)'s value is increased by v, and it will return the correct result.

As we can see, in this fashion, we can increment or decrement for a range [a, b], and get a single index effect for some index x. This problem is an example: SPOJ - UPDATEIT

(III) Range Update, Range Query:

I didn't even know it exists until I read some post in TopCoder forums (the post was made by: AnilKishore).

I will just re-state his explanation as it was quite clear itself. All we want here is to support range updates, and do range queries. As from the previous type, if we try to store range updates, the BIT structure effectively captures updates for single positions, instead of range/cumulative sums. However, we can do some tweaking to work around this problem.

Let's just consider only one update: Add v to [a, b] while the rest elements of the array is 0.
Now, consider sum(0, x) for all possible x, again three situation can arise:
1. 0 ≤ x < a : which results in 0
2. a ≤ x ≤ b : we get v * (x - (a-1))
3. b < x < n : we get v * (b - (a-1))

This suggests that, if we can find v*x for any index x, then we can get the sum(0, x) by subtracting T from it, where:
1. 0 ≤ x < : Sum should be 0, thus, T = 0
2. a ≤ x ≤ : Sum should be v*x-v*(a-1), thus, T = v*(a-1)
3. b < x < n : Sum should be 0, thus, T = -v*b + v*(a-1)

As, we can see, knowing T solves our problem, we can use another BIT to store this additive amount from which we can get:
0 for x < a, v*(a-1) for x in [a..b], -v*b+v(a-1) for x > b.

Now we have two BITs.
To add v in range [a, b]: Update(a, v), Update(b+1, -v) in the first BIT and Update(a, v*(a-1)) and Update(b+1, -v*b) on the second BIT.
To get sum in range [0, x]: you simply do Query_BIT1(x)*x - Query_BIT2(x);
Now you know how to find range sum for [a, b]. Just find sum(b) - sum(a-1) using the formula stated above.

Pretty impressive this one! SPOJ - HORRIBLE can be solved in this approach. And thanks to Iqram Mahmud for this nice problem.

(IV) 2D BIT

How to write Update and Query methods for 2D BIT is well described in the TopCoder tutorial I've mentioned above. The only thing to notice here is how the queries and updates work. 2D BIT is basically a BIT where each element is another BIT. Adding v on (x, y) means it's effect will be found throughout the rectangle [(x, y), (W, H)], and query for (x, y) gives you the result of the rectangle [(0, 0), (x, y)], assuming the total rectangle is [(0, 0), (W, H)]. SO when you query and update on this BIT, you have to be careful about how many times you are subtracting a rectangle and adding it. Simple set union formula works here. So if you want to get the result of a specific rectangle [(x1, y1), (x2, y2)], the following steps are necessary to do so:
V = Query(x2, y2)
V -= Query(x2, y1-1)
V -= Query(x1-1, y2)
V += Query(x1-1, y1-1)

This problem is an example: SPOJ - MATSUM

This page is likely to be updated if I find and manage to solve new types of BIT problems. Please let me know if there are mistakes. This post is inspired by some random posts lying around in TopCoder forums, I just wanted to put them in one place for future reference.

SPOJ ARRAYSUB

SPOJ Problem Set (Classical) 10582. Subarrays

This was also one of the problems I was asked on my recent interview with Google. Problem is a simple one for segment tree based algorithm. The solution basically requires us to maintain a Range Maximum Query (RMQ) algorithm, and I implemented this using segment tree.

Given, there are N items and a window of size K, we have to find the maximum item in each K sized window. First, we insert the first K items in the RMQ, so the segment tree root now knows the maximum item at this stage. Now if you observe you will see, for the (k+1)th item, 1st item will be removed from the tree and (k+1)th item will be inserted. This can be done by inserting (k+1)th item at the position of 1st item. Because for (k+1)th item, 1st item is in the oldest position. And clearly, for each of the next items, we can just insert it in the current oldest position on the K sized window. so (k+1) will be inserted at index 1, (k+2) at 2, (k+3) at 3 ... (2k) at k, (2k+1) at 1, (2k+2) at 2 and so on. So all we need is to keep inserting the items in the RMQ in a circular fashion and each time taking the updated range maximum value.

So, basically the structure of the code is:

 for(i = 0; i < k; i++) insert(root, 0, k-1, item[i]); output Tree[root]; for(; i < n; i++) {     insert(root, 0, k-1, item[i % k]);     output Tree[root]; } // considering item indexes to be 0 based in code // insert is the function that inserts an item on a specific index in the RMQ tree 

So, once you write down the RMQ function insert, you are pretty much done with it. Happy coding!

SPOJ EXPEDI

SPOJ: 348. Expedition

Nice problem! The first observation is, if you want to reach the city, say, point 0, you have to ensure that every single point between the current position and city must also be reachable. Now, the task is to minimize the number of stoppages for fuel, which is at most 10000. So, we sort the fuel stations, and start from current position. For every fuel station, if we want to reach it, we must have fuel f more than or equal to the distance d. Also, using the larger capacities will always reduce the number of stations we must stop.

So, for each stoppage, starting from farthest, if we can reach this stoppage with existing fuel, we push it in a priority queue (max heap in this case) for future use. If we cannot reach a particular stoppage, then we keep popping the queue and keep adding the amounts with currently available until we are able to reach current stoppage, and then pushing this value. This strategy ensures an optimal solution to reach a particular stoppage, as the priority queue will hold maximum capacities seen so far along the path, but not used yet.

If at any time, the queue gets empty and the amount of fuel is not sufficient, then the particular stoppage cannot be reached, hence, it will be impossible to reach the city.

Happy Coding

Apriori in Java (Part 2)

(Part 1)

Apriori Algorithm:

The algorithm works as follows: first it generates all the frequent itemsets of length 1 w.r.t. the given threshold (minimum support). Then it continue to generate itemsets of lengths 2,3, ... ,n if possible. There are lots of improvements and pruning possible in the implementation.

Do we need to sort frequently? First observation is, if the items are taken in sorted order on step k = 1, all the frequent patterns generated in future will also be in sorted order if maintained properly. So this eliminates the necessity of sorting or storing itemsets in logarithmic data structures like map or set. Rather, we can store them in arraylist or vector like data structure.

How do we generate itemsets of length k+1? We generate itemsets of length k+1 by merging two itemsets of length k. If two itemsets I1 and I2 have a common prefix of length k-1, and I1[k] < I2[k], we can take I1[1 ... k-1] I1[k] I2[k] which is an itemset of length k+1. As our itemsets are sorted, and frequent itemsets generated are also sorted, this can be done in O(N*K^2). Well, if we follow the naive approach, it will take O(N*K^3), however, as we can pre-calculate the length of common prefix of consecutive items in O(N*K), later, we can use this to perform joining operation stated above and also do early termination rather than looking for the entire N items. The approach is demonstrated in source code.

What are the prunings? The most important observation on apriori algorithm is, if an itemset is not frequent, none of its superset can be frequent. Which also tells us, if an itemset has to be frequent, all of its subset must be frequent. Well, the first one is automatically checked in the algorithm. As it takes the frequent itemsets of previous step to calculate itemsets of current step. Now, how the second rule is checked? Well, we don't need to check all the subsets really, all we need is to check the subsets of length k-1 for step k, which can be easily done by performing manual hashing, or using java hashmap. This saves a lots of hassles.

 /* Author: Zobayer Hasan */ import java.util.ArrayList; import java.util.HashMap; import java.util.List;  public class Apriori extends Thread {     public static boolean debugger = false;          private final Database db;     private final List< Integer > itemset;     private final List< List< Integer > > frequent;     private double minsup;      public Apriori(String thrName, Database db, double minsup) {         super(thrName);         this.db = db;         itemset = db.getItemset();         frequent = new ArrayList< List< Integer > >();         this.minsup = minsup;     }          @Override     public void run() {         double startTime = System.currentTimeMillis();                  int k = 1, n = db.dbSize();         List< List< Integer > > Ck = new ArrayList< List< Integer > >();         List< List< Integer > > Lk = new ArrayList< List< Integer > >();         HashMap< List< Integer>, Integer > seenK = new HashMap< List< Integer >, Integer >();                  for(Integer item : itemset) {             List< Integer > temp = new ArrayList< Integer >();             temp.add(item);             Lk.add(temp);         }                  while(k <= n && !Lk.isEmpty()) {             if(debugger) {                 System.out.println("Step " + k);                 System.out.println("Lk: " + Lk);             }                          seenK.clear();             Ck.clear();             for(List< Integer > kth : Lk) {                 int count = db.scanDatabase(kth);                 if((double)count < Math.ceil(minsup * (double)n / 100.0)) continue;                 Ck.add(kth);             }                          if(debugger) {                 System.out.println("Ck: " + Ck);             }                          if(Ck.isEmpty()) break;                          for(List< Integer > freq : Ck) {                 frequent.add(freq);                 seenK.put(freq, k);             }                          int[] prefixlen = new int[Ck.size()];             prefixlen[0] = 0;             for(int i = 1; i < Ck.size(); i++) {                 prefixlen[i] = prefixLen(Ck.get(i-1), Ck.get(i));             }                          List< List< Integer > > temp = new ArrayList< List< Integer > >();             for(int i = 0; i < Ck.size(); i++) {                 for(int j = i + 1; j < Ck.size(); j++) {                     if(prefixlen[j] == k-1) {                         if(debugger) {                             System.out.println("Joining: " + i + ":" + Ck.get(i) + " + " + j + ":" + Ck.get(j) + " Prefix Length " + prefixlen[j]);                         }                         temp.add(prefixJoin(Ck.get(i), Ck.get(j)));                     }                     else break;                 }             }                          if(debugger) {                 System.out.println("Temporary: " + temp);             }              Lk.clear();             for(List< Integer > list : temp) {                 boolean candid = true;                 if(k > 1) {                     for(int i = 0; i < list.size(); i++) {                         List< Integer > prev = new ArrayList< Integer >();                         for(int j = 0; j < list.size(); j++) {                             if(i != j) prev.add(list.get(j));                         }                         if(!seenK.containsKey(prev)) {                             candid = false;                             break;                         }                     }                 }                 if(candid) {                     Lk.add(list);                 }             }                          if(debugger) {                 System.out.println("Pruned: " + Lk);             }                          k++;         }                  double endTime = System.currentTimeMillis();         System.out.println("Apriori completed in " + (endTime - startTime)/1000.0 + " seconds");     }          public void printPatterns() {         System.out.println("Frequent Itemsets");         for(List< Integer > pattern : frequent) {             System.out.println(pattern);         }         System.out.println("Total " + frequent.size() + " itemsets");     }          private int prefixLen(List< Integer > left, List< Integer > right) {         int len = 0;         for(len = 0; len < left.size() && len < right.size(); len++) {             if(left.get(len).compareTo(right.get(len)) != 0) return len;         }         return len;     }          private List< Integer > prefixJoin(List< Integer > left, List< Integer > right) {         List< Integer > ret = new ArrayList< Integer >();         for(Integer i : left) {             ret.add(i);         }         ret.add(right.get(right.size() - 1));         return ret;     } } 

This class is threaded, so it is possible to take advantages of multicore processors.

A sample test class is shown here.

 /* Author: Zobayer Hasan */ public class FIMtest {      public static void main(String[] args) {         Database db = null;         try {             db = new Database("mushroom.dat");                      } catch(Exception e) {             e.printStackTrace();         }                  System.out.println("\nStarting Apriori");                  Apriori test1 = new Apriori("test1", db, 40.0);         Apriori.debugger = true;         test1.start();         try {             test1.join();             test1.printPatterns();         } catch(Exception e) {             e.printStackTrace();         }     } } 

So, this is it, an efficient implementation of Apriori algorithm in java. It is possible that there are some lacking or mistakes in either source code or analysis. If you find any, please let me know. Here is a sample run on mushroom for 40% minimum support.

Have fun...

Apriori in Java (Part 1)

Introduction:

Apriori is a very basic and straight forward algorithm for frequent pattern mining, I will not be discussing much about the approach, as those can already be studied from different lectures/books available on net. I will basically present an implementation of mine which is an efficient implementation of the standard apriori algorithm in Java. The target input files are taken from Frequent Itemset Mining Dataset Repository, for example, the mushroom dataset. Due to the space and runtime complexity, apriori is not suitable for larger files having 50,000 records or so. It also may take huge time for very dense files.

The Database:

First we need to read the files and store them in some data structure which will be easy to access and efficient at the same time. Here. I am presenting my java source code, and then I will present an explaining analysis why this works better.

 /* Author: Zobayer Hasan */  import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue;  class Entry {     public Integer first;     public Integer second;     Entry() {}     Entry(Integer first, Integer second) {         this.first = first;         this.second = second;     } }  public class Database {     public static boolean debugger = false;          private final List< List< Integer > > transactions;     private final List< Integer > items;      public Database(String dataFileName) throws Exception {         if(debugger) {             System.out.println("Processing " + dataFileName);         }                  transactions = new ArrayList< List< Integer > >();         items = new ArrayList< Integer >();                  FileInputStream fin = new FileInputStream(dataFileName);         InputStreamReader istream = new InputStreamReader(fin);         BufferedReader stdin = new BufferedReader(istream);                  String line;                  double startTime = System.currentTimeMillis();                  while((line = stdin.readLine()) != null) {             List< Integer > transaction = new ArrayList< Integer >();             String[] temp = line.split("\\s+");                          for(String num : temp) {                 transaction.add(Integer.parseInt(num));             }                          if(transaction.isEmpty()) continue;                          Collections.sort(transaction);             transactions.add(transaction);         }                  fin.close();         istream.close();         stdin.close();                  int n = transactions.size();         int[] header = new int[n];         PriorityQueue< Entry > pQ = new PriorityQueue< Entry >(n, new Comparator< Entry >() {             public int compare(Entry item1, Entry item2) {                 if(item1.first.equals(item2.first)) {                     return item1.second.compareTo(item2.second);                 } else {                     return item1.first.compareTo(item2.first);                 }             }         });                  for(int i = 0; i < n; i++) {             header[i] = 0;             pQ.add(new Entry(transactions.get(i).get(header[i]), i));         }                  while(!pQ.isEmpty()) {             Entry peek = pQ.remove();             int val = peek.first;             int idx = peek.second;             if(items.isEmpty() || items.get(items.size()-1) < val) {                 items.add(val);             }             while(header[idx] < transactions.get(idx).size() && transactions.get(idx).get(header[idx]) <= val) {                 header[idx]++;             }             if(header[idx] < transactions.get(idx).size()) {                 pQ.add(new Entry(transactions.get(idx).get(header[idx]), idx));             }         }                  double endTime = System.currentTimeMillis();         System.out.println("Database created in " + (endTime - startTime)/1000.0 + " seconds");     }          public int scanDatabase(List< Integer > transaction) {         int count = 0;         for(List< Integer > row : transactions) {             boolean found = true;             for(Integer item : transaction) {                 int idx, stp, st = 0, en = row.size(), cnt = en - st;                 while(cnt > 0) {                     stp = cnt >> 1; idx = st + stp;                     if(row.get(idx).compareTo(item) < 0) {                         st = ++idx;                         cnt -= stp+1;                     }                     else {                         cnt = stp;                     }                 }                 if(st == row.size() || row.get(st).compareTo(item) != 0) {                     found = false;                     break;                 }             }             if(found) count++;         }         return count;     }          public List< Integer > getItemset() {         return items;     }          public int dbSize() {         return transactions.size();     }          public List< Integer > getRow(int row) {         try {             return transactions.get(row);         } catch(Exception e) {             throw e;         }     } } 

Clearly it provides some interface to access the database where the constructor must be called with a file name for example 'mushroom.dat'. The sorting on line 56 is not necessary if you know the transactions in the file will be sorted in ascending order. All the data files in this repository are already sorted, so sorting can be disabled.

Now, if we look at the constructor, what is this huge code doing actually? First it treads each transaction as a string, then parses it and inserts the transaction in a sorted list. Now, we need a list of unique elements. Well, this could be done by sorting all the records together, and then eliminating duplicates. However, this can be performed better with the help of a priority queue in O(NK log N) time, where we have n transactions, and each transaction has K records on an average. Actually this works much better than it would be in naive approach which would take O(NK log NK) because of extra sorting overhead.

Then comes the last important part, scanDatabase() method. Which basically searches each record in the database for a set of elements. It takes O(NK log K) time at most, where, we have N records, each having an average length of K. This is much better than looking in O(N*K^2) following a naive approach. Here is some improvement possible, if we know the length of transactions, we could use a bit vector in addition to each transaction. Then the query can be performed in O(NK). However, as the datasets are huge, I didn't go for it due to the necessity of using huge memory.

Part 2 contains the source code and explanation for the apriori algorithm.

SPOJ RPAR : Raining Parabolas

6906. Raining Parabolas

Problem Summery

Given an array of n items h_i ( 0≤i<n ), we have to perform an update operation for a given range [i,j] such that, h_x = (h_x + f(x))%M, ( i≤x≤j and f(x) = ax²+bx+c ). We also have to perform a query operation for a range [i,j] such that, result = (h_i + h_i+1 + h_i+2 + … + h_j)%M.

Solution Idea

Solution idea with the help of a segment tree is quite simple. First, we need to observe the types of information we need to store on each node of the tree. As we will be facing range updates, lazy propagation can be utilized, so, we can have three carry variables, namely ca, cb, cc. If we look closely to the update procedure, parts with x² are added together and parts with x are added together and there is another part which are the constants. We can resemble them namely with variables, a, b, c, i.e. a is the variable that holds the sum for x² part, b is the variable that holds the sum for x part and c is the last one that holds the constant part. Also, we can keep the pre-computed values of sum of x² and x on tree node ranges for the ease of calculation.

Now, let’s dissect the update part. Say, on node p (i to j) we already have in a:

a₁x_i² + a₂x_i+1² + a₃x_i+2² + … + a_nx_j²

Now we want to add a new parabola (a, b, c) on this range, as only x² parts will be added here, so the new value of a on this node will be:

(a₁+a)x_i² + (a₂+a)x_i+1² + (a₃+a)x_i+2² + … + (a_n+a)x_j²

So, we can easily see the extra value added with the previous in variable a:

a * (sum of x² in range [i,j])

Similarly, for x part, i.e. variable b we can show the added value is:

b * (sum of x in range [i,j])

And for the constant part, i.e. variable c we can show the added value is:

c * n where n is the size of range [i,j];

So we can perform these updates now using lazy propagation, and query is also done in the similar way, the final result for a range is simply the sum of variable a, b, c from that range. And obviously modulus operations must be handled properly.

Have fun!

SPOJ - POSTERS

138. Election Posters

Although this problem is actually a good data structure problem, which is meant to be solved by range tree, but as that would need a trick. We only have 40000 nodes so total of 80000 points, but actual range is huge (10^7) for range trees. So, we can map the points so that they span over the minimum range (i.e. compress them). Sounds pathetic, right? However, there are easier ways to solve this.

By using STL set, you can make the problem pretty simulation type. Lets consider a set which contains the ranges, but not as given in input. At any moment, the set will represent the wall at that time, i.e. only visible ranges (so they must be mutually exclusive).

Now, whenever we need to add a new range, we find the leftmost poster (or piece of poster still visible) which must fall under the current one (probably you already got it, it's called lower_bound) and the rightmost poster segment that must fall under it. All the segment between these two segments will be covered, so we remove them from set. Now, we just again insert new left fragment, new right fragment and the new range... that simple it is!

Finally, we can keep and index with each segment so that we can calculate the number of actual different segment at the end of the day :)
For more clarification, consider the sample case:

5
1 4
2 6
8 10
3 4
7 10

The states of the set are shown after each input:

1 4
first entry
{(1,4)}

2 6
{1,4) is leftmost and rightmost at the same time (according to above discussion)
So, we remove it and insert new ranges:
{(1,1),(2,6)}

8 10
no conflict
{(1,1),(2,6),(8,10)}

3 4
conflicts with (2,6) (left and right both)
{(1,1),(2,2),(3,4),(5,6),(8,10)}

7 10
conflicts with (8,10)
{(1,1),(2,2),(3,4),(5,6),(7,10)}

Finally, segments with different id:
(1,1), (2,2), (3,4), (7,10). Note, (2,2) and (5,6) should have same id.

It's good if you have understood what to do, and it's even better if you don't, cause you should solve your problems on your own :p

CSE 202 Pseudo Codes 2

Insert ans Delete operation on a Singly Linked List

Each Item on a Singly Linked List is formed with two fields, Info (which contains the data for the node) and Next (which is a pointer to the next Item). A pointer 'head' points the start of the linked list, and in case the linked list is empty, head has the value 'null'. Pseudo-codes for insertion and deletion at nth position is shown below:

Insert Procedure

Insert ( head, n, item )
    if n = 1 then
        temp := new Node;
        Info[temp] := item, Next[temp] = head;
        head = temp;
        return;
    ptr := head, pos := 1;
    repeat while pos + 1 < n and Next[ptr] != null
        ptr := Next[ptr], pos = pos + 1;
    temp := new Node;
    Info[temp] = item, Next[temp] = Next[ptr];
    Next[ptr] = temp;
    return;

Delete Procedure

Delete ( head, n )
    if head = null then return;
    if n = 1 then
        temp := head, head := Next[head];
        free temp;
        return;
    ptr := head, pos := 1;
    repeat while pos + 1 < n and Next[ptr] != null
        ptr := Next[ptr], pos := pos + 1;
    if Next[ptr] = null then return
    temp := Next[ptr], Next[ptr] = Next[temp];
    free temp;
    return;

Both of them handle all the possible cases on a singly linked list.

CSE 202 Pseudo Codes 1

Iterative Tree Traversal

There are three types of tree traversals, namely, inorder, preorder and postorder. For some strange reasons, students @CSE-DU are forced to write iterative versions of these. I am just noting it down here again.

The Node is composed of three fields, namely, Info (data for this node), Left (pointer to left child), Right (pointer to right child). The pseudo-codes are shown below

Preorder

Preorder ( Info, Left, Right, root )
    top := 1, Stack[top] := NULL, ptr := root;
    repeat while ptr != NULL
        apply process() to Info[ptr];
        if Right[ptr] != NULL then
            top := top + 1, Stack[top] = Right[ptr];
        if Left[ptr] != NULL then
            ptr = Left[ptr];
        else
            ptr = Stack[top], top := top - 1;
    exit

Inorder

Inorder ( Info, Left, Right, root )
    top := 1, Stack[top] := NULL, ptr := root;
    repeat while ptr != NULL
        top := top + 1, Stack[top] = ptr, ptr = Left[ptr];
    ptr = Stack[top], top := top - 1;
    repeat while ptr != NULL
        apply process() to Info[ptr];
        if Right[ptr] != NULL then
            ptr := Right[ptr];
            go to step 03;
        ptr := Stack[top], top := top - 1;
    exit

Postorder

Postorder ( Info, Left, Right, root )
    top := 1, Stack[top] := NULL, ptr := root;
    repeat while ptr != NULL
        top := top + 1, Stack[top] = ptr, ptr = Left[ptr];
    repeat while Stack[top] != NULL and ptr = Right[Stack[top]]
        ptr := Stack[top], top := top - 1;
        apply process() to Info[ptr];
    if Stack[top] != NULL then
        ptr := Right[Stack[top]];
        go to step 03;
    exit

Really pointless though!

SPOJ - HORRIBLE

Problem 8002. Horrible Queries

Another nice problem by Iqram Mahmud.

This is a data structure related problem and can easily be solved by segment tree / range tree. At each node of the tree, we can keep the sum of all elements that falls in the current range, i.e. children of current node, and add which is the value which must be added when we pass through this node.

So, for the update query, we just find the exact interval and add the given additional value with current sum (Node->sum += interval * value) and add (Node->add += value). Then we recursively update sum of all its ancestors (Node->sum = Left->sum + Right->sum + interval * Node->add). Similarly, we can make the second query, we just keep adding the add values of each node we pass (call it carry), then when we are in the exact range, we return current sum + interval * carry.

Be careful, indexes are 1 based and the calculation may easily overflow 32 bit integer.

Merge Sort

Introduction:

Merge-sort is based on the divide-and-conquer paradigm. The Merge-sort algorithm can be described in general terms as consisting of the following three steps:

1. Divide Step: If given array A has zero or one element, return S; it is already sorted. Otherwise, divide A into two arrays, A1 and A2, each containing about half of the elements of A.


2. Recursive Step: Recursively sort array A1 and A2.


3. Conquer Step: Combine the elements back in A by merging the sorted arrays A1 and A2 into a sorted sequence.

This diagram below shows the divide and conquer (or merging) steps stated above. We can visualize Merge-sort by means of binary tree where each node of the tree represents a recursive call and each external nodes represent individual elements of given array A. Such a tree is called Merge-sort tree. The heart of the Merge-sort algorithm is conquer step, which merge two sorted sequences into a single sorted sequence. This simple but amazing algorithm and a straight forward C++ implemented is presented below, and some cool links are added in the "Reference" section at the end of the post.

Algorithm:

Input: Array A[p...r], indices p, q, r (p ≤ q < r).
Output: Array A[p...r] in ascending order

MERGE-SORT(A, p, r):
    if p < r
        then q := (r + p) / 2
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q+1, r)
        MERGE(A, p, q, r)

MERGE(A, p, q, r):
    n1 := q - p + 1
    n2 := r - q
    create arrays L[1...N1+1] and R[1...N2+1]
    for i := 1 to N1
        do L[i] := A[p + i - 1]
    for j := 1 to N2
        do R[j] := A[q + j]
    L[N1 + 1] := INF
    R[N2 + 1] := INF
    i := 1
    j := 1
    for k := p to r
        do if L[i] <= R[j]
            then A[k] := L[i]
                i := i + 1
            else
                A[k] := R[j]
                j := j + 1

Follow this link to see a javascript demonstration that simulates the above algorithm.

Analysis:

In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists) and the closed form follows from the master theorem.

Simple proof:
The merge sort algorithm created a complete binary tree, which have d depth and at each level, a total of n elements.
So, 2^d ≈ n, which implies d ≈ lg n
Now the total numbers of operation in merge sort algorithm is:
n * 2d ≈ 2n lg n ≈ O(n lg n)

In the worst case, merge sort does an amount of comparisons equal to or slightly smaller than (n ⌈lg n⌉ - 2^{⌈lg n⌉} + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n)).

In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case. Merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case. In terms of moves, merge sort's worst case complexity is O(n log n) — the same complexity as quicksort's best case, and merge sort's best case takes about half as many iterations as the worst case. Although, depending on the machine's memory architecture, quick sort can sometimes outperform merge sort, which is a very rare case.

Recursive implementations of merge sort make 2n - 1 method calls in the worst case, compared to quicksort's n, thus merge sort has roughly twice as much recursive overhead as quicksort. However, iterative, non-recursive, implementations of merge sort, avoiding method call overhead, are not difficult to code. Merge sort's most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in.

Merge sort as described here also has an often overlooked, but practically important, best-case property. If the input is already sorted, its complexity falls to O(n). Specifically, n-1 comparisons and zero moves are performed, which is the same as for simply running through the input, checking if it is pre-sorted.

Although heap sort has the same time bounds as merge sort, it requires only T(1) auxiliary space instead of merge sort's T(n), and is often faster in practical implementations. In case in-place sorting is necessary (Merge sort can be implemented as in-place algorithm, but the performance gain is not worth the complexity of the program, however, still merge sort runs in O(n lg n) time), heap sort is a better choice.

C++ Implementation:

Call Merge_Sort(A, start, end) to sort the closed range [start, end] of the array A.

void Merge(int A[], int p, int q, int r) {
    int i, j, k, n1 = q - p + 1, n2 = r - q;
    int L[n1], R[n2];
    for(i = 0; i < n1; i++)
        L[i] = A[p + i];
    for(j = 0; j < n2; j++)
        R[j] = A[q + j + 1];
    for(k = p, i = j = 0; k <= r; k++) {
        if(j >= n2 || (i < n1 && L[i] <= R[j])) A[k] = L[i++];
        else A[k] = R[j++];
    }
}

void Merge_Sort(int A[], int p, int r) {
    if(p < r) {
        int q = (p + r) / 2;
        Merge_Sort(A, p, q);
        Merge_Sort(A, q+1, r);
        Merge(A, p, q, r);
    }
}

For implementations in other languages, this page contains the implementation of merge sort procedure in almost all the living languages of the world: http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort

Reference:

• Introduction To Algorithms (CLRS, MIT Press, 2^nd Edition): Chapter 2, Section 2.3.1 - The divide-and-conquer approach.
• http://en.wikipedia.org/wiki/Merge_sort
• http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm
• http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm

Thanks for reading.

Binary Tree -- N Nodes & H Height

The problem:

You are told that you have N unique numbers, how many different binary trees are possible with those N numbers (i.e. nodes) which has exactly H height.

Analysis:

If we look closely, it will be not that hard to figure out that, the problem actually wants to know, how many different binary trees are possible to build with N nodes, each of which has exactly H height allowing rotations. Here, two trees are different when their structures are different. For example:

           @                   @
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

Solution:

I don't know whether this problem has a mathematical solution or not, I have searched for it and found nothing... But, if the values N and H supports, this problem can be solved with a dynamic programming approach.

When we want to build a tree with N nodes and H height, we can select a node as a root, so, we can put 1 to N-2 nodes on the left subtree of height H-1 or less and N-2 to 1 nodes on the right subtree of height H-1 or less, satisfying that, at least one of the subtree has a height H-1. So, by using proper base condition, we can find the number of different trees of exactly H height from this recursive formulation, and we can express the relation as follows,

if k == 1 then exactTrees( N, D ) = ( n == 1 )
if n <= 1 then exactTrees( N, D ) = 0
for all {L, R} such that L, R > 0 and L + R = N - 1:
exactTrees( N, D ) += exactTrees( L, D - 1 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += smallerTrees( L, D - 2 ) * exactTrees( R, D - 1 )
exactTrees( N, D ) += exactTrees( L, D - 1 ) * smallerTrees( R, D - 2 )

This is pretty obvious, because, if we want to get a tree of height H from any node, either one or both of its subtrees must have a height H - 1, and if we have N nodes at any step, we need to take 1 node as root, and then if we take i nodes for left subtree, we have N - 1 - i nodes left for the right subtree.
When we calculate exact height, we need to consider that a subtree may have a smaller height, so we need to calculate smallerTrees( N, D ) separately, but actually it is a bit easier:

if n < 0 or k <= 0 then smallerTrees( N, D ) = 0
if k == 1 then smallerTrees( N, D ) = ( n == 1 )
if n <= 1 then smallerTrees( N, D ) = 1
else
for all {L, R} such that L, R > 0 and L + R = N - 1:
smallerTrees( N, D ) += smallerTrees( L, D - 1 ) * smallerTrees( R, D - 1 )

Sample program:

First one goes the recursive algorithm (with dp):

// states: nodes, height
int exact[202][101], smaller[202][101];

int smallTrees(int n, int k)
{
    if(n<0 || k<=0) return 0;
    if(k==1) return n==1;
    if(n<=1) return 1;
 
    int &ret = smaller[n][k], l, r;
    if(ret!=-1) return ret;
 
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += smallTrees(l, k-1)*smallTrees(r, k-1);
        }
    }
    return ret;
}

int exactTrees(int n, int k)
{
    if(k==1) return n==1;
    if(n<=1) return 0;

    int &ret = exact[n][k], l, r;
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=1; i<n-1; i++)
    {
        l = i, r = n-1-i;
        if(l && r)
        {
            ret += exactTrees(l, k-1)*exactTrees(r, k-1);
            ret += exactTrees(l, k-1)*smallTrees(r, k-2);
            ret += smallTrees(l, k-2)*exactTrees(r, k-1);
        }
    }
    return ret;
}

Here is the iterative version (a little complex):

// states: height, nodes
int exactTrees[101][202], smallTrees[101][202];

void solve(int n, int k)
{
    int d, i, j;
    exactTrees[1][1] = 1;
    for(d=2; d<=k; d++) // depth
    {
        for(i=1; i<=n; i+=2) // number of nodes
        {
            for(j=1; j<=i-1; j+=2) // left & right
            {
                exactTrees[d][i] += exactTrees[d-1][j]*exactTrees[d-1][i-1-j];
                exactTrees[d][i] += exactTrees[d-1][j]*smallTrees[d-2][i-1-j];
                exactTrees[d][i] += smallTrees[d-2][j]*exactTrees[d-1][i-1-j];
            }
        }
        for(i=1; i<=n; i+=2) // update smaller tree
        {
            smallTrees[d-1][i] += smallTrees[d-2][i]+exactTrees[d-1][i];
        }
    }
}

[P.S. The result of this problem grows very rapidly along with the increase of N and H, so, it may easily run out of range, normally problems like this requires the result with respect to some modulus values.]

Similar problem:

USACO Section: 2.3, Problem: Cow Pedigrees, Code: nocows.
[P.S. Links won't work for usaco, you need to reach level 2.3 if you want to see the problem yourself.]
If you find any more problem regarding this, please post it as a comment below.

Linked List in C

Linked List in C (covers insert, delete, sort, search, print)

Here it goes:

#include <stdio.h>
#include <stdlib.h>

typedef struct linked_list {
    int val;
    struct linked_list *next;
} LL;

LL *head, *tail;

void tail_insert(int v)
{
    if(head==NULL)
    {
        head = (LL *)malloc(sizeof(LL));
        head->val = v;
        head->next = NULL;
        tail = head;
    }
    else
    {
        LL *temp = (LL *)malloc(sizeof(LL));
        temp->val = v;
        temp->next = NULL;
        tail->next = temp;
        tail = tail->next;
    }
}

void head_insert(int v)
{
    if(head==NULL)
    {
        head = (LL *)malloc(sizeof(LL));
        head->val = v;
        head->next = NULL;
        tail = head;
    }
    else
    {
        LL *temp = (LL *)malloc(sizeof(LL));
        temp->val = v;
        temp->next = head;
        head = temp;
    }
}

void insert_before(int v, int n) // insert v before every n
{
    LL *curr, *temp;
    if(head!=NULL)
    {
        if(head->val==n)
        {
            temp = (LL *)malloc(sizeof(LL));
            temp->val = v;
            temp->next = head;
            head = temp;
            curr = head->next;
        }
        else curr = head;
        while(curr->next!=NULL)
        {
            if(curr->next->val==n)
            {
                temp = (LL *)malloc(sizeof(LL));
                temp->val = v;
                temp->next = curr->next;
                curr->next = temp;
                curr = curr->next;
            }
            curr = curr->next;
        }
    }
}

void insert_after(int v, int n) // insert v after every n
{
    LL *curr, *temp;
    if(head!=NULL)
    {
        curr = head;
        while(curr!=NULL)
        {
            if(curr->val==n)
            {
                temp = (LL *)malloc(sizeof(LL));
                temp->val = v;
                temp->next = curr->next;
                if(curr->next==NULL) tail = temp;
                curr->next = temp;
                curr = curr->next;
            }
            curr = curr->next;
        }
    }
}

void sort_linked_list()
{
    LL *i, *j, *k;
    int temp;
    k = tail;
    for(i=head; i!=tail; i=i->next)
    {
        for(j=head; ;j=j->next)
        {
            if(j->val > j->next->val)
            {
                temp = j->val;
                j->val = j->next->val;
                j->next->val = temp;
            }
            if(j->next==k)
            {
                k = j;
                break;
            }
        }
    }
}

void delete_all(int v) // deletes every v
{
    LL *temp, *curr = head;
    while(head!=NULL && head->val==v)
    {
        temp = head;
        head = head->next;
        free(temp);
        curr = head;
    }
    if(curr==NULL) return;
    while(curr->next!=NULL)
    {
        if(curr->next->val==v)
        {
            temp = curr->next;
            curr->next = curr->next->next;
            free(temp);
            if(curr->next==NULL) tail = curr;
        }
        else curr = curr->next;
    }
}

int search_linked_list(int v)
{
    LL *curr = head;
    int n = 0;
    while(curr!=NULL)
    {
        if(curr->val==v) return n;
        n++;
        curr = curr->next;
    }
    return -1;
}

void print_linked_list()
{
    LL *curr = head;
    while(curr!=NULL)
    {
        printf("%d ", curr->val);
        curr = curr->next;
    }
    printf("\n");
}

int main()
{
    int i, n, v;

    // insert at the end
    for(i=1; i<=5; i++)
        tail_insert(5);
    print_linked_list();

    // insert at the beginning
    for(i=1; i<=5; i++)
        head_insert(i);
    print_linked_list();

    for(i=1; i<5; i++)
    {
        scanf("%d %d", &n, &v);
        // insert v before every n
        insert_before(v, n);
        print_linked_list();
    }

    for(i=1; i<5; i++)
    {
        scanf("%d %d", &n, &v);
        // insert v after every n
        insert_after(v, n);
        print_linked_list();
    }

    // sort the list with bubble sort
    sort_linked_list();
    print_linked_list();

    for(i=0; i<5; i++)
    {
        scanf("%d", &v);
        // delete all v in the list
        delete_all(v);
        print_linked_list();
    }

    for(i=0; i<5; i++)
    {
        scanf("%d", &v);
        // see if there is v in the list
        n = search_linked_list(v);
        if(n==-1) printf("not found\n");
        else printf("found at %d\n", n);
    }
    return 0;
}

Everything is commented out, if more explanation needed, leave a comment...

Bitwise operations in C: Part 3

Bitwise Operation: Some applications

Back to Part 2

Binary number system is closely related with the powers of 2, and these special numbers always have some amazing bit-wise applications. Along with this, some general aspects will be briefly shown here.

Is a number a power of 2?
How can we check this? of course write a loop and check by repeated division of 2. But with a simple bit-wise operation, this can be done fairly easy.
We, know, the binary representation of p = 2ⁿ is a bit string which has only 1 on the n^th position (0 based indexing, right most bit is LSB). And p-1 is a binary number which has 1 on 0 to n-1 th position and all the rest more significant bits are 0. So, by AND-ing p and (p-1) will result 0 in this case:

p   = ....01000 &rArr 8
p-1 = ....00111 &rArr 7
-----------------------
AND = ....00000 &rArr 0

No other number will show this result, like AND-ing 6 and 5 will never be 0.

Swap two integers without using any third variable:
Well, as no 3^rd variable is allowed, we must find another way to preserve the values, how about we some how combine two values on one variable and the other will then be used as the temporary one...

Let A = 5 and B = 6
A = A ^ B = 3 /* 101 XOR 110 = 011 */
B = A ^ B = 5 /* 011 XOR 110 = 101 */
A = A ^ B = 6 /* 011 XOR 101 = 110 */
So, A = 6 and B = 5

Cool!!!

Divisibility by power of 2
Use of % operation is very slow, also the * and / operations. But in case of the second operand is a power of 2, we can take the advantage of bit-wise operations.
Here are some equivalent operations:

Here, P is in the form 2^X and N is any integer (typically unsigned)

N % P = N & (P-1)
N / P = N >> X
N * P = N << X

A lot faster and smarter...
About the % operation : the above is possible only when P is a power of 2

Masking operation
What is a mask? Its a way that is used to reshape something. In bit-wise operation, a masking operation means to reshape the bit pattern of some variable with the help of a bit-mask using some sort of bit-wise operation. Some examples following here (we won't talk about actual values here, rather we'll look through the binary representation and using only 16 bits for our ease of understanding):

Grab a portion of bit string from an integer variable.
Suppose A has some value like A = ... 0100 1101 1010 1001
We need the number that is formed by the bit-string of A from 3rd to 9th position.

[Lets assume, we have positions 0 to 15, and 0th position is the LSB]
Obviously the result is B = ... 01 1010 1; [we simply cut the 3rd to 9th position of A by hand]. But how to do this in programming.

Lets assume we have a mask X which contains necessary bit pattern that will help us to cut the desired portion. So, lets have a look how this has to be done:

A = 0100 1101 1010 1001
X = 0000 0011 1111 1000

See, we have X which have 1s in 3rd to 9th position and all the other thing is 0. We know, AND-ing any bit b with 1 leaves b unchanged.

So, X = X & A
Now, we have,
X = 0000 0001 1010 1000

So, now we've cut the desired portion, but this is exactly not what we wanted. We have 3 extra 0s in the tail, So just right-shift 3 times:

X = X >> 3 = 0000 0000 0011 0101; // hurrah we've got it.

Well, I got everything fine, but how to get such a weird X?

int x = 0, i, p=9-3+1; // p is the number of 1s we need
for(i=0; i<p, i++)
    x = (x << 1) | 1;
x = x << 3; // as we need to align its lsb with the 3rd bit of A

Execution:
X = 0000 0000 0000 0000 (initially X=0)
X = 0000 0000 0000 0001 (begin loop i=0)
X = 0000 0000 0000 0011 (i=1)
X = 0000 0000 0000 0111 (i=2)
X = 0000 0000 0000 1111 (i=3)
X = 0000 0000 0001 1111 (i=4)
X = 0000 0000 0011 1111 (i=5)
X = 0000 0000 0111 1111 (i=6 loop ends)
X = 0000 0011 1111 1000 (X=X<<3)

So, following the same approach, we may invert some portion of a bit-string (using XOR), make all bits 1 (using OR), make all bits in the portion 0 (using AND) etc etc very easily...

So, these are some tasks for the learner,
You have an integer A with some value, print the integers which have:
1. same bit pattern as A except it has all bits 0 within 4th to 23rd position.
2. same bit pattern as A except it has all bits 1 within 9th and 30th position.
3. same bit pattern as A except it has all bits inverted within positions 2nd and 20th.
4. totally inverted bit pattern.

Subset pattern:
Binary numbers can be used to represent subset ordering and all possible combination of taking n items.
For example, a problem might ask you to determine the n'th value of a series when sorted, where each term is some power of 5 or sum of some powers of 5.
It is clear that, each bit in a binary representation correspondence to a specific power of two in increasing order from right to left. And if we write down the consecutive binary values, we get some sorted integers. Like:

3 2 1 0 ⇒ power of 2
0 0 0 0 = 0 // took no one
0 0 0 1 = 1 // took power 0
0 0 1 0 = 2 // took power 1
0 0 1 1 = 3 // took power 1 and 0
0 1 0 0 = 4 // took power 2
0 1 0 1 = 5 // took power 2 and 0
0 1 1 0 = 6 // took power 2 and 1
0 1 1 1 = 7 // took power 2, 1 and 0
...........
...........
...........

So, what we do here is, take a power of 2 or take the sum of some powers of 2 to get a sorted sequence. Well, if this work for 2.. this will also work for 5 in the same way... Instead of taking the power of 2, we'll take the power of 5.
So the n'th term will be the sum of those powers of 5 on which position n's binary representation has 1. So the 10th term is 5³ + 5¹; As, 10₁₀ = 1010₂, it has 1 in 3rd and 1st position.

Worse than worthless
A bitwise GCD algorithm (wikipedia), translated into C from its assembly routine.

Sieve of Eratosthenes (SOE)
This is the idea of compressing the space for flag variables. For example, when we generate prime table using SOE, we normally use 1 int / bool for 1 flag, so if we need to store 10⁸ flags, we barely need 100MB of memory which is surely not available... and using such amount of memory will slow down the process. So instead of using 1 int for 1 flag, why don't we use 1 int for 32 flags on each of its 32 bits? This will reduce the memory by 1/32 which is less than 4MB :D

#define MAX 100000000
#define LMT 10000

unsigned flag[MAX>>6];

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))

void sieve() {
    unsigned i, j, k;
    for(i=3; i<LMT; i+=2)
        if(!ifc(i))
            for(j=i*i, k=i<<1; j<MAX; j+=k)
                isc(j);
}

ifc(x) checks if x is a composite (if correspondent bit is 1)
isc(x) sets x as a composite (by making correspondent bit 1)

Other than this famous bit-wise sieve, we could use the technique in many places, to reduce memory for flagging.

Keep going on...

Bitwise operations in C: Part 2

Bitwise Operation: LEFT SHIFT and RIGHT SHIFT

Back to Part 1

<< (SHIFT LEFT) operator

This operator also depends highly on the length of the bit-string. Actually this operator only "shift" or moves all the bits to the left. This operator is mostly used if we want to multiply a number by 2, or, some powers of 2.
Example :

int a = 4978;
printf("%d\n", a<<1);

The output will be 9956. Do you see the relation between 4978 and 9956?

YES, 4978 * 2 = 9956. For more detailed explanation, we will see it in binary:

0001001101110010 ⇒ a = 4978(16 bit)
---------------- << 1 (SHIFT LEFT the bits by one bit)
0010011011100100 ⇒ 9956

Just move left all the bits by one. The left most bit is lost! and at the rightmost, a zero is added. Second example: count 4978 << 8 (count 4978 shifted left by 8 bits)
Answer:

0001001101110010 ⇒ 4978 (16 bit representation)
---------------- << 8 (SHIFT LEFT the bits by 8 bit)
0111001000000000 ⇒ 29184

So, using 16 bit compiler, 4978 << 8 is 29184, which is incorrect! Some of the left most bits are lost...It will not, however, if we use 32 bits data type.

00000000000000000001001101110010 ⇒ 4978(32 bit)
-------------------------------- << 8 (SHIFT LEFT the bits by 8 bit)
00000000000100110111001000000000 ⇒ 1274368

I've told you before that, this operator depends the length of bit-string. Don't be surprised if you got the output of 4978 << 8 is 1274368. (this is actually correct!) As we see, no bits are lost after shifting the bits left by 8 bits if we use a 32 bit data type.
Note that you don't have to have an int to store the value! In C, you can just print like this :

printf("%d", 4978 << 8);

The output will be 29184 for 16 bit compiler as Turbo C (16 bits; some bits will be lost)
The output will be 1274368 for 32 bit compiler as GNU C (32 bits; all bits are reserved since it has bigger capacity)
Now you know why shifting left 1 bit is the same as multiply the number by 2 right?
And shifting left 8 bits is exactly the same as multiplying the number by 2⁸.

4978 << 8 = 1274368 (in 32 bits compiler)
4978 * 2⁸ = 4978 * 256 = 1274368. (exactly the same)

BTW, we need to be careful when using signed data type, as the left most bit is the sign bit. So, while left shifting, if you push a 1 at that position, the number will be negative.

>> (SHIFT RIGHT) operator

Not much different with << (SHIFT LEFT) operator. It just shifts all the bits to the right instead of shifting to the left. This operator is mostly used if we want to divide a number by 2, or, some powers of 2.

Example :

count 4978 >> 8

int a = 4978;
printf("%d\n", a>>8);

4978 >> 8 = 19 (in 16 bits compiler or 32 bits compiler, the >> has no difference, because >> will discard the right most bit, and increased capacity on the left side doesn't help here anyhow)

Detailed explanation :

0001001101110010 ⇒ 4978(16 bit)
---------------- >> 8 (SHIFT RIGHT the bits by 8 bit)
0000000000010011 ⇒ 19

and

00000000000000000001001101110010 ⇒ 4978(32 bit)
-------------------------------- >> 8 (SHIFT RIGHT the bits by 8 bit)
00000000000000000000000000010011 ⇒ 19

If you notice:

4978 >> 8 = 19 (in 32 bits compiler)

4978 / 2⁸ = 4978 / 256 = 19. (They both the same, but using bit-wise operator >> (SHIFT RIGHT) is a LOT faster!)

The RIGHT SHIFT operator is machine dependent, it may work differently on different machines for signed data types. >> empties the left most bit and that is filled either by a 0 or by a 1, depending on the machine.
Filled by a 1 (RIGHT SHIFT ARITHMETIC)
Filled by a 0 (RIGHT SHIFT LOGICAL)
Example:

signed char x = -75 /* 1011 0101 */
signed char y = x >> 2

/* result of logical right shift */
y = 45  /* 0010 1101 */

/* result of arithmetic right shift */
y = -19 /* 1110 1101 */

So this behavior of RIGHT SHIFT leads to a non-portability of a program.

A few more words

The two shift operators are generally used with unsigned data type to avoid ambiguity.
Result of Shifting Right or Left by a value which is larger than the size of the variable is undefined.
Result of shifting Right or Left by a negative value is also undefined.

Order precedence of the basic operators is:

NOT ( ~ ) highest
AND ( & )
XOR ( ^ )
 OR ( | ) lowest

Some basic operations:

Let X is a single bit, then we can write the following: 
X & 1 =  X; X & 0 =  0
X | 1 =  1; X | 0 =  X
X ^ 1 = ~X; X ^ 0 =  X

Bit-wise operations are quite fast and easy to use, sometimes they reduce the running time of your program heavily, so use bit-wise operations when-ever you can. But if you look on the software developing aspect, they are not much reliable because, they aren't applicable with any type of data, especially floating points, and signed types. Also, not many people understand them.

But, still, who cares? I want to give some scary looks to my code... lol :D
Hopefully, on the next post, we'll see some simple ideas which will implement some bit-wise operations...

Continue to Part 3

Bitwise operations in C: Part 1

Bitwise Operation: AND, OR, XOR, NOT

In computer, all the numbers and all the other data are stored using 2 based number system or in binary format. So, what we use to say a '5' in decimal (do we use decimal only because we have 10 figures? who knows...), a computer will represent it as '101', in fact, everything is represented as some sequence of 0s and 1s. We call this sequence a bit-string.

Bit-wise operations means working with the individual bits other than using the larger or default data types, like integers, floating points, characters, or some other complex types. C/C++ provides a programmer an efficient way to manipulate individual bits of a data with the help of commonly known logical operators like AND(&), OR(|), NOT(~), XOR(^), LEFT SHIFT(<<) and RIGHT SHIFT(>>) operators.

To be fluent with bit-wise operations, one needs to have a clear concepts about how data is stored in computer and what is a binary number system.

From a programming contest aspect, we'll explore bit-wise operations for only integer types (int in C/C++) and as this is almost 2010, we'll consider int as a 32 bit data type. But for the ease of writing, sometimes only the lowest 16 bits will be shown. The above operators works on bit-by-bit, i.e. during bit-wise operation, we have to align right the bits! (just like addition, multiplication,...) The shorter bits always have leading 0s at the front. And another important thing... we do not need to convert the integers to the binary form ourselves, when we use the operators, they will be automatically evaluated and the following examples shows the underlying activities... :P

& (AND) operator

This table will clearly explains the bit-wise operator & (AND):

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

Example:
What is the value of 24052 & 4978 ?
To solve this, we have to consider the operations in base 2.
So, we imagine both numbers in base 2 and align right the bits, as shown below using 16 bits. Now, AND the numbers : (shorter bits can have leading zeros at the front):

101110111110100 ⇒ 24052
001001101110010 ⇒ 4978
--------------- &
001000101110000 ⇒ 4464

Each bit-column is AND-ed using the AND table above.

| (OR) operator

This table summarizes the OR operations :

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

Now, using the same example above, let's do it using | (OR) operator :

101110111110100 ⇒ 24052
001001101110010 ⇒ 4978
--------------- |
101111111110110 ⇒ 24566

Each bit-column is OR-ed using the OR table above.

^ (XOR) operator

This table summarize the XOR operations :

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

Now, using the same example above, let's do using ^ (XOR) operator :

101110111110100 ⇒ 24052
001001101110010 ⇒ 4978
--------------- ^
100111010000110 ⇒ 20102

Easy, isn't it?

~ (NOT) operator

This operator is different from the above operators. This operator is called unary operator, since it only needs one operand. The operators &, |, ^ are binary operators, since it takes 2 operands/number to be operated.

This ~ (NOT) operator, inverts all the bits in a variable. That is, changes all zeros into ones, and changes all ones into zeros.
Remember! that the result of this ~ (NOT) operation highly depends on the length of the bit-string.

Example:

int a = 10;
printf("%d\n", ~a);

Surprisingly, the output is -11. But actually this is normal as most of the cases computer represents negative numbers in the 2's complement form. Look at the operation shown below using 16 bits:

0000000000001010 ⇒ a(16 bits)
---------------- ~
1111111111110101 ⇒ -11

This is correct! Because computer stores -11 as 1111111111110101 in binary! (in the 2's complement form). Even if we use 32 bits representation, it is still the 2's complement form of -11;

-11(10) = 11111111111111111111111111110101(2)

Anyway, if we do the same operation for unsigned int:

unsigned int a = 10;
printf("%u\n", ~a);

Hah ha, don't be surprised if you get the output of the unsigned value of -11 is 4294967285.

If you use 32 bits, you actually will get -11 as 11111111111111111111111111110101 in signed binary representation:

00000000000000000000000000001010 ⇒ 10 (32 bits)
-------------------------------- ~
11111111111111111111111111110101 ⇒ -11 (for signed) and -> 4294967285 (for unsigned)

In the unsigned data type, all the bits are considered to be the part of the magnitude, there's no bit position reserved for sign bits.

Continue to Part 2