We propose a new, low-complexity solution to realize multi-input-bit gates acting on exponentially large superpositions in noise-based logic processors. Two examples are shown, the NOT gate and the CNOT gate. The operations can be executed and repeated with polynomial time and hardware complexity. The lack of a solution for this problem had been one of the major issues prohibiting the efficient realization of Shors algorithm by Instantaneous Noise-Based Logic, which runs on a classical Turing computer with a true random number generator. With the method described in this paper, we are one step closer to this goal.