1
$\begingroup$

Problem: How do we can generate some mathematical close form of the following sequence, which has following 256 entries:

1 7 7 7 7 9 9 9 7 9 9 9 7 9 9 9 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15

Origin/background of Problem: These number are generated from a divide and conquer algorithm. For example if we have a 8 bit binary-string and we are asked to find the location of 1's in minimal number of questions then, the above sequence is the # of questions asked for each possible binary 8-bit word i.e from 00000000, 00000001 ....11111111 the corresponding # of questions are elements of above sequence i.e 1,7,..15, respectively.

Algorithm:

Lets take 0000 0001, for instance:

1) First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.

2) Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?

3) Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.

4) This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.

$\endgroup$
  • 2
    $\begingroup$ Could you explain somewhat further the motivation for your question? Just tossing a sequence up and vaguely detailing its origin, it seems that you don't really care all that much for an answer. For example, a specific inquiry: how does the minimal number of questions needed to find all the 1s in a binary representation of 0x01 result in the number 7? What is a question, please give a rigorous definition. $\endgroup$ – Kaya Jul 11 '13 at 3:08
  • $\begingroup$ What's wrong with the closed form that you've already given (the list of 256 values)? $\endgroup$ – JeffE Jul 11 '13 at 9:33
  • $\begingroup$ And why are any of those numbers bigger than 8? (Is bit 0 equal to 1? Is bit 1 equal to 1? Is bit 2 equal to 1? ...) $\endgroup$ – JeffE Jul 11 '13 at 9:35
  • $\begingroup$ @Kaya For instance, we have a 8-bit long binary number, say 00000001, then my algorithm would go like this: $\endgroup$ – kaka Jul 12 '13 at 16:48
  • 1
    $\begingroup$ @kaka You should (re)edit your question to ask exactly what you want to know. $\endgroup$ – Raphael Jul 13 '13 at 12:12
1
$\begingroup$

Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=00010101$. Then the sequence is $$ 0111, 11, 1, $$ and so $N = 6$ and the cost is $13$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.