如何计算某char变量bit位为1的总数目？

bsdc

还是x & (x - 1)比较有效率，相比移位来讲，查表意义不大吧，还得去构造一个数组

呵呵，这题目怎么经常面试到，还有反转位序，反转链表之类

aaaaa5aa

七楼的方法比较好

nuying117

原帖由 sunchiang 于 2009-6-25 13:21 发表
把所有可能存进一个数组，直接查表，不知道我的意思你明白不？

那人家如果让你计算一个int型的数里面的1的个数，你也查表啊

mgqw

原帖由 bruceteen 于 2009-6-25 09:33 发表
size_t func( char x )
{
    x = (x & 0x55) + ((x>>1) & 0x55);
    x = (x & 0x33) + ((x>>2) & 0x33);
    x = (x & 0x0f) + ((x>>4) & 0x0f);

    return x;
}

#include
using namespace std ...

这个算法看着迷糊，能否说一下原理

eveson

x & (x - 1)和移位哪个效率高？怎么确定的

daybreakcx

原帖由 eveson 于 2009-6-25 16:24 发表
x & (x - 1)和移位哪个效率高？怎么确定的

前者，前者算的是O(n)（n是1个数），后者是O(m)（m是位数），特别是稀疏的时候前者高，但是位数比较少其实都差不多

JohnBull

谁说查表法没意义？禁止误导初学者！

int型怎么了？你不会查4次啊？笨！

nuying117

原帖由 JohnBull 于 2009-6-25 18:07 发表
谁说查表法没意义？禁止误导初学者！

int型怎么了？你不会查4次啊？笨！

对对对，牛逼！

咱当时没想到。不好意思。

foolishx

某年某次的某个面试中，我也遇到过这个问题，当时顺手就写了一个移位的程序，后来发现的确好多地方可以优化。

个为认为查表是比较好的，时间复杂度比较小。

yulihua49

原帖由 bsdc 于 2009-6-25 14:06 发表
还是x & (x - 1)比较有效率，相比移位来讲，查表意义不大吧，还得去构造一个数组

呵呵，这题目怎么经常面试到，还有反转位序，反转链表之类

你这个方法好！