All-optical ultra-fast and reconfigurable logic gates have been implemented by exploiting simple and low-cost schemes based on nonlinear optical loop mirrors (NOLM). Conventional NOLM-based all-optical logic gates utilize the self-phase modulation effects or cross-phase modulation effects. Thus, types of logic gates that can be achieved are limited by the low degree of freedom in reconstruction of the transmission function. Here, an improved scheme of NOLM-based all-optical logic gate is proposed by exploiting the nonlinear polarization rotation in the NOLM. The evolution of the polarized state of light is analyzed as well as the effect of the polarization of the input light and the polarization controller in NOLM. Theoretical analysis and numerical simulation results show that all the basic logic gates can be realized using a single NOLM structure, only by adjusting the polarization controller. Because it is more free to rebuild the transmission function when the nonlinear polarization rotation effect is taken into account. We demonstrate the feasibility of the scheme experimentally by realizing all-optical logic gates of “NOT”, “AND”, “OR”, “NOR”, “XOR”, “NXOR” at 40 Gb/s operation.