arXiv
Open Access
2011
A SWAR Approach to Counting Ones
Holger Petersen
Abstrak
We investigate the complexity of algorithms counting ones in different sets of operations. With addition and logical operations (but no shift) $O(\log^2(n))$ steps suffice to count ones. Parity can be computed with complexity $O(\log(n))$, which is the same bound as for methods using shift-operations. If multiplication is available, a solution of time complexity $O(\log^*(n))$ is possible improving the known bound $O(\log\log(n))$.
Topik & Kata Kunci
Penulis (1)
H
Holger Petersen
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2011
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