计数整数的二的补重新presentations 1秒在范围[X，Y] [英] Counting 1s in the two's complement representations of integers in range[x,y]

问题描述

我的问题是有关在论坛里previous的问题 - <一href="http://stackoverflow.com/questions/7942732/number-of-1s-in-the-twos-complement-binary-re$p$psentations-of-integers-in-a-ran">Number 1秒中的整数的二进制补码重新presentations的范围来 有没有'添加评论'的me.So我问在这里 问题是要计算写下在2的补码形式的所有数字，它们是由两个输入号码中指定的范围内的1的数 该解决方案张贴在 https://gist.github.com/1285119  这是因为以下

My question is related to a previous question in the forum - Number of 1s in the two's complement binary representations of integers in a range There was no 'add comment' for me.So i am asking it here The question was to count the number of 1's in writing down all numbers in 2's complement form,which are in a range specified by two input numbers The solution is posted at https://gist.github.com/1285119 It is as below

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 //没有测试用例

When the input is 4 //No of test cases

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

-1 //first number -2 //Second number Output 0

-1 -3  输出-31

-1 -3 Output -31

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

-3 -5 Output -30 //how can number of 1's be -30

1 2 输出2

由于code被张贴作为InterviewStreet codesprint解决方案，并在此forum.It高度投票的答案应该是正确的。 谁能解释线背后的逻辑 长长的RET =（32LL * - （久长）一） - 解决（〜一）解决（INT A，INT B） 什么是的#define INF（INT）1E9的目的//在不使用时将其设置为无穷大的价值？

Since the code is posted as Codesprint solutions on InterviewStreet and a highly voted answer on this forum.It should have been correct. Can anyone explain the logic behind the line long long ret = (32LL * -(long long)a) - solve(~a) in solve(int a,int b) And what is the purpose of #define INF (int)1e9 //setting value of infinity when not using it?

推荐答案

错误的结果您输入

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

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

are because the programme assumes that the two limits are entered in ascending order and does no checks, therefore input not conforming to that expectation produces wrong results. A simple

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

在 INT的开始解决（INT A，INT B）将使其在任何命令返回正确的结果输入。

at the beginning of int solve(int a, int b) would make it return the correct result for input in any order.

背后的逻辑很长很长RET =（32LL * - （久长）一） - 解决（〜A）是（三三两两的补）位元补对 N 是〜N =（-N）-1 。位的总数量（0或1）从 A 到 1 数字 - 无论是包容性 - 是 32 * | A | 如果 A＆LT; 0 。从该计数，我们减去0位在这些数字的总数，这是1位在​​其按位补码的总数。这些位补码是从0到号码| A | - 1 =〜一个，包括两端，1位在这些计数是由给予解决（| A | - 1）=求解（〜A）。

The logic behind long long ret = (32LL * -(long long)a) - solve(~a) is that (in twos' complement) the bitwise complement of n is ~n = (-n)-1. The total number of bits (0 or 1) in the numbers from a to -1 - both inclusive - is 32 * |a| if a < 0. From that count, we subtract the total number of 0 bits in these numbers, which is the total number of 1-bits in their bitwise complements. These bitwise complements are the numbers from 0 to |a| - 1 = ~a, both inclusive, the count of 1-bits among these is given by solve(|a| - 1) = solve(~a).

这篇关于计数整数的二的补重新presentations 1秒在范围[X，Y]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！