【C# 每日一题6】素数个数解决方法

【C# 每日一题6】素数个数
输入a b （0<a<=b<10000000)
求a b之间（不算a,b）的素数个数！

input:
3 17
output:
4

因为之间的是5 7 11 13

这个题应该有很多方法，求最优算法，大家想想怎么算最快呢？



[解决办法]

C# code

using System;using System.Collections;using System.Collections.Generic;using System.Linq;using System.Text;namespace Primes{   public class Primes   {      private long min;      private long max;      public Primes()         : this(2, 100)      {      }      public Primes(long minimum, long maximum)      {         if (min < 2)            min = 2;         else            min = minimum;         max = maximum;      }      public IEnumerator GetEnumerator()      {         for (long possiblePrime = min; possiblePrime <= max; possiblePrime++)         {            bool isPrime = true;            for (long possibleFactor = 2; possibleFactor <=               (long)Math.Floor(Math.Sqrt(possiblePrime)); possibleFactor++)            {               long remainderAfterDivision = possiblePrime % possibleFactor;               if (remainderAfterDivision == 0)               {                  isPrime = false;                  break;               }            }            if (isPrime)            {               yield return possiblePrime;            }         }      }   }}   class Program   {      static void Main(string[] args)      {         Primes primesFrom2To1000 = new Primes(2, 1000);         foreach (long i in primesFrom2To1000)            Console.Write("{0} ", i);         Console.ReadKey();      }   }
[解决办法]
素数没产生的公式吧...
多核情况下用多个线程探测吧.
[解决办法]
用素数筛，复杂度是O(n)

C/C++ code
#include <algorithm>#include <cstdio>template<int MAX_PRIME>struct PNMaker {    bool isP[MAX_PRIME]; //标记某个数是不是素数    int p[MAX_PRIME]; //素数线性表    //找出[1, N)的所有素数,并且返回素数的个数    inline int makePrimes(int N) {        fill(isP, isP + N, true);        int i, j;        int top = 0;        int x;        isP[0] = isP[1] = false;        for (i = 2; i < N; ++i) {            if (isP[i]) p[top++] = i;            for (j = 0; j < top; ++j) {                x = p[j] * i;                if (x >= N) break;                isP[x] = false;                if (i % p[j] == 0) break;            }        }        return top;    }    /////////////////////////////////////    int p_num;    void init() {        p_num = makePrimes();    }    int getNum() { return p_num;}    bool isPrm(int i) { return isP[i]; }    int get(int index) { return p[index]; }    /////////////////////////////////////    bool isPrmForce(unsigned int p) {        if (p == 2 || p == 3) return true;        else if(p % 2 == 0 || p % 3 == 0) return false;        int step = 4;        int i;        for (i = 5; i * i <= p; i += step) {            if (p % i == 0) return false;            step = 6 - step;        }        return true;    }};using namespace std;PNMaker<10000005> p;int main() {    int a, b;    scanf("%d %d", &a, &b);    p.makePrimes(b);    int cnt = 0;    for (int i = a + 1; i < b; ++i)        if (p.isPrm(i))            ++cnt;    printf("%d\n", cnt);    return 0;}
[解决办法]
探讨


引用:

