StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
9947181
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2012-03-30T16:46:46.737
FavoriteCount
0
LastActivityDate
2012-03-30T19:09:00.593
LastEditDate
2012-03-30T19:09:00.593
LastEditorUserId
1256609
OwnerUserId
1256609
ParentId
9943479
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
<p>Here is O((log n)^3). </p> <h1>Lets compute how many numbers fits in first N bits</h1> <p>Imagine that we have function:</p> <pre><code>long long number_of_all_bits_in_sequence(long long M); </code></pre> <p>It computes length of "Fibonacci bit sequence of natural numbers" created by all numbers that aren't greater than M.</p> <p>With this function we could use binary search to find how many numbers fits in the first N bits.</p> <h1>How many bits are 1's in representation of first M numbers</h1> <p>Lets create function which calculates how many numbers <= M have 1 at k-th bit.</p> <pre><code>long long kth_bit_equal_1(long long M, int k); </code></pre> <p>First lets preprocess results of this function for all small values, lets say M <= 1000000. </p> <p>Implementation for M > PREPROCESS_LIMIT:</p> <pre><code>long long kth_bit_equal_1(long long M, int k) { if (M <= PREPROCESS_LIMIT) return preprocess_result[M][k]; long long fib_number = greatest_fib_which_isnt_greater_than(M); int fib_index = index_of_fib_in_fibonnaci_sequence(fib); if (fib_index < k) { // all numbers are smaller than k-th fibbonacci number return 0; } if (fib_index == k) { // only numbers between [fib_number, M] have k-th bit set to 1 return M - fib_number + 1; } if (fib_index > k) { long long result = 0; // all numbers between [fib_number, M] have bit at fib_index set to 1 // so lets subtrack fib_number from all numbers in this interval // now this interval is [0, M - fib_number] // lets calculate how many numbers in this inteval have k-th bit set. result += kth_bit_equal_1(M - fib_number, k); // don't forget about remaining numbers (interval [1, fib_number - 1]) result += kth_bit_equal_1(fib_number - 1, k); return result; } } </code></pre> <p>Complexity of this function is O(M / PREPROCESS_LIMIT).</p> <p>Notice that in reccurence one of the addends is always one of fibbonaci numbers. </p> <pre><code>kth_bit_equal_1(fib_number - 1, k); </code></pre> <p>So if we memorize all computed results than complexity will improve to T(N) = T(N/2) + O(1) . T(n) = O(log N).</p> <h1>Lets get back to number_of_all_bits_in_sequence</h1> <p>We can slighly modify kth_bit_equal_1 so it would also count bits equal to 0.</p>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POCounting the bits set in the Fibonacci number system?
  singulars
  PostTypePostTypeId
  PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USJarosław Gomułka
UserOwnerUserId
1. USJarosław Gomułka
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.