Multiplierless FIR filter optimization has been extensively studied in the past decades to minimize the number of adders. A more accurate measurement of the implementation complexity is the number of full adders counted at bit-level. However, the high computational complexity of the optimization at bit-level hinders the technique from practical applications. In this paper, the sparse filter technique is exploited and makes the search space at bit-level significantly reduced. Thus, the bit-level optimization of multiplierless FIR filters for the first time becomes possible. When the sparse filter technique is employed for the multiplierless filter design, the sparsity of the filter is properly controlled so that the feasibility of the bit-level optimization in discrete space is maintained. Thereafter, in the reduced search space, a tree search algorithm is formulated at bit-level, and techniques to estimate the bit level hardware cost and to accelerate the search are presented. Design examples show that the proposed bit-level optimization method generates designs with lower hardware cost and power consumption than that of the best word-level optimization methods, while the design time is still at an acceptable level. The average power savings to 3 recent published techniques are 13.6%, 8.0% and 26.1%, respectively.