2016 001 Add popCount to WORD signature

John Reppy edited this page May 10, 2016 · 3 revisions

Proposal 2016-001

Add popCount to WORD signature

Author: John Reppy
Last revised: May 9, 2016
Status: proposed
Discussion: issue #13


Synopsis

signature WORD

This proposal adds the population-count operation to the WORD signature.

Interface

val popCount : word -> int

Description

  • popCount w

returns the number of `1` bits in the word `w`.

Rationale

This operation is useful for computing the Hamming distance between two words and for implementing various data structures (e.g., the Hash array mapped trie). There are two reasons for making it part of the Basis Library:

  1. the straight-line implementation depends on the size of the word type.

  2. some architectures support the operation in hardware, which can be even faster than the the straight-line code.