Sachverhalt: A. Das Obergericht des Kantons Zürich verurteilte X._ mit Urteil vom 11. Oktober 2007 in zweiter Instanz zu einer teilbedingten Freiheitsstrafe von 30 Monaten. Den unbedingt zu vollziehenden Teil der Freiheitsstrafe setzte es auf 15 Monate fest, abzüglich 39 Tage Untersuchungshaft. Daraufhin versetzte der Justizvollzug des Kantons Zürich X._ mit Vollzugsauftrag vom 31. Dezember 2007 rückwirkend per 11. Oktober 2007 in den ordentlichen Strafvollzug. B. X._ wurde in anderer Angelegenheit am 25. Juli 2007 in Untersuchungshaft genommen und mit Urteil des Bezirksgerichts Zürich vom 19. Juni 2008 zu 4 Jahren Freiheitsstrafe verurteilt, als Zusatzstrafe unter anderem zum Urteil des Obergerichts des Kantons Zürich vom 11. Oktober 2007. Dagegen erklärte X._ die Berufung. Das Obergericht des Kantons Zürich sprach ihn mit Urteil vom 7. April 2009 vom Vorwurf der mehrfachen Vergewaltigung frei. In Ziffer 5 des Urteilsdispositivs erkannte es ihm eine Genugtuung von Fr. 25'000.-- zu. C. Mit Beschwerde in Strafsachen bzw. mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt X._, Ziffer 5 des Urteils des Obergerichts des Kantons Zürich vom 7. April 2009 sei aufzuheben. Die Untersuchungshaft von 78 Tagen und der vorzeitige Strafvollzug von 293 Tagen seien auf die mit Urteil des Obergerichts des Kantons Zürich vom 11. Oktober 2007 zu vollziehende Freiheitsstrafe von 15 Monaten anzurechnen. Er sei mit sofortiger Wirkung aus dem ordentlichen Strafvollzug zu entlassen und ihm sei für die Überhaft eine Genugtuung von mindestens Fr. 30'000.-- aus der Staatskasse zu bezahlen. Zudem ersucht X._ um unentgeltliche Prozessführung und Verbeiständung. D. Die Oberstaatsanwaltschaft des Kantons Zürich und das Obergericht des Kantons Zürich verzichten beide auf Vernehmlassung. 