Genetic algorithms (GAs) are widely used in the parameter training of Neural Network (NN). In this paper, we investigate GAs based on our proposed novel genetic representation to train the parameters of NN. A splicing/decomposable (S/D) binary encoding is designed based on some theoretical guidance and existing recommendations. Our theoretical and empirical investigations reveal that the S/D binary representation is more proper than other existing binary encodings for GAs’ searching. Moreover, a new genotypic distance on the S/D binary space is equivalent to the Euclidean distance on the real-valued space during GAs convergence. Therefore, GAs can reliably and predictably solve problems of bounded complexity and the methods depended on the Euclidean distance for solving different kinds of optimization problems can be directly used on the S/D binary space. This investigation demonstrates that GAs based our proposed binary representation can efficiently and effectively train the parameters of NN.