A Non-Oblivious Reduction of Counting Ones to Multiplication

2015/06/10 by Petersen, Holger
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1506.03473

Abstract

An algorithm counting the number of ones in a binary word is presented running in time O(loglog b) where b is the number of ones. The operations available include bit-wise logical operations and multiplication.

Related

• Counting Ones Without Broadword Operations
• A SWAR Approach to Counting Ones
• Counting Clean Words According to the Number of Their Clean Neighbors
• Counting Results in Weak Formalisms
• Counting Terms in the Binary Lambda Calculus