For smart GNSS devices with small power capacity and limited computation capability, consecutively tracking the GNSS signal can short their operation hours. To deal with this problem, we propose a computationally efficient ultra-tight integration of GNSS and INS in this paper. Compared to the traditional ultra-tight integration, the GNSS signal tracking in the presented integration scheme is non-consecutive. The GNSS signal code phase of each used satellite is predicted according to the INS solution, and the code phase error obtained by a non-coherent code discriminator is directly applied as the measurement of the integration filter to estimate and correct INS solution error. The GNSS signal tracking interval can be adaptively adjusted according to the real-time GNSS code tracking error. To validate the presented scheme, a vehicle-based experiment based on a software defined receiver is performed, in which GPS L1 C/A and Galileo E1 signals are non-consecutively tracked and ultra-tightly coupled with MEMS based INS. The experiment results show that the presented integration is able to maintain the lock of GNSS code signal and can significantly reduce system’s computational burden with a little loss of navigation accuracy.