It is important to understand how bipedal walkers balance and walk effectively on granular materials, such as sand and loose dirt, etc. This paper first presents a computational approach to obtain the motion and energy analysis of bipedal walkers on granular terrains and then discusses an optimization method for the robot foot-shape contour design for energy efficiently walking. We first present the foot-terrain interaction characteristics of the intrusion process using the resistive force theory that provides comprehensive force laws. Using human gait profiles, we compute and compare the ground reaction forces and the external work for walking gaits with various foot shapes on granular terrains. A multi-objective optimization problem is finally formulated for the foot contour design considering energy saving and walking efficiency. It is interesting to find out a non-convex foot shape gives the best performance in term of energy and locomotion efficiency on hard granular terrains. The presented work provides an enabling tool to further understand and design efficient and effective bipedal walkers on granular terrains.