1

我的问题与论坛中的上一个问题有关 - 范围内整数的二进制补码二进制表示中的 1 的数量对 我来说没有“添加评论”。所以我在这里问它问题是计算1 以 2 的补码形式记下所有数字，这些数字在两个输入数字指定的范围内 解决方案发布在https://gist.github.com/1285119 如下

long long solve(int a)
  {
  if(a == 0) return 0 ;
  if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ;
  return ((long long)a + 1) / 2 + 2 * solve(a / 2) ;
  }


 long long solve(int a,int b)
 {
  if(a >= 0)
  {
   long long ret = solve(b) ;
   if(a > 0) ret -= solve(a - 1) ;
   return ret ;
   }
 long long ret = (32LL * -(long long)a) - solve(~a) ;
 if(b > 0) ret += solve(b) ;
 else if(b < -1)
 {
  b++ ;
  ret -= (32LL * -(long long)b) - solve(~b) ;
 }
return ret ;
}

当输入为4时 //测试用例数

-1 //第一个数字 -2 //第二个数字 输出 0

-1 -3 输出 -31

-3 -5 输出 -30 //1 的个数怎么能是 -30

1 2 输出 2

由于代码作为 Codesprint 解决方案发布在 InterviewStreet 上，并且在这个论坛上获得了高度投票的答案。它应该是正确的。谁能解释一下 long long ret = (32LL * -(long long)a) - solve(~a) in solve(int a,int b) 这行背后的逻辑以及#define INF (int)1e9 的目的是什么//不使用时设置无穷大的值？

4

1 回答 1

0

您输入的错误结果

-1 -2
-1 -3
-3 -5

是因为程序假定这两个限制是按升序输入的，不做检查，因此输入不符合预期会产生错误的结果。一个简单的

if (b < a) {
    int temp = a;
    a = b;
    b = temp;
}

在开头int solve(int a, int b)将使它返回正确的输入结果以任何顺序输入。

背后的逻辑long long ret = (32LL * -(long long)a) - solve(~a)是（在二进制补码中）nis的按位补码~n = (-n)-1。a从到的数字（包括 0 或 1）的总位数-1是32 * |a|if a < 0。从该计数中，我们减去这些数字中 0 位的总数，即按位补码中 1 位的总数。这些按位补码是从 0 到 的数字|a| - 1 = ~a，包括 0 和 1，其中 1 位的计数由 给出solve(|a| - 1) = solve(~a)。

于 2012-04-03T22:54:19.667 回答