c++ - 计算范围 [x,y] 中整数的二进制补码表示中的 1

Question

我的问题与论坛中的先前问题有关 - Number of 1s in the two's complement binary representations of integers in a range我没有“添加评论”。所以我在这里问题目是计算写下所有 2 的补码形式的数字中 1 的个数，这些数字在两个输入数字指定的范围内解决方案发布在 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-5Output -30//1的个数怎么可能是-30

12个输出 2

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

Answer 1

您输入的结果错误

-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)背后的逻辑是(二进制补码)n 的按位补码是~n = (-n)-1 . a 中数字的总位数(0 或 1)至 -1 - 包括在内 - 是 32 * |a|如果a < 0 .从该计数中，我们减去这些数字中 0 位的总数，即它们的按位补码中 1 位的总数。这些按位补码是从 0 到 |a| - 1 = ~a 的数字。 ，包括在内，其中 1 位的计数由 solve(|a| - 1) = solve(~a) 给出.