15

この問題は、2011 Codesprint ( http://csfall11.interviewstreet.com/ ) からのものです。

コンピュータ サイエンスの基本の 1 つは、数値が 2 の補数でどのように表されるかを知ることです。A から B までのすべての数値を 2 の補数表現で 32 ビットを使用して書き留めるとします。全部で何個の 1 を書き留めますか? 入力: 最初の行には、テスト ケースの数 T (<1000) が含まれます。次の各 T 行には、2 つの整数 A と B が含まれます。 出力: 各テスト ケースに対応する T 行を出力します。制約: -2^31 <= A <= B <= 2^31 - 1

サンプル入力: 3 -2 0 -3 4 -1 4 サンプル出力: 63 99 37

説明: 最初のケースでは、-2 には 31 個の 1 が含まれ、その後に 0 が続きます。-1 には 32 個の 1 が含まれ、0 には 0 個の 1 が含まれます。したがって、合計は 63 です。2 番目のケースの場合、答えは 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99 です。

-X の 1 の数と (-X) = X-1 の補数の 0 の数が等しいという事実を利用して、検索を高速化できることがわかりました。解決策は、答えを生成するための O(log X) 再帰関係があると主張していますが、私はそれを理解していません。ソリューション コードは、 https ://gist.github.com/1285119 で確認できます。

この関係がどのように導き出されるかを誰かが説明できれば幸いです!

4

4 に答える 4

31

うーん、そんなに複雑じゃない…

単一引数solve(int a)関数が鍵です。短いのでカット＆ペーストします。

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) ;
}

負でない a に対してのみ機能し、0 から 0 までのすべての整数の 1 ビットの数をカウントしますa。

関数には 3 つのケースがあります。

a == 0-> 0 を返します。

aaeven -> plusの 1 ビットの数を返しますsolve(a-1)。また、かなり明白です。

最後のケースは興味深いものです。では、0 から奇数までの 1 ビットの数をどのように数えますaか?

0 から までのすべての整数を考えて、aそれらを偶数と奇数の 2 つのグループに分けます。たとえば、aが 5 の場合、2 つのグループ (バイナリ) があります。

000  (aka. 0)
010  (aka. 2)
100  (aka. 4)

と

001  (aka 1)
011  (aka 3)
101  (aka 5)

これら 2 つのグループは同じサイズでなければならないことに注意してください (aは奇数であり、範囲は包括的であるため)。各グループに 1 のビットがいくつあるかをカウントするには、最初に最後のビットを除くすべてのビットをカウントし、次に最後のビットをカウントします。

最後のビットを除くすべては次のようになります。

00
01
10

...そして、両方のグループで次のようになります。ここの 1 ビットの数はちょうどsolve(a/2)です。(この例では、0 から 2 までの 1 ビットの数です。また、C/C++ の整数除算は切り捨てられることを思い出してください。)

最後のビットは、最初のグループのすべての数値でゼロであり、2 番目のグループのすべての数値で 1 であるため、それらの最後のビット(a+1)/2は合計に 1 ビット寄与します。

したがって、再帰の 3 番目のケースは であり(a+1)/2 + 2*solve(a/2)、適切なキャストを使用して、 is (したがってオーバーフロー)long longのケースを処理します。aINT_MAXa+1

これは O(log N) ソリューションです。に一般化するには、 に加えて、負の数を心配するための適切なロジックをsolve(a,b)計算するだけです。solve(b) - solve(a)それが、2 つの引数solve(int a, int b)が行っていることです。

于 2011-10-30T04:21:58.283 に答える
3

配列を一連の整数にキャストします。次に、整数ごとに次のようにします。