C# code

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Primes
{
public class Primes
……

------解决方案-------------------- 
 
代码经过修改说明我的程序是可以连续测试样例的
C# code
using System;using System.Collections;using System.Collections.Generic;using System.Linq;using System.Text;namespace Primes{   public class Primes:IDisposable   {      private long min;      private long max;      public Primes()         : this(2, 100)      {      }      public Primes(long minimum, long maximum)      {         if (min < 2)            min = 2;         else            min = minimum;         max = maximum;      }      public IEnumerator GetEnumerator()      {         for (long possiblePrime = min; possiblePrime <= max; possiblePrime++)         {            bool isPrime = true;            for (long possibleFactor = 2; possibleFactor <=               (long)Math.Floor(Math.Sqrt(possiblePrime)); possibleFactor++)            {               long remainderAfterDivision = possiblePrime % possibleFactor;               if (remainderAfterDivision == 0)               {                  isPrime = false;                  break;               }            }            if (isPrime)            {               yield return possiblePrime;            }         }      }                 public void Dispose()     {        Dispose(true);        GC.SuppressFinalize(this);     }      protected virtual void Dispose(bool disposing)     {        if (!m_disposed)        {            if (disposing)            {               // Release managed resources            }              // Release unmanaged resources              m_disposed = true;        }     }       ~Primes()     {        Dispose(false);     }       private bool m_disposed;   }}   class Program   {      static void Main(string[] args)      {          string s ="";          while(!(s.ToLower().Equals("exit")))          {              Console.WriteLine("请输入你要输出素数的范围 如1000");              long i = long.Parse(Console.ReadLine());              using(Primes primesFrom2To1000 = new Primes(2 , i))              {                  foreach(long j in primesFrom2To1000)                      Console.Write("{0} " , j);              }              Console.WriteLine();              Console.WriteLine("请输入exit退出或者继续");              s = Console.ReadLine();                        }      }   }
[解决办法]
这个版本无论你有多少行询问复杂度都是O(N + M)，N是被询问里最大的那个数（<10000000), M是询问的个数

C/C++ code
#include <algorithm>#include <cstdio>using namespace std;template<int MAX_PRIME>struct PNMaker {    bool isP[MAX_PRIME]; //标记某个数是不是素数    int p[MAX_PRIME]; //素数线性表    //找出[1, N)的所有素数,并且返回素数的个数    inline int makePrimes(int N) {        fill(isP, isP + N, true);        int i, j;        int top = 0;        int x;        isP[0] = isP[1] = false;        for (i = 2; i < N; ++i) {            if (isP[i]) p[top++] = i;            for (j = 0; j < top; ++j) {                x = p[j] * i;                if (x >= N) break;                isP[x] = false;                if (i % p[j] == 0) break;            }        }        return top;    }    /////////////////////////////////////    int p_num;    void init() {        p_num = makePrimes();    }    int getNum() { return p_num;}    bool isPrm(int i) { return isP[i]; }    int get(int index) { return p[index]; }};struct duo {    int a, b;    void set(int x, int y) { a = x; b = y; }};////////////////////////////////////////////////////////////PNMaker<10000005> p;int before[10000005];duo query[1000000];int maxNum;int N;//////////////////////////////////////////////////////////////void input() {    int i = 0;    int a, b;    maxNum = -99999999;    while(1) {        if (scanf("%d %d", &a, &b) == 2) {            query[i].set(a, b);            ++i;            maxNum = max(maxNum, max(a, b));        }        else            break;    }    N = i;}void init() {    p.makePrimes(maxNum+1);    before[2] = 0;    for (int i = 3; i <= maxNum; ++i) {        before[i] = before[i-1] + (p.isPrm(i-1) ? 1 : 0);    }}void run() {    int i;    for (i = 0; i < N; ++i) {        int a, b;        a = query[i].a;        b = query[i].b;        printf("%d\n", before[b] - before[a] - (p.isPrm(a) ? 1 : 0));    }}int main() {    input();    init();    run();    return 0;} 
 
[解决办法]
其实用线性素数筛子绝对可以解决了，因为可以利用预处理来应付多个数据的问题

先用素数筛子把1..N以内的素数全部选出来，这个复杂度是O(N)
然后令B[i] 表示 [1..i) 区间内的素数个数，我们有B[i] = B[i-1] + （i-1是素数 ? 1 : 0）,这一步的复杂度也是O(N)
然后对于每个询问(a,b)，只要输出 B[b] - B[a] - (a是素数 ? 1 : 0)，这一步的复杂度是O(M),因为总共有M个询问

所以最后的复杂度O(N+M)
[解决办法]
来个急速版的
C# code
        static void Main()        {            Console.WriteLine((int)PrimeCount(1000000));            Console.Read();        }        static double PrimeCount(double num)        {            return num / Math.Log(num);        }
[解决办法]
这是带注释的版本：

C/C++ code
#include <algorithm>#include <cstdio>using namespace std;template<int MAX_PRIME>struct PNMaker {    bool isP[MAX_PRIME]; //标记某个数是不是素数    int p[MAX_PRIME]; //素数线性表    //找出[1, N)的所有素数,并且返回素数的个数    inline int makePrimes(int N) {        fill(isP, isP + N, true);        int i, j;        int top = 0;        int x;        isP[0] = isP[1] = false;        for (i = 2; i < N; ++i) {            if (isP[i]) p[top++] = i;            for (j = 0; j < top; ++j) {                x = p[j] * i;                if (x >= N) break;                isP[x] = false;                if (i % p[j] == 0) break;            }        }        return top;    }    /////////////////////////////////////    int p_num;    void init() {        p_num = makePrimes();    }    int getNum() { return p_num;}    bool isPrm(int i) { return isP[i]; }    int get(int index) { return p[index]; }};struct duo {    int a, b;    void set(int x, int y) { a = x; b = y; }};////////////////////////////////////////////////////////////PNMaker<10000005> p;int before[10000005];duo query[1000000];int maxNum;int N;//////////////////////////////////////////////////////////////void input() {    int i = 0;    int a, b;    maxNum = -99999999;    while(1) {        if (scanf("%d %d", &a, &b) == 2) {            query[i].set(a, b);  //把询问存起来！            ++i;            maxNum = max(maxNum, max(a, b)); //maxNum表示所有的询问(a,b)里的最大的a或者b        }        else            break;    }    N = i;}void init() {    p.makePrimes(maxNum+1);  //进行素数筛子的工作，这一步结束以后就可以在O(1)内判断某个数是不是素数了！    before[0] = 0;    before[1] = 0;    before[2] = 0; //before[i] 表示在[1,i)内的素数的个数    for (int i = 3; i <= maxNum; ++i) {        before[i] = before[i-1] + (p.isPrm(i-1) ? 1 : 0); //递推每个before[i]    }}void run() {    int i;    for (i = 0; i < N; ++i) {        int a, b;        a = query[i].a;        b = query[i].b;        printf("%d\n", before[b] - before[a] - (p.isPrm(a) ? 1 : 0)); //每个询问都可以在O(1)解决    }}int main() {    input();    init();    run();    return 0;}
[解决办法]
C# code
    static class Solver    {        const int MaxLength = 10000000;        static int[] masks = new int[MaxLength];         static Solver()        {            for(int i = 2; i<MaxLength; i++)            {                if (masks[i] != 0)                {                    masks[i] = masks[i - 1];                }                else                {                    masks[i] = masks[i - 1] + 1;                    for (int elimiate = i + i; elimiate < MaxLength; elimiate += i)                    {                        masks[elimiate] = -1;                    }                }            }        }        public static int CountPrimes(int floorExclusive, int ceilingExclusive)        {            if (ceilingExclusive <= floorExclusive) return 0;            return masks[ceilingExclusive - 1] - masks[floorExclusive];        }    } 
 
[解决办法]
筛法。。。
[解决办法]
用Meissel-Lehmer method，可以更快，低于线性的，有功夫写一个。
[解决办法]
探讨


引用:

用素数筛，复杂度是O(n)

C/C++ code

#include <algorithm>
#include <cstdio>

template<int MAX_PRIME>
struct PNMaker {
bool isP[MAX_PRIME]; //标记某个数是不是素数
int p[MAX_PRIME]; //素数线性表
……

[解决办法]
既然b是有限值，那先建立一个范围内的素数数组。查询一下就知道结果啊。
[解决办法]
用hashmap记录素数和其对应在[1,10000000]素数队列的下标，然后直接去查hashmap即可。
hashmap效率很高的。
下面是java code


package com.myprime;

import java.util.HashMap;

public class MyPrimes {
private int low;
private int high;

private final int MIN = 1;
private final int MAX = 10000000;
private static HashMap<Integer, Integer> primesHashMap = new HashMap<Integer, Integer>();//key = 素数，value = 素数所在的素数队列中的下标
private static boolean isFirst = true;//如果是第一次测试，就将该区间所有素数放到map里

public MyPrimes(int low,int high){
this.low = low;
this.high = high;
}

public int getLow() {
return low;
}

public int getHigh() {
return high;
}

public int getNum(){
System.out.println("low = " + low + " high = " + high);
int lownum = 0,highnum = 0;
//仅在第一次的时候查找
if(isFirst == true){
getPrimes();
}
lownum = getLowPrime();
//该范围内没有素数
if(lownum == 0){
return 0;
}
highnum = getHighPrime();
//不要忘记+1
return primesHashMap.get(highnum) - primesHashMap.get(lownum) + 1;
}

//获取离low最近的素数
private int getLowPrime(){
for(int i = getLow();i <= getHigh();i++){
if(isPrime(i) == true){
return i;
}
}
return 0;
}

//获取离high最近的素数
private int getHighPrime(){
for(int i = getHigh();i >= getLow();i--){
if(isPrime(i) == true){
return i;
}
}
return 0;
}

private void getPrimes(){
int index = 1;
for(int i = MIN;i <= MAX;i++){
if(isPrime(i) == true){
primesHashMap.put(i, index++);
}
}
isFirst = false;
}

private boolean isPrime(int n){
if(n == 1){
return false;
}
for(int i = 2;i <= Math.sqrt(n);i++){
if(n % i == 0){
return false;
}
}
return true;
}
}




package com.myprime;

public class MainTest {

public static void main(String[] args) {
System.out.println(new MyPrimes(12345, 987654).getNum());
System.out.println(new MyPrimes(1, 12).getNum());
System.out.println(new MyPrimes(10, 10).getNum());
System.out.println(new MyPrimes(666, 7777).getNum());

}

}


result:
low = 12345 high = 987654
count = 76140
low = 1 high = 12
count = 5
low = 10 high = 10
count = 0
low = 666 high = 7777
count = 864
[解决办法]
题目漏看了句话 求a b之间（不算a,b）的素数个数！。。
//获取离low最近的素数
private int getLowPrime(){
for(int i = getLow();i <= getHigh();i++){//改成 getLow() + 1
if(isPrime(i) == true){
return i;
}
}
return 0;
}

//获取离high最近的素数
private int getHighPrime(){
for(int i = getHigh();i >= getLow();i--){ //改成 getHigh() - 1 
 
if(isPrime(i) == true){
return i;
}
}
return 0;
}

哈哈，又犯小错误了～～
[解决办法]
本人解法：根据初等数论，不能被其平方根之内的数整除就不是素数。http://blog.csdn.net/xiaoxin888888/archive/2011/05/27/6450182.aspx
[解决办法]
贴一个网上参考的算法
C# code
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{    class Program    {        static public void priem(int size)        {            int n = 0;            if (size % 2 == 0)                n = (size - 2) / 2;            else                n = (size - 1) / 2;              bool[] p = new bool[n];            for (int i = 0; i < n; i++)                p[i] = true;// 初始化全部奇数为素数。p[0]对应3，即p[i]对应2*i+3               for (int i = 0; i < Math.Sqrt(size); i++)            {                if (p[i])//如果 i+i+3 是素数                   {                    for (int k = i + i + 3, j = k * i + k + i; j < n; j += k) // 筛法起点是 p[i]所对应素数的平方 k^2                           // k^2在 p 中的位置是 k*i+k+i                           //    下标 i         k*i+k+i                          //对应数值 k=i+i+3   k^2                          p[j] = false;                }            }                      Console.WriteLine(2);            for (int i = 0; i < p.Length; i++)            {                if (p[i])                {                    Console.WriteLine(3 + 2 * i);                }            }            Console.Read();        }        static void Main(string[] args)        {            priem(100);        }    }}
[解决办法]
C# code
         //素数的个数         public static int CountPrimes(int min, int max)        {            int count = 0;            for (int i = min+1; i < max; i++)            {                if (IsPrime(i))                    count++;            }            return count;        }        //判断是否是素数         public static bool IsPrime(int n)        {            bool flag=false;            for (int i = 2; i < n; i++)            {                flag = n % i == 0;                if (flag)                    break;            }            return !flag;        }
[解决办法]
贴个最简单的，也是最费时间的~~~~~~
其实，最快的就是用已经建立好的素数表进行直接查找~~~~~
找素数真的是门高深的学问~~~
C/C++ code
#include <iostream>using namespace std;int main(){    bool isPrime(const int);    int low, high;    cin >> low >> high;    for(int i = low; i <= high; ++i)        if(isPrime(i))            cout << i << "\t";    cout << endl;    return EXIT_SUCCESS;}bool isPrime(const int value){    int temp = value;        for(int i = 2; i < value; ++i)    {        if(0 == temp % i)            return false;    }    return true;}
[解决办法]
C# code
class Program{    const int N = 10000000;    static int[] nums = new int[(N >> 5) + 1];    static void Main(string[] args)    {        CreatePrimeTable();        Console.WriteLine(PrimeCount(8000, 10000));        Console.WriteLine(PrimeCount(10, 10000000));        Console.Read();    }    //用筛法获得素数表。    //Convert.ToString(nums[0],2)得到的字符串1011111011101011101011101010011表示0-31的素数情况    //从左到右，0表示素数 1表示合数    //依次类推nums[1] 表示32-63 的素数表    private static void CreatePrimeTable()    {        nums[0] = 3;        for (int i = 2; i <= N; i++)            if ((nums[i >> 5] & (1 << (i & 31))) == 0)                for (int x = i + i; x <= N; x += i)                    nums[x >> 5] |= (1 << (x & 31));    }    //从素数表查询素数的个数。    private static int PrimeCount(int startNum, int endNum)    {        startNum++;//因为不算自身        endNum--; //因为不算自身        if (startNum < 0 || endNum > N || startNum > endNum) return 0;        int s1, s2, e1, e2, count = 0;        s1 = startNum >> 5;        e1 = endNum >> 5;        s2 = startNum & 31;        e2 = endNum & 31;        if (s1 == e1)            return ZeroCount(nums[s1], s2, e2);        count += ZeroCount(nums[s1], s2, 31);        for (int i = s1 + 1; i < e1; i++)            count += ZeroCount(nums[i], 0, 31);        count += ZeroCount(nums[e1], 0, e2);        return count;    }    //单个素数表num中0(素数)的个数    //startBit查询的开始位，左边界 endBit查询的结束位 右边界    private static int ZeroCount(int num, int startBit, int endBit)    {        uint maskNum = uint.MaxValue;        maskNum <<= 31 - endBit;        maskNum >>= 31 - endBit + startBit;        maskNum <<= startBit;        maskNum = (uint)(num & maskNum);        int count = 0;        while (maskNum > 0)        {//2进制数中1的个数。             count ++;            maskNum &= (maskNum - 1);        }        return endBit- startBit + 1 - count;//总查询数 - 1的个数 = 0的个数    } 
 
[解决办法]
跟我在大一写的差不多：
static void Main(string[] args)
{
  Console.WriteLine("请输入你要计算的从2到多少的素数：");
           int N = Convert.ToInt16(Console.ReadLine());
           //const int N = 100;           //const指定N为常数，不能被修改
           bool[] isprime = new bool[N + 1];     //定义数组isprime为bool类型

           int i, total = 0;
           for (i = 2; i < isprime.Length; i++)
           {
               isprime[i] = true;
           }
           for (i = 0; i < Math.Sqrt(N); i++)
           {
               if (isprime[i] == true)
               {
               
                       for (int k = 2 * i; k < isprime.Length; k = k + i)
                       isprime[k] = false;
               }
           }
           for (i = 2; i < isprime.Length; i++)
           {
               if (isprime[i] == true)
               {
                   total++;
                   Console.Write("{0,5}", i);
                   if (total % 10 == 0)
                       Console.WriteLine("\n");
               }

           }
           Console.WriteLine("\n从2到{0}共有{1}个素数", N,total);
           Console.ReadKey();  

         
       }
  
[解决办法]
个人感觉算法不必写的那么详细,说一下我个人的思想吧.
首先不知楼主知不知道筛选素数的方法,比如10000以内的素数求法是-->一开始在H[10001]中去掉2的倍数-->循环到3,由于没有被去掉,去掉3的倍数,--->4(被去),5(没去,循环去掉5的倍数),6(去掉了),一直判断到根号10000 也就是100;
在此基础之上,将去掉的位置设置为0,没去掉的位置上保存一个递增的数值,比如2的时候是1,3的时候是2,5的时候是3;
例如
memset(H,1,10000);
int primeNum=1;
for(i=2;i<100;i++)
if(H[i]!=0){
   primeNum++;
   H[i]=primeNum;
   for(j=i*2;j<10000;j+=i)
   {
       H[j]=0;
   }
}
这样就构造好了一个素素个数的表.
在取得 n,m间的素数个数时.可以从n向前判断H[n-i]是否为0,用H[m-j]-H[n-i]"这里两个数都是m和n向前第一次遇到的非零值.",即为楼主想要的数字.
不知楼主能否明白我说的原理.


这个的第一个素数筛选方法是由素数的定义得到的 只被1和自身整除,那么从2开始不断的去倍数,就排除了非素数. 而为什么是根号,可以用一个计算式说明 10*10=100 2*50=100 50*2=100,在根号左右的两个因子只是换了位置而已.
话就到此了.
[解决办法]
求 PI(x) 有 O(N^(2/3+ε)) 的算法, 试过求 PI( 1E10 ) 也是秒出...


[解决办法]
探讨


引用:

求 PI(x) 有 O(N^(2/3+ε)) 的算法, 试过求 PI( 1E10 ) 也是秒出...

求思想，求代码，求验证！
求回答，是否是和31楼liyaoye的想法一样的！

[解决办法]
不会 C# , 只好贴个C的, 我这运行结果是:
$ cl -nologo -O2 -Ox -Og 1.c ; time ( echo 0 100000000000 | ./1 ) ; time ( echo 0 10000000000 | ./1 )
1.c
4118054813

real    0m8.812s
user    0m0.046s
sys     0m0.000s
455052511

real    0m1.640s
user    0m0.030s
sys     0m0.030s



[解决办法]
struct PNMaker {
   bool isP[MAX_PRIME]; //标记某个数是不是素数
   int p[MAX_PRIME]; //素数线性表
   //找出[1, N)的所有素数,并且返回素数的个数
   inline int makePrimes(int N) {
       fill(isP, isP + N, true);
       int i, j;
       int top = 0;
       int x;
       isP[0] = isP[1] = false;
       for (i = 2; i < N; ++i) {
           if (isP[i]) p[top++] = i;
           for (j = 0; j < top; ++j) {
               x = p[j] * i;
               if (x >= N) break;
               isP[x] = false;
               if (i % p[j] == 0) break;
           }
       }
       return top;
   }



------解决方案-------------------- 
 
刚试了下时间，初始化素数表300ms  后面的运算不怎么用时间
C# code
class Program{    const int N = 10000000;    static int[] nums = new int[(N >> 5) + 1];    static void Main(string[] args)    {        DateTime dt = DateTime.Now;        CreatePrimeTable();        Console.WriteLine( "初始化时间:"+(DateTime.Now - dt).TotalMilliseconds);               dt = DateTime.Now;        Console.WriteLine("结果:" + PrimeCount(12345, 987654));        Console.WriteLine("结果:" + PrimeCount(10, 10000000));        Console.WriteLine("结果:" + PrimeCount(1, 100));        Console.WriteLine("运算时间:" + (DateTime.Now - dt).TotalMilliseconds);        Console.Read();    }    //用筛法获得素数表。    //Convert.ToString(nums[0],2)得到的字符串1011111011101011101011101010011表示0-31的素数情况    //从左到右，0表示素数 1表示合数    //依次类推nums[1] 表示32-63 的素数表    private static void CreatePrimeTable()    {        nums[0] = 3;        for (int i = 2; i <= Math.Sqrt(N); i++)            if ((nums[i >> 5] & (1 << (i & 31))) == 0)                for (int x = i + i; x <= N; x += i)                    nums[x >> 5] |= (1 << (x & 31));    }    //从素数表查询素数的个数。    private static int PrimeCount(int startNum, int endNum)    {        startNum++;//因为不算自身        endNum--; //因为不算自身        if (startNum < 0 || endNum > N || startNum > endNum) return 0;        int s1, s2, e1, e2, count = 0;        s1 = startNum >> 5;        e1 = endNum >> 5;        s2 = startNum & 31;        e2 = endNum & 31;        if (s1 == e1)            return ZeroCount(nums[s1], s2, e2);        count += ZeroCount(nums[s1], s2, 31);        for (int i = s1 + 1; i < e1; i++)            count += ZeroCount(nums[i], 0, 31);        count += ZeroCount(nums[e1], 0, e2);        return count;    }    //单个素数表num中0(素数)的个数    //startBit查询的开始位，左边界 endBit查询的结束位 右边界    private static int ZeroCount(int num, int startBit, int endBit)    {        uint maskNum = uint.MaxValue;        maskNum <<= 31 - endBit;        maskNum >>= 31 - endBit + startBit;        maskNum <<= startBit;        maskNum = (uint)(num & maskNum);        int count = 0;        while (maskNum > 0)        {//2进制数中1的个数。             count ++;            maskNum &= (maskNum - 1);        }        return endBit- startBit + 1 - count;//总查询数 - 1的个数 = 0的个数    }}