The traditional majority-logic decoding (MLgD) based algorithms suffer error-floors for decoding non-binary LDPC codes with small column weights. This paper presents a bit-reliability based MLgD (BRB-MLgD) algorithm with low error-floors for non-binary LDPC codes. The proposed algorithm is carried out based on the binary representations of non-binary symbols. The reliability update along each edge of the Tanner graph of a non-binary LDPC code is in terms of bits rather than symbols. Thus, its computational complexity and memory consumption are less than those of the existing MLgD based algorithms. Simulation results indicate that the proposed algorithm can significantly reduce error-floors with small performance degradation in the waterfall region.