Point set registration is the technology used to estimate the spatial transformation between two LiDAR scans, which is challenging in the presence of outlier correspondences and noise. Our focus is on 4 degrees of freedom (DOF) point set registration, in which 1DOF rotation and 3DOF translation need to be estimated. It is commonly found in practical scenarios, such as arbitrarily mobile robots equipped with an inertial measurement unit (IMU), terrestrial LiDAR scanners, or planar moving vehicles in urban environments. Recently, many solutions have leveraged branch and bound (BnB) in global and deterministic approaches to solve the registration problem with performance guarantees. However, BnB-based methods are usually time-consuming since their convergence speed is exponential to the dimensionality of the solution domain, and existing methods estimate these 4DOF simultaneously. Our key idea is to speed up BnB-based methods by decoupling the joint pose into separate translation and rotation with the aid of known gravity directions. This effectively reduces the search domain to 3DOF+1DOF, thereby enhancing algorithm efficiency. Specifically, we propose a novel BnB-based consensus maximization method for a fast 3DOF translation search and derive the specific lower and upper bound functions. We then propose an efficient global voting method for estimating the rotation with 1DOF. To demonstrate the superiority of our proposed method, we conduct extensive experiments on both synthetic and real-world datasets. The experimental results show that (1) our proposed method is more robust against outliers and noise than several existing methods and far faster than the existing BnB-based 4DOF method by almost an order of magnitude, (2) our proposed method is robust against the biases in gravity directions, such that the general error of the IMU is acceptable, and (3) thanks to its significant robustness, our proposed method can solve the challenging problem of simultaneous pose and correspondence registration (SPCR). Moreover, the proposed approach is also more robust and accurate than several SPCR benchmark methods. Code is available at https://github.com/Xinyi-tum/Fast-and-Deterministic-Registration.