Bitwise Operations under RAMBO
Andrej Brodnik, Johan Karlsson · Epubl LTU · 2006
In this paper we study the problem of computing w-bit bitwise operations using only O(1) memory probes. We show that under the RAM model there exists a Omega(2^w) space lower bound while under the RAMBO model this space bound goes down to O(w) bits. We present algorithms that use four different RAMBO memory topologies to perform bitwise boolean operations and shift operations.