As an essential technique for data privacy protection, reversible data hiding in encrypted images (RDHEI) methods have drawn intensive research interest in recent years. In response to the increasing demand for protecting data privacy, novel methods that perform RDHEI are continually being developed. We propose two effective multi-MSB (most significant bit) replacement-based approaches that yield comparably high data embedding capacity, improve overall processing speed, and enhance reconstructed images' quality. Our first method, Efficient Multi-MSB Replacement-RDHEI (EMR-RDHEI), obtains higher data embedding rates (DERs, also known as payloads) and better visual quality in reconstructed images when compared with many other state-of-the-art methods. Our second method, Lossless Multi-MSB Replacement-RDHEI (LMR-RDHEI), can losslessly recover original images after an information embedding process is performed. To verify the accuracy of our methods, we compared them with other recent RDHEI techniques and performed extensive experiments using the widely accepted BOWS-2 dataset. Our experimental results showed that the DER of our EMR-RDHEI method ranged from 1.2087 bit per pixel (bpp) to 6.2682 bpp with an average of 3.2457 bpp. For the LMR-RDHEI method, the average DER was 2.5325 bpp, with a range between 0.2129 bpp and 6.0168 bpp. Our results demonstrate that these methods outperform many other state-of-the-art RDHEI algorithms. Additionally, the multi-MSB replacement-based approach provides a clean design and efficient vectorized implementation.