Journal Article

A Systematical and Parallel Approach to Solve Problems Involving Special Properties of Bit-Vectors

Chia Shin Ou, Chin Lung Lu and R.C.T. Lee

in The Computer Journal

Volume 58, issue 5, pages 1112-1121
Published in print May 2015 | ISSN: 0010-4620
Published online April 2014 | e-ISSN: 1460-2067 | DOI: https://dx.doi.org/10.1093/comjnl/bxu025
A Systematical and Parallel Approach to Solve Problems Involving Special Properties of Bit-Vectors

Show Summary Details

Preview

Suppose that we are given a vector consisting of only 1's and 0's and we are interested in finding some special properties of this vector. For instance, we like to determine whether all of the bits from location s to location e in the vector are all 1's or whether there exists a 1 from location s to location e. In more complicated cases, we are given two bit-vectors and we like to investigate the mutual properties between the two vectors. For instance, we want to find all locations i in vector B such that there exists a k in vector A, ki, such that A(k)=1 and in vector B, locations from k to i all assume value 1. These problems all involve ‘for-all’ or ‘there-exists’ notations and can of course be solved by sequential programs. In this paper, we are interested in bit-parallel process to solve these problems. That is, we are interested in solving the problem efficiently by using ‘bitwise-and’, ‘bitwise-or’ and other bitwise logical operations. A sequence of logical operations can be expressed as a logical formula. This paper proposes a systematical method to find such logical formulas to solve problems involving bit-vectors with ‘for-all’ and ‘there-exists’ notations. Five logical prototype problems, named ‘single-for-all’ (1's), ‘single-there-exists’, ‘multiple-for-all’, ‘multiple-there-exists’ and ‘multiple-there-exists-and-for-all’, are defined in this paper. For each problem, we show that there exists a corresponding logical formula that can be computed using bit-parallel operations in O(n/w) time, where w is the word size of the machine. We also propose four variants for these five problems, and show that their logical formulas can be obtained using those of the five prototype problems.

Keywords: bit-parallel; logical operation; for-all operation; there-exists operation

Journal Article.  0 words. 

Subjects: Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.