Variable Block Size Motion Estimation (VBSME) is one of the most important features of state-of-the-art video encoders. In the H.264/AVC encoder, the computational complexity of integer motion estimation is about 75%. Therefore, reducing this complexity is one of the key points to provide low power video encoding. In this paper, a reconfigurable bit plane matching based VBSME method and a runtime reconfigurable hardware architecture are proposed to allow low-power consumer electronic devices to make a trade-off between power requirements and motion estimation (ME) accuracy. The proposed ME method is the only low complexity ME algorithm proposed in the literature so far that can provide compatible ME accuracy for lower block sizes compared to the sum of absolute difference (SAD) criterion. A new data path for the computation of the matching criterion in the proposed hardware architecture which has a fully arithmetic structure is proposed to improve the previously utilized LUT based architectures by having a fully arithmetic structure(1).