Find the decimal number rank based on the function F (N) = rank

Question

I found this question here , but this is not the answer I'm looking for. Therefore, send again.

View function:

F( N ) = rank 

means that Given the number N in decimal notation, its rank is given as:

 Starting from 0 to N, how many numbers are there with same number of set bits in its binary representation. 

I will consider an example to make it more understandable.

 N = 6 ( 0110 ) Its rank is 3. 1. 3 ( 0011 ) 2. 5 ( 0101 ) 3. 6 ( 0110 ) 

Now, given the number, find its rank.

The obvious approach is to start from scratch and check the number of bits set for each number up to N-1 .

The question arises:

Is there any logN solution?

Answer 1

Yes, there is a solution log n .

Suppose that bit k set to n , the most significant bit is at position p (starting from 0, so 2^p <= n < 2^(p+1) ). Then there is pCk (binomial coefficient, also choose(p,k) ) a way to place k bits at positions 0, ..., p-1 , all of them give numbers with exactly k set bits that are less than n . If k == 1 , then it will otherwise remain a number with k bits set, and the p bit is the –th bit, which is less than n for consideration. They can be counted by determining the rank n - 2^p .

Code (not optimal, does some unnecessary recalculation and not everything that he could do to avoid overflow):

 unsigned long long binom(unsigned n, unsigned k) { if (k == 0 || n == k) return 1; if (n < k) return 0; if (k > (n >> 1)) k = nk; unsigned long long res = n, j; // We're not doing all we can to avoid overflow, as this is a proof of concept, // not production code. for(j = 2; j <= k; ++j) { res *= (n+1-j); res /= j; } return res; } unsigned popcount(unsigned long long n) { unsigned k = 0; while(n) { ++k; n &= (n-1); } return k; } unsigned long long rank(unsigned long long n) { if (n == 0) return 1; unsigned p = 0, k = popcount(n); unsigned long long mask = 1,h = n >> 1; while(h > 0) { ++p; h >>= 1; } mask <<= p; unsigned long long r = binom(p,k); r += rank(n-mask); return r; } 

Tested in a loop for 0 <= n < 10^8 to check for errors without any inconsistency.

Check out the output here .

Answer 2

It can be solved using a combination and permutation methods.

F (N) = rank

First, find the number of bits that should represent N. In binary, a number can be constructed as follows:

 N = cn 2^n + .... + c3 2^2 + c2 2^1 + c1 2^0 

Now, to find n (or the number of bits in the binary representation of the number) in the above equation, we can assume that it will be floor(log2(N)) + 1 . For example, consider any number, say 118 , then it can be represented by gender (log2 (118)) + 1 = 7 bits.

 n = floor(log2(118)) + 1; 

Above the formula is only O(1) . Now we need to find how many 1s exist in the binary representation of the number. Given the pseudo code to complete this task:

 function count1(int N) { int c = 0; int N' = N; while(N' > 0) { N' -= 2^(floor(log2(N'))); c++; } } 

Above the pseudo code is O(logN) . I wrote a small script in MATLAB to check my pseudo code above and here are the results.

 count1(6) = 2 count1(3) = 2 count1(118) = 5 

Perfectly, now we have the number of bits and the number 1s in these bits. Now, to find the rank of a number, you can apply a simple combination and permutation. first suppose that n is the number of bits needed to represent the number, and c is the number 1 in the bit representation of the number. Therefore, the rank will be set as follows:

 r = n ! / c ! * (n - c) ! 

EDIT: As suggested by DSM, I corrected the logic to find the correct RANK. The idea is to remove all unnecessary numbers from the permutation. So added this code:

 for i = N + 1 : 2^n - 1 if count(i) == c r = r - 1; end end 

I wrote a MATLAb script to find the rank of a number using the method described above:

 function r = rankN(N) n = floor(log2(N)) + 1; c = count(N); r = factorial(n) / (factorial(c) * factorial(n - c)); % rejecting all the numbers may have included in the permutations % but are unnecessary. for i = N + 1 : 2^n - 1 if count(i) == c r = r - 1; end end function c = count(n) c = 0; N = n; while N > 0 N = N - 2^(floor(log2(N))); c = c + 1; end 

And above alogrithm O(1) + O(logN) + O(1) = O(logN) . Exit:

 >> rankN(3) ans = 1 >> rankN(4) ans = 3 >> rankN(7) ans = 1 >> rankN(118) ans = 18 >> rankN(6) ans = 3 

Note. Rank 0 always 1 , because the method above will not work for 0 , because log2(0) is undefined.

Answer 3

Here is a pretty efficient O (logN) implementation that does multiple additions in parallel at every step:

 unsigned int countBits( unsigned int bits ) { bits = ( bits & 0x55555555 ) + ( ( bits >> 1 ) & 0x55555555 ); bits = ( bits & 0x33333333 ) + ( ( bits >> 2 ) & 0x33333333 ); bits = ( bits + ( bits >> 4 ) ) & 0x0f0f0f0f; bits += bits >> 8; return ( bits + ( bits >> 16 ) ) & 63; } 

It starts with 16-bit add-ons, then adds 8 4-bit add-ons, etc. It can be expanded to work with 64-bit integers using longer masks and one additional step:

 unsigned int countBits( unsigned long long bits ) { bits = ( bits & 0x5555555555555555L ) + ( ( bits >> 1 ) & 0x5555555555555555LL ); bits = ( bits & 0x3333333333333333L ) + ( ( bits >> 2 ) & 0x3333333333333333LL ); bits = ( bits + ( bits >> 4 ) ) & 0x0f0f0f0f0f0f0f0fLL; bits += bits >> 8; bits += bits >> 16; return (unsigned int) ( bits + ( bits >> 32 ) ) & 127; }