In one embodiment of an e-fuse programming/re-programming circuit, the e-fuse has two short high atomic diffusion resistance conductor layers positioned on opposite sides and at a same end of a long low atomic diffusion resistance conductor layer. A voltage source is used to vary the polarity and, optionally, the magnitude of voltage applied to the terminals in order to control bi-directional flow of electrons within the long conductor layer and, thereby formation of opens and/or shorts at the long conductor layer-short conductor layer interfaces. The formation of such opens and/or shorts can be used to achieve different programming states. Other circuit structure embodiments incorporate e-fuses with additional conductor layers and additional terminals so as to allow for even more programming states. Also disclosed are embodiments of associated e-fuse programming and re-programming methods.