Searching Words

Prev: Counting Bits

Next: Rearranging Bits and Bytes

Sections

• 6-1 Find First 0-Byte
• 6-2 Find First String of 1-Bits of a Given Length
• 6-3 Find Longest String of 1-Bits
• 6-4 Find Shortest String of 1-Bits

Problems

1. Code an elaboration of Hsieh’s algorithm that will find both the length and position of the longest string of 1’s in a word $x$. You may use the nlz function.

2. Code a function for finding the length and position of the shortest string of 1’s in a word $x$ that is at least as long as a given integer $n$.

3. Another way to find the shortest string of 1’s in a word $x$ is to successively turn off the rightmost string of 1’s in $x$ and observe the change in population count at each step. Code a function for the full RISC that uses this idea and also finds the position of a shortest string of 1’s.

4. For completely random 32-bit words $x$, each bit independently 0 or 1 with probability 0.5, what is the average number of strings of 1’s in $x$? The answer determines the average execution time of the function of exercise 3, for such input data.

5. Again, for completely random 32-bit words $x$, what is the average length of the shortest contiguous string of 1’s in $x$? The answer determines the average execution time of function fminstr1 in Figure 6-8 for such input data. Compute this with a Monte Carlo or exhaustive enumeration program.

6. Of the $2^n$ binary words of length $n$, for how many is their shortest contained string of 1’s of length 1? That is, how many $n$-bit words begin with 10, or end with 01, or contain the sequence 010? Find a closed-form solution or a recursion, not an exhaustive enumeration program.

7. Similarly, of the $2^n$ binary words of length $n$, for how many is their shortest contained string of 1’s of length 2?