回复： [TopLanguage] 鎴戜篃鏉ュ嚭涓ソ鐜╃殑棰? type =3D?=

[Llh]

时间空间的要求？

SpitFire <spit...@gmail.com> 写道：

计算出正整数N二进制1的个数

--
SpitFire

---

@yahoo.cn 新域名、无限量，快来抢注！

[SpitFire]

时间要求是不大于二进制1的个数,空间是1

在07-11-15，Llh <lin...@yahoo.cn> 写道：

--
SpitFire

[Yong Yuan]

俺没有时间解题。不过这些都是现成算法，所以贡献几个有名的：

 

Kernighan老大滴。The C Programming Language 上有（要不怎么是宝书嗫？）：

 

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
}

 

32位专用:

v = v - ((v >> 1) & 0x55555555);                                   // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);           // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;    // count

[pongba]

On Nov 15, 2007 11:53 PM, Yong Yuan <y...@cs.toronto.edu> wrote:

俺没有时间解题。不过这些都是现成算法，所以贡献几个有名的：

 

Kernighan老大滴。The C Programming Language 上有（要不怎么是宝书嗫？）：

 

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
}

 

这招实在是很强大..
 

32位专用:

v = v - ((v >> 1) & 0x55555555);                                   // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);           // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;    // count

 

On Nov 15, 2007 4:58 AM, Llh <lin...@yahoo.cn> wrote:

时间空间的要求？

SpitFire <spit...@gmail.com > 写道：

计算出正整数N二进制1的个数

--
SpitFire

---

@yahoo.cn 新域名、无限量，快来抢注！

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[莫华枫]

有人说说他们是怎么想出来的吗？

--
反者道之动，弱者道之用
m...@seaskysh.com
longsh...@gmail.com
http://blog.csdn.net/longshanks/

[Googol Lee]

hacker's delight......

On Nov 16, 3:24 pm, "莫华枫" <longshank...@gmail.com> wrote:
> 有人说说他们是怎么想出来的吗？
>
> On Nov 16, 2007 2:51 PM, pongba <pon...@gmail.com> wrote:
>
>
>
>
>
> > On Nov 15, 2007 11:53 PM, Yong Yuan <y...@cs.toronto.edu> wrote:
>
> > > 俺没有时间解题。不过这些都是现成算法，所以贡献几个有名的：
>
> > > Kernighan老大滴。The C Programming Language 上有（要不怎么是宝书嗫？）：
>
> > > 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
> > > }
>
> > 这招实在是很强大..
>
> > > 32位专用:
> > > v = v - ((v >> 1) & 0x55555555); //
> > reuse input as temporary
> > > v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
> > > c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
>
> > > On Nov 15, 2007 4:58 AM, Llh <lin...@yahoo.cn> wrote:
>
> > > > 时间空间的要求？
>

> > > > SpitFire <spitfi...@gmail.com > 写道：

> > > > 计算出正整数N二进制1的个数
>
> > > > --
> > > > SpitFire
> > > > ________________________________
> > @yahoo.cn 新域名、无限量，快来抢注！
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
>
> >http://blog.csdn.net/pongba
> > TopLanguage
>
> > http://groups.google.com/group/pongba
>
> --
> 反者道之动，弱者道之用
> m...@seaskysh.com

> longshank...@gmail.comhttp://blog.csdn.net/longshanks/

[pongba]

On Nov 16, 2007 3:24 PM, 莫华枫 <longsh...@gmail.com> wrote:

有人说说他们是怎么想出来的吗？

首先，我们有一个异或操作，然后我们研究异或操作的性质，比如0^R=R。R^R=0，交换率结合律等等。
其中性质之一就是v^v-1会将最后一个有效位消去，这一点性质不难得到。基于这一点性质，就像构造谜语一样，可以构造出这个题目，这也不难构造。
然后，对于解题者，则需要通过这个题目，去搜索解空间，这就难多了。如果这个解题者是熟悉异或操作的性质的，那么很可能他立即就会意识到这个解法。然后你问他他可能答"直觉呗"，然后你就被打击了。
实际上，这个直觉是知识量决定的。（也有直觉是逻辑训练积累决定的）

