1

私の質問は、フォーラムの前の質問に関連してい ます-2の補数の範囲内の整数の2の補数表現の1の数 「コメントを追加」はありませんでした。 2の補数形式ですべての数値を書き留める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//2番目の数値出力0

-1-3出力-31

-3-5出力-30//1の数を-30にするにはどうすればよいですか

12出力2

コードはInterviewStreetにCodesprintソリューションとして投稿されており、このフォーラムで非常に投票された回答であるため、正しいはずです。誰かが行の背後にあるロジックを説明できますかlonglongret =（32LL *-（long long）a）-solve（int a、int b）のsolve（〜a）そして#define INF（int）1e9の目的は何ですか//使用しないときに無限大の値を設定しますか？

4

1 に答える 1

0

入力に対する間違った結果

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

これは、プログラムが 2 つの制限が昇順で入力されていると想定し、チェックを行わないためです。したがって、その期待に準拠しない入力は間違った結果をもたらします。シンプルな

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)は、(2 の補数で) のビット単位の補数はnです~n = (-n)-1。aからまでの数値のビット (0 または 1) の総数 (-1両方を含む) は32 * |a|、 ifa < 0です。そのカウントから、これらの数値の 0 ビットの総数を引きます。これは、ビットごとの補数の 1 ビットの総数です。これらのビット単位の補数は 0 から までの数値であり、|a| - 1 = ~aこれらの 1 ビットの数は で与えられsolve(|a| - 1) = solve(~a)ます。

于 2012-04-03T22:54:19.667 に答える