Z*****Z 发帖数: 723 | 1 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: ZhangBZ (向日葵), 信区: InterviewHackers
标 题: 来个bit题
发信站: BBS 未名空间站 (Fri Jul 2 13:22:29 2010, 美东)
感觉这几个是相关的:
1. Let f(k) = y where k is the y-th number in the increasing sequence of non
-negative integers with the same number of ones in its binary representation
as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6)
= 3 and so on. Given k >= 0, compute f(k).
2. There is a series of numbers in ascending order. All these numbers have t
he sam | Z*****Z 发帖数: 723 | 2 用3去求1、2是不是有点儿傻?
non
representation
6)
t
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 InterviewHackers 俱乐部 】 : 发信人: ZhangBZ (向日葵), 信区: InterviewHackers : 标 题: 来个bit题 : 发信站: BBS 未名空间站 (Fri Jul 2 13:22:29 2010, 美东) : 感觉这几个是相关的: : 1. Let f(k) = y where k is the y-th number in the increasing sequence of non : -negative integers with the same number of ones in its binary representation : as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) : = 3 and so on. Given k >= 0, compute f(k). : 2. There is a series of numbers in ascending order. All these numbers have t
| p******n 发帖数: 32 | 3 第一题,可以这样来做
以二进制数010001001001为例
1. 用0x80000000每次右移1位遍历整个数。遍历完得到这个数里面1的个数,以及每个1
所在位的index
2. 从最左边的1开始,假设这个1后面全是0,算出比当前这个数小的含有相当个数1的
数目,比如,这个例子中最左边的1在第10位,也就是说最左边这个1 后面有10位,那
么含有4个1的数里面,一定有C(10, 4)(10个里面选3个,3个1可以出现在10位里面的
任意3位)个数比它小。
3. 用和2同样的逻辑对每一个1,算出比这个小的数字的个数。这里,对第二个1,就是
C(6.3),第三个1,就是C(3, 2), 第四个1就是C(1,1)
4. 把所有的数目加起来就是所有比这个数小的数字的个数。 | Z*****Z 发帖数: 723 | 4 这样做是不是算重了。用你的例子:010001001001
C(10,4) + C(6,3) + C(3,2) + C(1,1)
考虑把原数的最左边的1移到最右边,即:000001001011
这个数在C(10,4)、 C(6,3) 和 C(3,2)里面都被计算了1次
个1
【在 p******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一题,可以这样来做 : 以二进制数010001001001为例 : 1. 用0x80000000每次右移1位遍历整个数。遍历完得到这个数里面1的个数,以及每个1 : 所在位的index : 2. 从最左边的1开始,假设这个1后面全是0,算出比当前这个数小的含有相当个数1的 : 数目,比如,这个例子中最左边的1在第10位,也就是说最左边这个1 后面有10位,那 : 么含有4个1的数里面,一定有C(10, 4)(10个里面选3个,3个1可以出现在10位里面的 : 任意3位)个数比它小。 : 3. 用和2同样的逻辑对每一个1,算出比这个小的数字的个数。这里,对第二个1,就是 : C(6.3),第三个1,就是C(3, 2), 第四个1就是C(1,1)
| Z*****Z 发帖数: 723 | 5 可不可以这样想。当所求的数中只有1个1的时候是好办的。
计算010001001001,两种情况:
1、 当最左边的1不动时,右面的3个1只能右移。
2、最左边的1向右移动了至少1位,
那么 f(010001001001) = C(10,4) + f(000001001001) + 1
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这样做是不是算重了。用你的例子:010001001001 : C(10,4) + C(6,3) + C(3,2) + C(1,1) : 考虑把原数的最左边的1移到最右边,即:000001001011 : 这个数在C(10,4)、 C(6,3) 和 C(3,2)里面都被计算了1次 : : 个1
| s***e 发帖数: 793 | 6 no.
C(6,3) does not count 010001001001
C(6,3) count like 010000******
clear
【在 Z*****Z 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这样做是不是算重了。用你的例子:010001001001 : C(10,4) + C(6,3) + C(3,2) + C(1,1) : 考虑把原数的最左边的1移到最右边,即:000001001011 : 这个数在C(10,4)、 C(6,3) 和 C(3,2)里面都被计算了1次 : : 个1
| Z*****Z 发帖数: 723 | 7 哦,明白了。我的那个和这个其实是一样的
【在 s***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : no. : C(6,3) does not count 010001001001 : C(6,3) count like 010000****** : clear
| y****n 发帖数: 579 | 8 第三题碰到不存在的情况怎么办?
像0000 0111 next smallest就不存在。 | x****k 发帖数: 2932 | |
|