Counting Ones Without Broadword Operations

Abstract

A lower time bound $\Omega (\min (\nu (x),n-\nu (x))$ for counting the number of ones in a binary input word $x$ of length $n$ is presented, where $\nu (x)$ is the number of ones. The operations available are increment, decrement, bit-wise logical operations, and assignment. The only constant available is zero. An almost matching upper bound is also obtained.

References in corpus (1)

• A SWAR Approach to Counting Ones