We consider the transmission of data encoded into binary messages, with the goal of minimizing the Hamming distance, i.e., the number of bit-flips, between consecutive messages. This problem is relevant for enhancing the longevity of Non-Volatile Memories and reducing transition-induced energy consumption in data buses. Known as Write-Efficient Memory coding in the literature, this challenge has traditionally been addressed using optimal but complex schemes. In low-power computer systems the same topic is known as bus encoding. In this paper, we derive closed-form expressions to evaluate the average number of bit-flips for practical, sub-optimal encoding schemes, and propose two new schemes assisted by predefined random codebooks. We demonstrate that low-complexity solutions achieve performance very close to the optimal schemes, making them attractive for implementation in energy-sensitive and memory-critical applications. For instance, by adding 8 extra bits to 64-bits data, sub-optimal schemes can achieve a bit-flip reduction (related to energy saving) of approximately 24.7%, compared to the 26.4% reduction offered by the significantly more complex optimal scheme.