c********t
发帖数: 5706 | |
d**********x
发帖数: 4083 | 2 要不怎么做呢
【在 c********t 的大作中提到】
: 碰到这题，你们都是给O(lgN)的解法吗？
|
c********t
发帖数: 5706 | 3 搜搜吧，好像有O(1)的解法
【在 d**********x 的大作中提到】
: 要不怎么做呢
|
f*****e
发帖数: 2992 | 4 popcount?汇编指令？
【在 c********t 的大作中提到】
: 搜搜吧，好像有O(1)的解法
|
d*******u
发帖数: 186 | 5 uint numofone(int n)
{
unsigned long absn;
if(n<0)
absn = -n;
else
absn = n;
int count =0;
int mod = 1;
while(absn!=0)
{
if(mod & absn)
count++;
absn= absn>>1;
}
return count;
}
【在 c********t 的大作中提到】
: 碰到这题，你们都是给O(lgN)的解法吗？
|
k****r
发帖数: 807 | 6 被2除看余数吗？余数是1,counter＋＋，商继续直到为1 |
l*****a
发帖数: 559 | 7 怎么做都是lg（n）。
n为该数十进制的值，
bit的个数为lg（n）。 |
d**********x
发帖数: 4083 | 8 对了，你这里的N指的是位数吧
【在 c********t 的大作中提到】
: 碰到这题，你们都是给O(lgN)的解法吗？
|
d**********x
发帖数: 4083 | 9 不是的，n指的是2进制位数
【在 l*****a 的大作中提到】
: 怎么做都是lg（n）。
: n为该数十进制的值，
: bit的个数为lg（n）。
|
l*****a
发帖数: 559 | 10 如果n是二进制的位数，数个数总得访问一遍吧。
这一个访问就是O（n）。
【在 d**********x 的大作中提到】
: 不是的，n指的是2进制位数
|
|
|
b*****e
发帖数: 131 | |
d**********x
发帖数: 4083 | 12 奇数位和偶数位相加，然后mask
然后每4位，2位2位相加，mask...
【在 l*****a 的大作中提到】
: 如果n是二进制的位数，数个数总得访问一遍吧。
: 这一个访问就是O（n）。
|
l*******b
发帖数: 2586 | 13 int getBitsOne(int c)
{
c = ((c & 0xaaaaaaaa)>>1) + (c & 0x55555555);
c = ((c & 0xcccccccc)>>2) + (c & 0x33333333);
c = ((c & 0xf0f0f0f0)>>4) + (c & 0x0f0f0f0f);
c = ((c & 0xff00ff00)>>8) + (c & 0x00ff00ff);
c = ((c & 0xffff0000)>>16) + (c & 0x0000ffff);
return c;
} |
d**********x
发帖数: 4083 | 14 can u do it better?
【在 l*******b 的大作中提到】
: int getBitsOne(int c)
: {
: c = ((c & 0xaaaaaaaa)>>1) + (c & 0x55555555);
: c = ((c & 0xcccccccc)>>2) + (c & 0x33333333);
: c = ((c & 0xf0f0f0f0)>>4) + (c & 0x0f0f0f0f);
: c = ((c & 0xff00ff00)>>8) + (c & 0x00ff00ff);
: c = ((c & 0xffff0000)>>16) + (c & 0x0000ffff);
: return c;
: }
|
l*******b
发帖数: 2586 | 15 想不出来了。。
【在 d**********x 的大作中提到】
: can u do it better?
|
l*****a
发帖数: 559 | 16 这只能去掉最后一位1。如果全是1，还是O（n）。
【在 b*****e 的大作中提到】
: 移位神马的弱爆了，用这个: x&(x-1)
|
d**********x
发帖数: 4083 | 17 没事，只是中间两步可以不用mask...
【在 l*******b 的大作中提到】
: 想不出来了。。
|
l*****a
发帖数: 559 | 18 碰上一个未知位数的值，如何初始化mask？
对于int，long long等已知type，mask 都是hard coded的。
修改：看道题目说是整数，算是已知type的。
【在 d**********x 的大作中提到】
: 奇数位和偶数位相加，然后mask
: 然后每4位，2位2位相加，mask...
|
r**********g
发帖数: 22734 | 19 No, it is already the best.
【在 d**********x 的大作中提到】
: can u do it better?
|
c********t
发帖数: 5706 | 20 lanmama说得对，N为该数十进制的值
【在 d**********x 的大作中提到】
: 对了，你这里的N指的是位数吧
|
|
|
c********t
发帖数: 5706 | 21 正解！
我电面被问到，给了lg(n)解法，bug free,对方似乎不太满意啊。
问一下如果没做过，有人能直接给这个解吗？还是我bit operation太弱？
【在 l*******b 的大作中提到】
: int getBitsOne(int c)
: {
: c = ((c & 0xaaaaaaaa)>>1) + (c & 0x55555555);
: c = ((c & 0xcccccccc)>>2) + (c & 0x33333333);
: c = ((c & 0xf0f0f0f0)>>4) + (c & 0x0f0f0f0f);
: c = ((c & 0xff00ff00)>>8) + (c & 0x00ff00ff);
: c = ((c & 0xffff0000)>>16) + (c & 0x0000ffff);
: return c;
: }
|
d**********x
发帖数: 4083 | 22 如果你看过hacker's delight或者cs:app的话。。
尤其是cs:app第一章或者第二章，常用的这些trick基本都在那了
【在 c********t 的大作中提到】
: 正解！
: 我电面被问到，给了lg(n)解法，bug free,对方似乎不太满意啊。
: 问一下如果没做过，有人能直接给这个解吗？还是我bit operation太弱？
|
c********t
发帖数: 5706 | 23 嗯，还真没看过。认栽了！move on了，继续学习。
【在 d**********x 的大作中提到】
: 如果你看过hacker's delight或者cs:app的话。。
: 尤其是cs:app第一章或者第二章，常用的这些trick基本都在那了
|
l*******b
发帖数: 2586 | 24 这个其实也是log n的解法呀，n = 32位算5步对应log 32, 更好的不知道了。。
多看看就知道了吧，和教calculus的学生一样，总问这个有什么一般的方法，那只好告
诉他们把吉米多维奇上的积分都解了就可以了，哈哈 |
d**********x
发帖数: 4083 | 25 in terms of big-O, it's best
but 2 less operations is already a big improvement in this case.
【在 r**********g 的大作中提到】
: No, it is already the best.
|
d**********x
发帖数: 4083 | 26 加油，这种东西就是见过没见过而已
当年别人也用这个打击我来着。。
【在 c********t 的大作中提到】
: 嗯，还真没看过。认栽了！move on了，继续学习。
|
c********t
发帖数: 5706 | 27 这个是明确的 O(5) = O(1)
mod或者右移位，要看整数N大小， 虽然也不过是0--32之间，但确实是O(logN)
关键话语权不在我这边啊。
【在 l*******b 的大作中提到】
: 这个其实也是log n的解法呀，n = 32位算5步对应log 32, 更好的不知道了。。
: 多看看就知道了吧，和教calculus的学生一样，总问这个有什么一般的方法，那只好告
: 诉他们把吉米多维奇上的积分都解了就可以了，哈哈
|
h****n
发帖数: 1093 | 28 what about this algorithm?
int GetBitsNum(int num)
{
int res = 0;
while(num)
{
res++;
num &= (num-1);
}
return res;
}
It should be better that log N, the number of operation is only proportional
to the number of 1 bit in the binary representation.
for example, if input is 1000000, then only one iteration is enough.
if input is 1100000, then two iterations and so on.
Of course, you can achieve real O(1) complexity by creating a huge hashtable
for all the possible integers in advance. |
d**********x
发帖数: 4083 | 29 不是这个意思。。
如果你说这个是O(5)，那你的原算法就是O(32)之类的
肯定要定一个变量。。。
好告
【在 c********t 的大作中提到】
: 这个是明确的 O(5) = O(1)
: mod或者右移位，要看整数N大小， 虽然也不过是0--32之间，但确实是O(logN)
: 关键话语权不在我这边啊。
|
c********t
发帖数: 5706 | 30 顶！
虽然O(number of 1)=O(log(N)) 但是很不错的improve,可能我当时能给出这个解，也
会让他比较满意。
【在 h****n 的大作中提到】
: what about this algorithm?
: int GetBitsNum(int num)
: {
: int res = 0;
: while(num)
: {
: res++;
: num &= (num-1);
: }
: return res;
|
|
|
Q*******e
发帖数: 939 | 31 cnt = 0;
while (x) {
cnt++;
x &= (x-1);
} |
b*****e
发帖数: 131 | 32 1. 你确定你知道什么是big O？
2. 如果全1，你用什么算法比我的快？
【在 l*****a 的大作中提到】
: 这只能去掉最后一位1。如果全是1，还是O（n）。
|
