Fast additions on masked integers

Michael D. Adams and David S. Wise

Status: Published


Suppose the bits of a computer word are partitioned into d disjoint sets, each of which is used to represent one of a d-tuple of cartesian indices into d-dimensional space. Then, regardless of the partition, simple group operations and comparisons can be implemented for each index on a conventional processor in a sequence of two or three register operations.

These indexings allow any blocked algorithm from linear algebra to use some non-standard matrix orderings that increase locality and enhance their performance. The underlying implementations were designed for alternating bit postitions to index Morton-ordered matrices, but they apply, as well, to any bit partitioning. A hybrid ordering of the elements of a matrix becomes possible, therefore, with row-/column-major ordering within cache-sized blocks and Morton ordering of those blocks, themselves. So, one can enjoy the temporal locality of nested blocks, as well as compiler optimizations on row- or column-major ordering in base blocks.


dilated integers, Morton order, quadtrees, compilers, index arithmetic


Michael D. Adams and David S. Wise. Fast additions on masked integers. SIGPLAN Notices, 41(5):39–45, May 2006. ISSN 0362-1340. doi: 10.1145/1149982.1149987.

BibTeX Entry

  author = {Adams, Michael D. and Wise, David S.},
  title = {Fast additions on masked integers},
  journal = {SIGPLAN Notices},
  pages = {39--45},
  year = {2006},
  volume = {41},
  number = {5},
  address = {New York, NY, USA},
  month = may,
  publisher = {ACM},
  issn = {0362-1340},
  doi = {10.1145/1149982.1149987},

Copyright Notice

© ACM, 2006. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SIGPLAN Notices, Vol. 41, Num. 5, (2006).