In this paper, a new bit allocation algorithm, called EBFOS (Enhanced BFOS), is proposed for the MPEG-4 Advanced Audio Coding (AAC) scheme. The notion of "bit-use efficiency" is suggested and the basic idea behind our approach is "give bits to the band with the maximum NMR gain per bit" or "retrieve bits from the band with the maximum bits per NMR loss", which is similar to the basic concept of the generalized BFOS (Breiman, Friedman, Olshen, and Stone) algorithm. However, the inter-band dependency of coding process in AAC is also taken into consideration in our approach. Simulation results show that the performance of the EBFOS scheme is significantly better than that of the MPEG-4 AAC Verification Model and is close to that of the trellis-based scheme, which achieves the minimum of a predefined NMR cost function. Also proposed in this paper is a fast version of our algorithm to reduce its computational complexity.