s*n
2 楼
刚腾出来一小块地，不知道种啥，感觉毛豆或者花生挺好管理的，五区现在种毛豆花生
来得及吗？
来得及吗？
d*x
3 楼
要不怎么做呢
【在 c********t 的大作中提到】
: 碰到这题，你们都是给O(lgN)的解法吗？
【在 c********t 的大作中提到】
: 碰到这题，你们都是给O(lgN)的解法吗？
f*l
4 楼
好像还凑合，看了一下毛豆成熟天数是75天左右
【在 s*****n 的大作中提到】
: 刚腾出来一小块地，不知道种啥，感觉毛豆或者花生挺好管理的，五区现在种毛豆花生
: 来得及吗？
【在 s*****n 的大作中提到】
: 刚腾出来一小块地，不知道种啥，感觉毛豆或者花生挺好管理的，五区现在种毛豆花生
: 来得及吗？
c*t
5 楼
搜搜吧，好像有O(1)的解法
【在 d**********x 的大作中提到】
: 要不怎么做呢
【在 d**********x 的大作中提到】
: 要不怎么做呢
s*n
6 楼
还还来得及呢，今天就去买种子去。
：好像还凑合，看了一下毛豆成熟天数是75天左右
：☆ 发自 iPhone 买买提 1.23.04
【在 f****l 的大作中提到】
: 好像还凑合，看了一下毛豆成熟天数是75天左右
：好像还凑合，看了一下毛豆成熟天数是75天左右
：☆ 发自 iPhone 买买提 1.23.04
【在 f****l 的大作中提到】
: 好像还凑合，看了一下毛豆成熟天数是75天左右
f*e
7 楼
popcount?汇编指令？
【在 c********t 的大作中提到】
: 搜搜吧，好像有O(1)的解法
【在 c********t 的大作中提到】
: 搜搜吧，好像有O(1)的解法
c*d
8 楼
去年蓝星好像是六月初播的，八月底收的
所以我觉得你可能来不及了
【在 s*****n 的大作中提到】
: 刚腾出来一小块地，不知道种啥，感觉毛豆或者花生挺好管理的，五区现在种毛豆花生
: 来得及吗？
所以我觉得你可能来不及了
【在 s*****n 的大作中提到】
: 刚腾出来一小块地，不知道种啥，感觉毛豆或者花生挺好管理的，五区现在种毛豆花生
: 来得及吗？
d*u
9 楼
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)的解法吗？
{
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)的解法吗？
f*p
10 楼
藍星忽悠妳們呢！
【在 c******d 的大作中提到】
: 去年蓝星好像是六月初播的，八月底收的
: 所以我觉得你可能来不及了
【在 c******d 的大作中提到】
: 去年蓝星好像是六月初播的，八月底收的
: 所以我觉得你可能来不及了
k*r
11 楼
被2除看余数吗？余数是1,counter＋＋，商继续直到为1
l*a
12 楼
怎么做都是lg（n）。
n为该数十进制的值，
bit的个数为lg（n）。
n为该数十进制的值，
bit的个数为lg（n）。
d*x
13 楼
对了，你这里的N指的是位数吧
【在 c********t 的大作中提到】
: 碰到这题，你们都是给O(lgN)的解法吗？
【在 c********t 的大作中提到】
: 碰到这题，你们都是给O(lgN)的解法吗？
d*x
14 楼
不是的，n指的是2进制位数
【在 l*****a 的大作中提到】
: 怎么做都是lg（n）。
: n为该数十进制的值，
: bit的个数为lg（n）。
【在 l*****a 的大作中提到】
: 怎么做都是lg（n）。
: n为该数十进制的值，
: bit的个数为lg（n）。
l*a
15 楼
如果n是二进制的位数，数个数总得访问一遍吧。
这一个访问就是O（n）。
【在 d**********x 的大作中提到】
: 不是的，n指的是2进制位数
这一个访问就是O（n）。
【在 d**********x 的大作中提到】
: 不是的，n指的是2进制位数
b*e
16 楼
移位神马的弱爆了，用这个: x&(x-1)
d*x
17 楼
奇数位和偶数位相加，然后mask
然后每4位，2位2位相加，mask...
【在 l*****a 的大作中提到】
: 如果n是二进制的位数，数个数总得访问一遍吧。
: 这一个访问就是O（n）。
然后每4位，2位2位相加，mask...
【在 l*****a 的大作中提到】
: 如果n是二进制的位数，数个数总得访问一遍吧。
: 这一个访问就是O（n）。
l*b
18 楼
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;
}
{
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
19 楼
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 的大作中提到】
: 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
20 楼
想不出来了。。
【在 d**********x 的大作中提到】
: can u do it better?
【在 d**********x 的大作中提到】
: can u do it better?
l*a
21 楼
这只能去掉最后一位1。如果全是1，还是O（n）。
【在 b*****e 的大作中提到】
: 移位神马的弱爆了，用这个: x&(x-1)
【在 b*****e 的大作中提到】
: 移位神马的弱爆了，用这个: x&(x-1)
d*x
22 楼
没事，只是中间两步可以不用mask...
【在 l*******b 的大作中提到】
: 想不出来了。。
【在 l*******b 的大作中提到】
: 想不出来了。。
l*a
23 楼
碰上一个未知位数的值，如何初始化mask？
对于int，long long等已知type，mask 都是hard coded的。
修改：看道题目说是整数，算是已知type的。
【在 d**********x 的大作中提到】
: 奇数位和偶数位相加，然后mask
: 然后每4位，2位2位相加，mask...
对于int，long long等已知type，mask 都是hard coded的。
修改：看道题目说是整数，算是已知type的。
【在 d**********x 的大作中提到】
: 奇数位和偶数位相加，然后mask
: 然后每4位，2位2位相加，mask...
r*g
24 楼
No, it is already the best.
【在 d**********x 的大作中提到】
: can u do it better?
【在 d**********x 的大作中提到】
: can u do it better?
c*t
25 楼
lanmama说得对，N为该数十进制的值
【在 d**********x 的大作中提到】
: 对了，你这里的N指的是位数吧
【在 d**********x 的大作中提到】
: 对了，你这里的N指的是位数吧
c*t
26 楼
正解！
我电面被问到，给了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;
: }
我电面被问到，给了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
27 楼
如果你看过hacker's delight或者cs:app的话。。
尤其是cs:app第一章或者第二章，常用的这些trick基本都在那了
【在 c********t 的大作中提到】
: 正解！
: 我电面被问到，给了lg(n)解法，bug free,对方似乎不太满意啊。
: 问一下如果没做过，有人能直接给这个解吗？还是我bit operation太弱？
尤其是cs:app第一章或者第二章，常用的这些trick基本都在那了
【在 c********t 的大作中提到】
: 正解！
: 我电面被问到，给了lg(n)解法，bug free,对方似乎不太满意啊。
: 问一下如果没做过，有人能直接给这个解吗？还是我bit operation太弱？
c*t
28 楼
嗯，还真没看过。认栽了！move on了，继续学习。
【在 d**********x 的大作中提到】
: 如果你看过hacker's delight或者cs:app的话。。
: 尤其是cs:app第一章或者第二章，常用的这些trick基本都在那了
【在 d**********x 的大作中提到】
: 如果你看过hacker's delight或者cs:app的话。。
: 尤其是cs:app第一章或者第二章，常用的这些trick基本都在那了
l*b
29 楼
这个其实也是log n的解法呀，n = 32位算5步对应log 32, 更好的不知道了。。
多看看就知道了吧，和教calculus的学生一样，总问这个有什么一般的方法，那只好告
诉他们把吉米多维奇上的积分都解了就可以了，哈哈
多看看就知道了吧，和教calculus的学生一样，总问这个有什么一般的方法，那只好告
诉他们把吉米多维奇上的积分都解了就可以了，哈哈
d*x
30 楼
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.
but 2 less operations is already a big improvement in this case.
【在 r**********g 的大作中提到】
: No, it is already the best.
d*x
31 楼
加油，这种东西就是见过没见过而已
当年别人也用这个打击我来着。。
【在 c********t 的大作中提到】
: 嗯，还真没看过。认栽了！move on了，继续学习。
当年别人也用这个打击我来着。。
【在 c********t 的大作中提到】
: 嗯，还真没看过。认栽了！move on了，继续学习。
c*t
32 楼
这个是明确的 O(5) = O(1)
mod或者右移位，要看整数N大小， 虽然也不过是0--32之间，但确实是O(logN)
关键话语权不在我这边啊。
【在 l*******b 的大作中提到】
: 这个其实也是log n的解法呀，n = 32位算5步对应log 32, 更好的不知道了。。
: 多看看就知道了吧，和教calculus的学生一样，总问这个有什么一般的方法，那只好告
: 诉他们把吉米多维奇上的积分都解了就可以了，哈哈
mod或者右移位，要看整数N大小， 虽然也不过是0--32之间，但确实是O(logN)
关键话语权不在我这边啊。
【在 l*******b 的大作中提到】
: 这个其实也是log n的解法呀，n = 32位算5步对应log 32, 更好的不知道了。。
: 多看看就知道了吧，和教calculus的学生一样，总问这个有什么一般的方法，那只好告
: 诉他们把吉米多维奇上的积分都解了就可以了，哈哈
h*n
33 楼
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.
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
34 楼
不是这个意思。。
如果你说这个是O(5)，那你的原算法就是O(32)之类的
肯定要定一个变量。。。
好告
【在 c********t 的大作中提到】
: 这个是明确的 O(5) = O(1)
: mod或者右移位，要看整数N大小， 虽然也不过是0--32之间，但确实是O(logN)
: 关键话语权不在我这边啊。
如果你说这个是O(5)，那你的原算法就是O(32)之类的
肯定要定一个变量。。。
好告
【在 c********t 的大作中提到】
: 这个是明确的 O(5) = O(1)
: mod或者右移位，要看整数N大小， 虽然也不过是0--32之间，但确实是O(logN)
: 关键话语权不在我这边啊。
c*t
35 楼
顶！
虽然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;
虽然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
36 楼
cnt = 0;
while (x) {
cnt++;
x &= (x-1);
}
while (x) {
cnt++;
x &= (x-1);
}
b*e
37 楼
1. 你确定你知道什么是big O？
2. 如果全1，你用什么算法比我的快？
【在 l*****a 的大作中提到】
: 这只能去掉最后一位1。如果全是1，还是O（n）。
2. 如果全1，你用什么算法比我的快？
【在 l*****a 的大作中提到】
: 这只能去掉最后一位1。如果全是1，还是O（n）。
相关阅读
【参赛】小矮子里挑出的小将军绣球不开花了肿么办？大家都怎么贴图呢现在[开心一笑]无题桃树开花，狗狗上树砖家说今年会有毁灭性太阳风暴厚着脸皮问问:谁家种紫薯了啊?300油麦菜，300塌棵菜，一颗不能少！寒梅 Flowering Quince调查一下，这里的花匠园丁们希望收到什么样的新年礼物？这地里种的是啥东东?说说美国与中国的四季日期计算法的差异 (转载)有人种过/有种子for峨嵋豆, AKA.宽扁豆吗？荷兰郁金香一碗生的肉末坏了，能沤肥吗？育苗准备豌豆种下去两个星期了， 一直不见发芽， 挖出来看看 ：））平生见过最贵的一朵花，有图有真相新手求助：HD刚买的raspberry就要开花了？有图有真相经历今冬数轮寒流磨难以后， 俺家还剩下以下菜菜幸存：