反过来求解问题就跟做除法一样，复杂度比正向思考（乘法）难多了，因为搜索空间大，而且如果没有异或操作的性质这方面的知识的话，你甚至根本没法往下思考一步。

[hayate]

根本没看懂
每一行到底是啥意思 最郁闷这种玩弄bits的代码了 :(

On Nov 16, 2007 3:24 PM, 莫华枫 <longsh...@gmail.com> wrote:

[hayate]

en 这是比较科学的办法 我也尝试过去查阅异或的代数性质 但是已有的经验和知识量与最终解决问题到底有怎样的关系还不明确

不禁让我想起来了 哥德尔不完备性原理

[莫华枫]

我真的被打击了。:-D

On Nov 16, 2007 4:11 PM, pongba <pon...@gmail.com> wrote:
>
>

--

[li jiecong]

从小就知道 3＋4＝4＋3

但我是学线性代数的时候才知道交换律 结合律

很多老师该换换了 这些老师导致我们缺乏基本素养！

不过我还是没想明白自然界为什么会有 交换律 结合律 这个规律？
 

[王宁]

费曼同学的自传里有不少这样的例子

On 11/16/07, 莫华枫 <longsh...@gmail.com> wrote:

[pongba]

On 11/16/07, hayate <haya...@gmail.com> wrote:
> en 这是比较科学的办法 我也尝试过去查阅异或的代数性质 但是已有的经验和知识量与最终解决问题到底有怎样的关系还不明确

问题是，对于一个不知道异或的那四个关键性质的人来说。他又怎么会想到异或上去呢？
这类问题的特点就是与既有知识的挂钩非常紧密。并非可以通过系统化思维过程来逐步逼近（并在逼近的过程中根据需要查阅新知识）解的。

然而，在已经知道了第一种情况的解决方案之后，当问题扩展到第二种情况（即有两个数只出现一次时），就体现出思维的能力了，也就是打击人的地方了。

[hayate]

这个论题太复杂了....
我想任何人思考的过程 都受太多因素的影响 单纯地讨论哪些是因为现有知识的积累 哪些是灵感的迸发 都不确切

比如有时候死也想不出一道题，但是睡一觉之后就突然想出答案。碰到这种情况，我也不禁怀疑自己，到底自己真的想得出这个问题吗？

[wizard]

乘法 (加法) 结合律、交换律，这是小学数学课本的基本内容……怎么可能没有教给你。

在07-11-16，li jiecong <liji...@gmail.com> 写道：

[meta]

http://infolab.stanford.edu/~manku/bitcount/bitcount.html

On Nov 16, 3:24 pm, "莫华枫" <longshank...@gmail.com> wrote:

> 有人说说他们是怎么想出来的吗？
>
> On Nov 16, 2007 2:51 PM, pongba <pon...@gmail.com> wrote:
>
>
>
>
>
> > On Nov 15, 2007 11:53 PM, Yong Yuan <y...@cs.toronto.edu> wrote:
>
> > > 俺没有时间解题。不过这些都是现成算法，所以贡献几个有名的：
>
> > > Kernighan老大滴。The C Programming Language 上有（要不怎么是宝书嗫？）：
>
> > > 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
> > > }
>
> > 这招实在是很强大..
>
> > > 32位专用:
> > > v = v - ((v >> 1) & 0x55555555); //
> > reuse input as temporary
> > > v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
> > > c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
>
> > > On Nov 15, 2007 4:58 AM, Llh <lin...@yahoo.cn> wrote:
>
> > > > 时间空间的要求？
>

> > > > SpitFire <spitfi...@gmail.com > 写道：

> > > > 计算出正整数N二进制1的个数
>
> > > > --
> > > > SpitFire
> > > > ________________________________
> > @yahoo.cn 新域名、无限量，快来抢注！
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
>
> >http://blog.csdn.net/pongba
> > TopLanguage
>
> > http://groups.google.com/group/pongba
>
> --
> 反者道之动，弱者道之用
> m...@seaskysh.com

> longshank...@gmail.comhttp://blog.csdn.net/longshanks/

[meta]

附加HAKMEN手册：
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html

[pongba]

meta兄要么不冒泡，一出手就是两份重要资源啊:-)

附加HAKMEN手册：
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html

TopLanguage
http://groups.google.com/group/pongba