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）。
相关阅读
北木，求蔬菜种子啊【擂台赛】谁家的甜薯有我多天街小雨大家菜地里的马蜂，蜜蜂多吗?［求助］Japanese beetle 喷药后树叶一夜之间全黄了咋回事谁知道“高洋”何许人也？xing 师弟，lowes $10 0ff $50 胖子又来了！厉害的小童工现在还能种什么?第3周版标--竞拍开始！！老话新说-----老中做饭问题【擂台赛】谁家的太阳花有我的漂染得漂亮借人气哪儿可以买到那种墨西哥的红辣椒， 不是狠辣，求教 五彩西红柿的种子会退化吗？紫薯（叶子）gardening版申请发放”N区第一”活动奖励 (转载)【擂台赛】盆栽的鬼子姜啊，你咋就长得这么高？HD几个月前50%off的球茎我一直放在地下室阴凉处，下个月我能开始埋在土里了吗？(6区)秋实，buffaloboy喊你呢...哈哈【夏天的收获】ROI最高的水果