int NumberOfSetBits(int i)
{
   i = i - ((i >> 1) & 0x55555555);
   i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
   return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

また、__builtin_popcount とは異なり、これは移植可能です。

ここを参照してください: 32 ビット整数で設定されたビット数をカウントする方法は?

于 2012-06-21T20:05:54.853 に答える
2

a が正の場合、より適切な説明が既に投稿されています。

a が負の場合、32 ビット システムでは、a と 0 の間の各負の数は、0 から正の a のバイナリ表現までの範囲のビット数を差し引いた 32 個の 1 のビットを持ちます。

だから、より良い方法で、

long long solve(int a) {
    if (a >= 0){
        if (a == 0) return 0;
        else if ((a %2) == 0) return solve(a - 1) + noOfSetBits(a);
        else return (2 * solve( a / 2)) + ((long long)a + 1) / 2;
    }else {
        a++;
        return ((long long)(-a) + 1) * 32 - solve(-a);
    }
}
于 2013-10-12T14:54:29.650 に答える
1

次のコードでは、x のビットサムは、0 から x (両端を含む) までの数値の 2 の補数表現における 1 ビットのカウントとして定義されます。ここで、Integer.MIN_VALUE <= x <= Integer.MAX_VALUE です。

例えば：

bitsum(0) is 0   
bitsum(1) is 1   
bitsum(2) is 1   
bitsum(3) is 4

..等

10987654321098765432109876543210 i % 10 for 0 <= i <= 31
00000000000000000000000000000000 0
00000000000000000000000000000001 1
00000000000000000000000000000010 2
00000000000000000000000000000011 3
00000000000000000000000000000100 4
00000000000000000000000000000101 ...
00000000000000000000000000000110
00000000000000000000000000000111 (2^i)-1
00000000000000000000000000001000  2^i
00000000000000000000000000001001 (2^i)+1 
00000000000000000000000000001010 ...
00000000000000000000000000001011 x, 011 = x & (2^i)-1 = 3
00000000000000000000000000001100
00000000000000000000000000001101
00000000000000000000000000001110
00000000000000000000000000001111
00000000000000000000000000010000
00000000000000000000000000010001
00000000000000000000000000010010 18
...
01111111111111111111111111111111 Integer.MAX_VALUE

ビットサムの式は次のとおりです。

bitsum(x) = bitsum((2^i)-1) + 1 + x - 2^i + bitsum(x & (2^i)-1 )

x - 2^i = x & (2^i)-1 であることに注意してください。

負の数は、正の数とは少し異なる方法で処理されます。この場合、ビットの総数からゼロの数が差し引かれます。

Integer.MIN_VALUE <= x < -1
Total number of bits: 32 * -x.

負の数 x のゼロの数は、-x - 1 の 1 の数と同じです。

public class TwosComplement {
    //t[i] is the bitsum of (2^i)-1 for i in 0 to 31.
    private static long[] t = new long[32];
    static {
        t[0] = 0;
        t[1] = 1;
        int p = 2;
        for (int i = 2; i < 32; i++) {
            t[i] = 2*t[i-1] + p;
            p = p << 1;
        }
    }

    //count the bits between x and y inclusive
    public static long bitsum(int x, int y) {
        if (y > x && x > 0) {
            return bitsum(y) - bitsum(x-1);
        }
        else if (y >= 0 && x == 0) {
            return bitsum(y);
        }
        else if (y == x) {
            return Integer.bitCount(y);
        }
        else if (x < 0 && y == 0) {
            return bitsum(x);
        } else if (x < 0 && x < y && y < 0 ) {
            return bitsum(x) - bitsum(y+1);
        } else if (x < 0 && x < y && 0 < y) {
            return bitsum(x) + bitsum(y);
        }
        throw new RuntimeException(x + " " + y);
    }

    //count the bits between 0 and x
    public static long bitsum(int x) {
        if (x == 0) return 0;
        if (x < 0) {
            if (x == -1) {
                return 32;
            } else {
                long y = -(long)x;
                return 32 * y - bitsum((int)(y - 1));
            }
        } else {
            int n = x;
            int sum = 0;     //x & (2^i)-1
            int j = 0;
            int i = 1;       //i = 2^j
            int lsb = n & 1; //least significant bit
            n = n >>> 1;
            while (n != 0) {
                sum += lsb * i;
                lsb = n & 1;
                n = n >>> 1;
                i = i << 1;
                j++;
            }
            long tot = t[j] + 1 + sum + bitsum(sum);
            return tot;
        }
    }
}
于 2016-08-04T03:13:45.833 に答える