The elements hydrogen, carbon, nitrogen and oxygen are assumed to comprise the bulk of the interiors of the ice giant planets Uranus, Neptune, and sub-Neptune exoplanets. The details of their interior structures have remained largely unknown because it is not understood how the compounds H2O, NH3 and CH4 behave and react once they have been accreted and exposed to high pressures and temperatures. Here we study thirteen H-C-N-O compounds with ab initio computer simulations and demonstrate that they assume a superionic state at elevated temperatures, in which the hydrogen ions diffuse through a stable sublattice that is provided by the larger nuclei. At yet higher temperatures, four of the thirteen compounds undergo a second transition to a novel doubly superionic state, in which the smallest of the heavy nuclei diffuse simultaneously with hydrogen ions through the remaining sublattice. Since this transition and the melting transition at yet higher temperatures are both of first order, this may introduce additional layers in the mantle of ice giant planets and alter their convective patterns.