【题目大意】给出两个数a,b.求出在[a,b]区间中二进制形式只包含一个0的数字个数。
【解题思路】对于满足整数域中满足上面要求的数字都是可以按序求出的，例如10,101,110,1011,1101,1110…并且当二进制的长度（不为零的最高位）确定，该长度的满足要求数字个数是确定的。并且可以根据规律求出。
因此，可以求得≥a且最小的 满足要求的数A（用（l1，z1）表示。L:二进制长度，Z：唯一一个0的位置）同理也有≤b的最大的数B（l2,z2）,进而可以根据A和B得出ans。
代码如下
1 #include "iostream" 2 using namespace std; 3 int Slong(long long s) //求出数字长度 4 { 5 int i = 0; 6 while (s) 7 { 8 s = s / 2; 9 i++; 10 } 11 return i; 12 } 13 long long getnz(int n, int z)//根据数字长度（二进制）和0的位置==>十进制数字 14 { 15 long long i = 1; 16 long long k = 0; 17 for (int j = 1 ; j <= n ; j++) 18 { 19 if ( j != z ) k += i; 20 i *= 2; 21 } 22 return k; 23 } 24 int main() 25 { 26 long long a, b; 27 int n1 = 0, n2 = 0, z1 = 0, z2 = 0; 28 cin >> a >> b; 29 int l = Slong(a); 30 if (a > getnz(l, 1)) 31 // 边界:如果a比该长度下最大的满足要求数字还大, 32 // A的为(L+1,L) 33 // 长度比a长1第二高位为0 34 // (例:10111111111111111……) 35 { 36 n1 = l + 1; 37 z1 = l; 38 } 39 else 40 for ( int i = l - 1 ; i >= 1 ; i-- ) //从小到大枚举该长度下的数字，求A 41 { 42 if (getnz(l, i) >= a) 43 { 44 n1 = l; 45 z1 = i; 46 break; 47 } 48 } 49 l = Slong(b); 50 if (b < getnz(l, l - 1)) 51 // 边界:如果b比该长度下最小的满足要求数字还小, 52 // A的为(L-1,1) 53 // 长度比a小1第一位为0 54 // (例:11111……1110 ) 55 { 56 n2 = l - 1; 57 z2 = 1; 58 } 59 else 60 for ( int i = 1 ; i < l ; i++ )// 从大到小枚举该长度下数，求得B 61 { 62 if (getnz(l, i) <= b) 63 { 64 n2 = l; 65 z2 = i; 66 break; 67 } 68 } 69 //n1,n2表示A，B长度 z1,z2 表示A,B中0的位置 70 int ans; 71 if (n1 > n2) ans = 0; //ans = 0的情况 72 else if (n1 == n2) ans = (z1 - z2) + 1; 73 else ans = (n1 + n2 - 2) * (n2 - n1 - 1) / 2 + z1 + n2 - z2; 74 // 求得长度[n1+1,n2-1]中数字个数【 (n1 + n2 - 2) * (n2 - n1 - 1) / 2】 75 // 长度n1中数字个数 【z1】 76 // 长度n2中数字个数 【n2 - z2】 77 cout << ans << endl; 78 }