这个问题是在采访中被问到的，有人能说出下面的代码是做什么的吗？它为 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;
}
问问题
379 次
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
这是一种被称为Brian Kernighan 的方法来计算设置位：
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 位字，那么它只会通过循环一次。
1988 年出版的 C 程序设计语言第 2 版。（由 Brian W. Kernighan 和 Dennis M. Ritchie 撰写）在练习 2-9 中提到了这一点。2006 年 4 月 19 日，Don Knuth 向我指出，这种方法“由 Peter Wegner 在 CACM 3 (1960), 322 中首次发表。（也由 Derrick Lehmer 独立发现，并于 1964 年在 Beckenbach 编辑的书中发表。）”
于 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)
我不知道，那个著名的计算公式是不是。
于 2012-07-26T11:09:00.073 回答