Faits : A. Par jugement du 6 août 2015, le Tribunal de police de Genève a condamné X._ pour séjour illégal (art. 115 al. 1 let. b de la loi fédérale du 16 décembre 2005 sur les étrangers, LEtr; RS 142.20) à une peine privative de liberté de 45 jours, sous déduction d'un jour de détention avant jugement, et a renoncé à révoquer la libération conditionnelle octroyée le 21 juillet 2014. B. Par arrêt du 15 décembre 2015, la Chambre pénale d'appel et de révision de la Cour de justice genevoise a rejeté l'appel formé par X._. Cette condamnation repose sur les faits suivants: Du 22 juillet 2014 au 19 avril 2015, X._, ressortissant algérien, a séjourné sur le territoire suisse, sans autorisation, dépourvu de papiers d'identité et de moyens d'existence, alors qu'il faisait l'objet d'une interdiction d'entrée en Suisse valable du 6 août 2013 au 13 novembre 2017, notifiée le 13 avril 2014. Une procédure de renvoi a été introduite à son encontre le 1er mars 2011, et il fait l'objet d'une décision de renvoi exécutoire. Le recourant a déclaré avoir quitté l'Algérie en 2007 et loger en Suisse depuis le mois de mars 2008 dans un abri de protection civile et, occasionnellement, chez A._. Il a expliqué qu'il comptait épouser sa compagne, qui vivait en Espagne et qu'il connaissait depuis dix ans, le projet du couple étant de s'installer dans ce pays ou au Portugal. C. Contre ce dernier arrêt, X._ dépose un recours en matière pénale devant le Tribunal fédéral. Il conclut, principalement, à la réforme de l'arrêt attaqué en ce sens qu'il est acquitté du chef de l'infraction à l'art. 115 al. 1 let. b LEtr et, à titre subsidiaire, à l'annulation de l'arrêt attaqué et au renvoi de la cause à la cour cantonale pour nouvelle décision. En outre, il sollicite l'assistance judiciaire. Invités à se déterminer, la cour cantonale y a renoncé, alors que le Ministère public genevois a déposé des déterminations; celles-ci ont été communiquées au recourant.