-3

この質問はインタビューで尋ねられたものですが、次のコードが何をするのか誰か教えていただけますか? 150 の場合は 15、160 の場合は 3、15 の場合は 15 という出力が得られます。「n」に対して実行される数学演算は何ですか。

int foo(int n) 
{
    int t,count=0;
    t=n;
    while(n)
    {
        count=count+1;
        n=(n-1)&t;
    }
    return count;
}
4

3 に答える 3

1

number を計算するようですmax(n**2-1, 0)。ここで、n は1数値のバイナリ表現のビット数です。

    0     0 0b0  
    1     1 0b1  
    2     1 0b10 
    3     3 0b11 
    4     1 0b100
    5     3 0b101
    6     3 0b110
    7     7 0b111
    8     1 0b1000
    9     3 0b1001
   10     3 0b1010
   11     7 0b1011
   12     3 0b1100
   13     7 0b1101
   14     7 0b1110
   15    15 0b1111
   16     1 0b10000
   17     3 0b10001
   18     3 0b10010
   19     7 0b10011
   20     3 0b10100
   21     7 0b10101
   22     7 0b10110
   23    15 0b10111
   24     3 0b11000
   25     7 0b11001
   26     7 0b11010
   27    15 0b11011
   28     7 0b11100
   29    15 0b11101
   30    15 0b11110
   31    31 0b11111
   32     1 0b100000
   33     3 0b100001
   34     3 0b100010
   35     7 0b100011
   36     3 0b100100
   37     7 0b100101
   38     7 0b100110
   39    15 0b100111
   40     3 0b101000
   41     7 0b101001
   42     7 0b101010
   43    15 0b101011
   44     7 0b101100
   45    15 0b101101
   46    15 0b101110
   47    31 0b101111
   48     3 0b110000
   49     7 0b110001
   50     7 0b110010
   51    15 0b110011
   52     7 0b110100
   53    15 0b110101
   54    15 0b110110
   55    31 0b110111
   56     7 0b111000
   57    15 0b111001
   58    15 0b111010
   59    31 0b111011
   60    15 0b111100
   61    31 0b111101
   62    31 0b111110
   63    63 0b111111
   64     1 0b1000000
   65     3 0b1000001
   66     3 0b1000010
   67     7 0b1000011
   68     3 0b1000100
   69     7 0b1000101
   70     7 0b1000110
   71    15 0b1000111
   72     3 0b1001000
   73     7 0b1001001
   74     7 0b1001010
   75    15 0b1001011
   76     7 0b1001100
   77    15 0b1001101
   78    15 0b1001110
   79    31 0b1001111
   80     3 0b1010000
   81     7 0b1010001
   82     7 0b1010010
   83    15 0b1010011
   84     7 0b1010100
   85    15 0b1010101
   86    15 0b1010110
   87    31 0b1010111
   88     7 0b1011000
   89    15 0b1011001
   90    15 0b1011010
   91    31 0b1011011
   92    15 0b1011100
   93    31 0b1011101
   94    31 0b1011110
   95    63 0b1011111
   96     3 0b1100000
   97     7 0b1100001
   98     7 0b1100010
   99    15 0b1100011
于 2012-07-26T11:05:29.487 に答える
0

これは、設定されたビットを数えるブライアン・カーニハンの方法として知られている方法です:

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Brian Kernighan の方法は、設定されたビットの数だけ反復されます。そのため、上位ビットのみが設定された 32 ビット ワードがある場合、それはループを 1 回だけ通過します。

1988 年に発行された C プログラミング言語第 2 版。(Brian W. Kernighan と Dennis M. Ritchie による) 演習 2-9 でこれについて言及しています。2006 年 4 月 19 日、Don Knuth は私に、この方法は「CACM 3 (1960), 322 で Peter Wegner によって最初に公開されたものである」と指摘しました。

于 2013-01-31T14:31:56.290 に答える
0

関数が再帰的に変更されると、「数学演算」を見つけやすくなります。

int foo(int n, int t) 
{
    if( n )
        return foo( (n-1) & t ) + 1
    else
        return 0; 
}

したがって、式は次のとおりです。

F(0,t) = 0
F(n,t) = F( (n-1) & t, t ) + 1

foo(n) = F(n,n)

何かを数えるためのよく知られた公式かどうかはわかりません。

math.stackexchange.comから回答が見つかるかもしれません

于 2012-07-26T11:09:00.073 に答える